70pts求调
  • 板块P2416 泡芙
  • 楼主Yu_Chengxuan
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/8/8 10:55
  • 上次更新2024/8/8 11:32:53
查看原帖
70pts求调
782210
Yu_Chengxuan楼主2024/8/8 10:55
#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e5 + 10;
struct node {
	int v,w;
};
struct edge{
	int u,v,w,nxt;
};
vector<node> g[maxn];
edge e[maxn*2];
int dfn[maxn],low[maxn],scc[maxn],ins[maxn],f[maxn][16],val[maxn][16],deep[maxn],dot[maxn],head[maxn],tot,cnt,edg;
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-'0',ch=getchar();
	return x*f;
}
inline void add(int u,int v,int w){
	edg++;
	e[edg].nxt = head[u];
	e[edg].u = u,e[edg].v = v;
	e[edg].w = w;
	head[u] = edg;
}
void tarjan(int u ,int pre) {
	low[u]=dfn[u]=++tot;
	ins[u]=true;
	s.push(u);
	bool flag=0;
	for (int i = head[u];i;i = e[i].nxt){
		int v=e[i].v;
		if (v == pre && !flag){
			flag=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 (low[u]==dfn[u]) {
		cnt++;
		int check=-1;
		do {
			check=s.top();
			s.pop();
			ins[check] = 0;
			scc[check] = cnt;
		} while (check!=u);
	}
}
void bfs() {
	memset(deep,0x3f,sizeof(deep));
	deep[0]=0;
	deep[1]=1;
	queue<int> q;
	q.push(1);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (node y : g[x]) {
			int i=y.v;
			if (deep[i]<deep[x]) {
				continue;
			}
			q.push(i);
			deep[i] = deep[x]+1;
			f[i][0]=x;
			val[i][0]=dot[i]|y.w|dot[x];
		}
	}
}
int lca(int a,int b) {
	if (deep[a]<deep[b]) swap(a,b);
	int ans=0;
	for (int i=15; i>=0; i--) {
		if (deep[f[a][i]]>=deep[b]) {
			ans=max(val[a][i],ans);
			a=f[a][i];
		}
	}
	if (a==b) return ans;
	for (int i=15; i>=0; i--) {
		if (f[a][i]!=f[b][i]) {
			ans=max(val[a][i],ans);
			ans=max(val[b][i],ans);
			a=f[a][i];
			b=f[b][i];
		}
	}
	return max(val[a][0],val[b][0])|ans;
}
signed main() {
	int n=read(),m=read();
	for (int i=1; i<=m; i++) {
		int u=read(),v=read(),w=read();
		add(u,v,w);
		add(v,u,w);	
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i]) {
			tarjan(i,0);
		}
	}
	for (int i=1;i<=2*m;i++){
		int u = e[i].u,v = e[i].v;
		if (scc[u] == scc[v]){
			dot[scc[u]] |= e[i].w;
		}
		else{
			g[scc[u]].push_back({scc[v],e[i].w});
		}
	}
	bfs();
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=15; 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 10:55
加载中...