p2416不知道哪错了
  • 板块题目总版
  • 楼主Yu_Chengxuan
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/8 15:38
  • 上次更新2024/8/8 16:17:01
查看原帖
p2416不知道哪错了
782210
Yu_Chengxuan楼主2024/8/8 15:38
#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e5 + 10;
struct node {
	int v,w;
};
vector<node> e[maxn];
vector<node> g[maxn];
int dfn[maxn],low[maxn],scc[maxn],ins[maxn],f[maxn][25],val[maxn][25],deep[maxn],dot[maxn],tot,cnt;
stack<int> s;
inline int read() {
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9') {
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&& ch<='9') {
		x=x*10+ch-48;
		ch=getchar();
	}
	return x*f;
}

void tarjan(int u ,int pre){
	dfn[u] = low[u] = ++tot;
	s.push(u);
	ins[u]=1;
	bool f = 0;
	for (auto i:e[u]){
		int v = i.v;
		if (v == pre && !f){
			f = 1;
			continue;
		}
		if (!dfn[v]){
			tarjan(v,u);
			low[u] = min(low[u] ,low[v]);
		}
		else if (ins[v]){
			low[u] = min(low[u] ,dfn[v]);
		}	
	}

	if (dfn[u] == low[u]){
		int x;
		cnt++;
		do{
			x = s.top(); 
			ins[x] = 0;
			scc[x] = cnt;			
			s.pop();
		} while (x != u);
	}
}
void dfs(int u ,int fa){
	deep[u] = deep[fa] + 1;
	for (auto x : g[u]){
		int v=x.v;
		if (v != fa){
			f[u][0] = fa;
			val[v][0] = dot[v] | dot[u] | x.w;
			dfs(v,u);
		}
	}
}
int lca(int a, int b) {
    int ans = 0;
    if (deep[a] < deep[b])
        swap(a, b);
    for (int i = 20; i >= 0; i--) {
        if (deep[f[a][i]] >= deep[b]) {
            ans = max(ans, val[a][i]);
            a = f[a][i];
        }
    }
    if (a == b)
        return ans;
    for (int i = 20; i >= 0; i--) {
        if (f[a][i] != f[b][i]) {
            ans = max(ans, max(val[a][i], val[b][i]));
            a = f[a][i];
            b = f[b][i];
        }
    }
    ans = max(ans, max(val[a][0], val[b][0]));
    return ans;
}
signed main() {
	int n=read(),m=read();
	for (int i=1; i<=m; i++) {
		int u=read(),v=read(),w=read();
		e[u].push_back({v,w});
		e[v].push_back({u,w});
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i]) {
			tarjan(i,0);
		}
	}
	for (int u=1; u<=n; u++) {
		for (auto x:e[u]) {
			int v=x.v;
			if (scc[u]!=scc[v]) {
				g[scc[u]].push_back({scc[v],x.w});
			} else {
				dot[scc[u]] |= x.w;
			}
		}
	}
	dfs(1,0);
	for (int i=1; i<=cnt; i++) {
		for (int j=1; j<=24; j++) {
			f[i][j]=f[f[i][j-1]][j-1];
			val[i][j]=max(val[f[i][j-1]][j-1],val[i][j-1]);
		}
	}
	int q=read();
	while (q--) {
		int u=read(), v=read();
		u=scc[u],v=scc[v];
		if (u==v) {
			(dot[u]) ? puts("YES") : puts("NO");
		} else (lca(u,v)) ? (puts("YES")) : (puts("NO"));
	}
}
2024/8/8 15:38
加载中...