社区讨论
百爪挠心血泪求助,WA第一个点,90pts分
P3854[TJOI2008] 通讯网破坏参与者 4已保存回复 7
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @mhj1s9v9
- 此快照首次捕获于
- 2025/11/03 19:19 4 个月前
- 此快照最后确认于
- 2025/11/03 19:19 4 个月前
CPP
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
using namespace std;
template <class T>
string toString(T x) { return to_string(x); }
string toString(const char *x) { return string(x); }
string toString(const string &x) { return x; }
template <class T>
string expand(const T &x) { return toString(x); }
template <class T, class... A>
string expand(const T &x, A... a) { return expand(x) + ", " + expand(a...); }
int read(){int type = 1, n = 0;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-'){type = -1;}ch = getchar();}while (ch >= '0' && ch <= '9'){n = (n << 1) + (n << 3) + (ch ^ 48),ch = getchar();}return n * type;}
void write(int n){if (n < 0){putchar('-'), n = -n;}if (n < 10){return putchar(n + '0'), void();}return write(n / 10), putchar(n % 10 + '0'), void();}
void wt(int n, bool o = 1){write(n);if (!o){putchar(' ');}else{putchar('\n');}}
#define debug(a...) cerr << "[" << #a << "] = " << expand(a) << '\n'
#define fileio(x) (freopen(x".in", "r", stdin), freopen(x".out", "w", stdout))
#define rd read()
#define ptc putchar('\n')
#define pii pair<int, int>
const int N = 2e5 + 10;
const int newN = 4e4 + 10;
const int MOD = 998244353;
const int INF = 0x7fffffff;
const int Fill = 0x3f3f3f3f;
int vdcctot, dfscnt, nodetot; // 点双标号,dfs序,圆方树总节点数
int low[N], dfn[N], bel[N], cutId[N]; // bel[i] 是 i属于哪一个点双,cutId是割点的新标号
int fa[newN][23], dep[newN], lg[newN]; // LCA要用的数组
bool cut[N]; // 是否为割点
stack <int> st;
vector <int> G[N], tr[newN], vdcc[N];
void tarjan(int id, int rt) // 常规求点双连通分量,这部分改一改交到模板题过了,大概率没错
{
int flag = 0;
if (id == rt && !G[id].size())
{
vdcc[++vdcctot].push_back(id);
return ;
}
low[id] = dfn[id] = ++dfscnt;
st.push(id);
for (int to : G[id])
{
if (!dfn[to])
{
tarjan(to, rt);
low[id] = min(low[id], low[to]);
if (low[to] >= dfn[id])
{
flag++;
int lst = -1;
vdcctot++;
vdcc[vdcctot].push_back(id);
while (lst != to)
{
lst = st.top();
st.pop();
vdcc[vdcctot].push_back(lst);
}
if (id != rt || flag >= 2)
{
cut[id] = 1;
}
}
}
else
{
low[id] = min(low[id], dfn[to]);
}
}
}
void dfs(int id, int from) // LCA预处理
{
int i;
dep[id] = dep[from] + 1;
fa[id][0] = from;
for (i = 1; i <= lg[dep[id]]; i++)
{
fa[id][i] = fa[fa[id][i - 1]][i - 1];
}
for (int son : tr[id])
{
if (son == from) continue;
dfs(son, id);
}
}
int lca(int x, int y) // LCA
{
int i;
if (dep[x] < dep[y])
{
swap(x, y);
}
for (i = 20; i >= 0; i--)
{
if (dep[fa[x][i]] >= dep[y])
{
x = fa[x][i];
}
}
if (x == y) return x;
for (i = 20; i >= 0; i--)
{
if (fa[x][i] != fa[y][i])
{
x = fa[x][i], y = fa[y][i];
}
}
return fa[x][0];
}
void build()
{
int i, j;
int n = rd, m = rd;
for (i = 1; i <= m; i++)
{
int x = rd, y = rd;
G[x].push_back(y), G[y].push_back(x);
}
for (i = 1; i <= n; i++)
{
if (!dfn[i]) tarjan(i, i);
}
lg[1] = 0;
for (i = 2; i <= newN - 5; i++)
{
lg[i] = lg[i >> 1] + 1;
}
nodetot = vdcctot;
for (i = 1; i <= n; i++)
{
if (cut[i]) cutId[i] = ++nodetot; // 割点重标号
}
for (i = 1; i <= vdcctot; i++)
{
for (int node : vdcc[i])
{
if (cut[node])
{
tr[cutId[node]].push_back(i);
tr[i].push_back(cutId[node]); // 建圆方树,i是方点,node是圆点
}
else
{
bel[node] = i;
}
}
}
dfs(1, 0);
}
int dis(int x, int y)
{
int anc = lca(x, y);
// debug(x,y,anc);
int res = dep[x] + dep[y] - 2 * dep[anc] + 1;
return res;
}
void solve()
{
int i, j;
int s = rd, t = rd, m = rd;
if (bel[s] == bel[t])
{
cout << "no\n";
return ;
}
if (!cut[m])
{
cout << "no\n";
return ;
}
if (cut[s]) s = cutId[s];
else s = bel[s];
if (cut[t]) t = cutId[t];
else t = bel[t];
m = cutId[m];
int LCA = lca(s, t);
if (lca(LCA, m) != LCA)
{
cout << "no\n";
return ;
}
if (lca(s, m) != m && lca(t, m) != m)
{
cout << "no\n";
return ;
}
cout << "yes\n";
return ;
}
signed main()
{
int T;
int i, j;
build();
T = rd;
while (T--)
{
solve();
}
return 0;
}
一整天了一直挂第一个点,跪求调题,感激不尽
甚至这个题提交记录里有大量90分
回复
共 7 条回复,欢迎继续交流。
正在加载回复...