跪请大佬帮调……
查看原帖
跪请大佬帮调……
592402
Pure_Echo楼主2024/8/12 20:04
#include<bits/stdc++.h>
using namespace std;
int n,t,cnt,w;
long long f[200100],x,y; 
struct op{
	long long u,v;
}den[100100],yi[100100];
int de1,yi1;
int fu[200100];
int cha(int o){
	if(fu[o]!=o) return fu[o]=cha(fu[o]);
	return o;
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		de1=0,yi1=0;
		for(int i=1;i<=n;i++){
			scanf("%lld %lld %d",&x,&y,&w);
			f[2*(i-1)+1]=x;fu[2*(i-1)+1]=2*(i-1)+1;
			f[2*i]=y;fu[2*i]=2*i;
			if(w==1) den[++de1].u=x,den[de1].v=y;
			else  yi[++yi1].u=x,yi[yi1].v=y;
		}
		sort(f+1,f+2*n+1);
		cnt=unique(f+1,f+2*n+1)-f-1;		
		for(int i=1;i<=de1;i++){
			int u=lower_bound(f+1,f+cnt+1,den[i].u)-f;
			int v=lower_bound(f+1,f+cnt+1,den[i].v)-f;
			int f1=cha(u);
			int f2=cha(v);
			fu[f2]=f1;
		}
		bool ans=1;
		for(int i=1;i<=yi1;i++){
			int u=lower_bound(f+1,f+cnt+1,yi[i].u)-f;
			int v=lower_bound(f+1,f+cnt+1,yi[i].v)-f;
			if(fu[u]==fu[v]){
				ans=0;
				break;
			}
		}
		if(ans) puts("YES");
		else puts("NO");
	}
	return 0;
}

2024/8/12 20:04
加载中...