【注意】Wrong Answer 20pts求调
查看原帖
【注意】Wrong Answer 20pts求调
723466
banned_gutongxing楼主2024/1/20 08:36

(点击进入提交记录)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e6+10;
int T,n,x,y,e,jsum,usum,dsum;
struct judge{
	int x,y;
}j[MAXN];
struct un{
	int x,y;
}u[MAXN];
//DSU
int fath[MAXN];
void init(){
	memset(fath,0,sizeof(fath));
	for(int i = 1;i<=5*n;i++){
		fath[i] = i;
	}
}
int get_father(int x){
	if(x == fath[x]) return x;
	return fath[x] = get_father(fath[x]);
}
void merge(int x,int y){
	fath[get_father(x)] = get_father(y);
}
//Lisanhau
struct discre{
	int x,belong,joru,xory;
}disc[MAXN];
bool dis_with_x(discre a,discre b){
	return a.x<b.x;
}
int discsum;
void discretize(){
	int sum = 0;
	sort(disc+1,disc+1+discsum,dis_with_x);
	for(int i = 1;i<=discsum;i++){
		if(i!=1&&disc[i].x==disc[i-1].x){
			disc[i].x = sum; 
		}else{
			disc[i].x = ++sum;
		}
	}
	for(int i = 1;i<=discsum;i++){
		if(disc[i].joru==1){
			if(disc[i].xory==1){
				j[disc[i].belong].x = disc[i].x;
			}else j[disc[i].belong].y = disc[i].x;
		}else{
			if(disc[i].xory==1){
				u[disc[i].belong].x = disc[i].x;
			}else u[disc[i].belong].y = disc[i].x;
		}
	}
	dsum = sum;
} 
signed main(){
	scanf("%lld",&T);
	while(T--){
		jsum = usum = discsum = 0;
		scanf("%lld",&n);
		for(int i = 1;i<=n;i++){
			scanf("%lld%lld%lld",&x,&y,&e);
			if(e==1){
				u[++usum] = {x,y};
				disc[++discsum] = {x,usum,2,1};
				disc[++discsum] = {y,usum,2,2};
			}else{
				j[++jsum] = {x,y};
				disc[++discsum] = {x,jsum,1,1};
				disc[++discsum] = {y,jsum,1,2};
			}
		}if(T==0){
			bool p =0;
		}
		discretize();
		init();
		for(int i = 1;i<=usum;i++){
			merge(u[i].x,u[i].y);
		}
		bool fg = 0;
		
		for(int i = 1;i<=jsum;i++){
			if(get_father(j[i].x)==get_father(j[i].y)){
				fg = 1;
				puts("NO");
				break;
			} 
		}
		if(!fg){
			puts("YES");
		}
	}
	return 0;
}
2024/1/20 08:36
加载中...