萌新表示很疑惑,好好的 $O(Tn)$ 算法怎么最慢点跑了 $1.38ms$ ?
查看原帖
萌新表示很疑惑,好好的 $O(Tn)$ 算法怎么最慢点跑了 $1.38ms$ ?
658786
STUDENT00楼主2023/1/20 14:32

Thecodeisoverhere:The\quad code\quad is\quad over\quad here:

#include<bits/stdc++.h>
#define N 200005
using namespace std;
int T,n,m,a[N],in[N],cnt,sum[N];
vector<int> g[N];
void dfs(int now){
	in[now]=cnt;sum[cnt]+=a[now];
	for(int i=0;i<g[now].size();i++){if(!in[g[now][i]]) dfs(g[now][i]);}
}
void work(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=(n<<1);i++) g[i].clear();
	for(int i=1;i<=(n<<1);i++) in[i]=sum[i]=cnt=0;
	for(int i=1;i<=(n<<1);i++) scanf("%d",&a[i]);
	while(m--){
		int t,u,v;scanf("%d%d%d",&t,&u,&v);
		if(t==1){g[u].push_back(v+n);g[v+n].push_back(u);g[v].push_back(u+n);g[u+n].push_back(v);}
		else{g[u].push_back(v);g[v].push_back(u);g[u+n].push_back(v+n);g[v+n].push_back(u+n);}
	}
	for(int i=1;i<=(n<<1);i++){
		if(!in[i]){cnt++;dfs(i);}
	}
	for(int i=1;i<=n;i++){
		if(in[i]==in[i+n]){
			if(sum[in[i]]&1){printf("NO\n");return;}
		}else{
			if(sum[in[i]]!=sum[in[i+n]]){printf("NO\n");return;}
		}
	}
	printf("YES\n");return;
}
int main(){
	scanf("%d",&T);
	while(T--) work();
	return 0;
}

Andthisone:And\quad this\quad one:

https://www.luogu.com.cn/record/100297368

2023/1/20 14:32
加载中...