WA50求条
查看原帖
WA50求条
768530
Expert_Dream楼主2023/9/9 12:56
#include <bits/stdc++.h>
using namespace std;
int t,n;
const int N = 1e6+5;
struct node{
	int x,y,op;
}a[N];
vector<int> ve;
set<int> st[N];
int f[N];
int find(int x){
	return f[x] == x ? x : f[x] = find(f[x]);
}
void run(){
	for(int i = 1;i <= n;i++){
//		cout<<i<<" ";
		if(a[i].op){//?? 
			if(*st[find(a[i].x)].lower_bound(find(a[i].y)) != find(a[i].y)){//??????????? 
				int xx = find(a[i].x);
				int yy = find(a[i].y);
				for(auto it:st[xx]){//???????? 
					st[yy].insert(it);
				}
				f[xx] = yy;//?? 
			}else{
				cout<<"NO\n";//???????,??????,??,?? 
				return;
			}
		}else{
			if(find(a[i].x) == find(a[i].y)){//??????,????????,?? 
				cout<<"NO\n";
				return;
			}else{
				st[find(a[i].x)].insert(find(a[i].y));//???????? 
				st[find(a[i].y)].insert(find(a[i].x));
			}
		}
		
//		cout<<i<<" ";
	}	
	cout<<"YES\n";
	return;
}
int main(){
//	freopen("P1955_2.in","r",stdin);
	cin >> t;
	while(t--){
		cin >> n;
		ve.clear();
		for(int i = 1;i <= n*2;i++) st[i].clear();
		for(int i = 1;i <= n;i++){
			scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].op);
			ve.push_back(a[i].x);
			ve.push_back(a[i].y);
		}
		sort(ve.begin(),ve.end());
		ve.erase(unique(ve.begin(),ve.end()),ve.end());
		for(int i = 1;i <= n;i++){
			a[i].x = lower_bound(ve.begin(),ve.end(),a[i].x) - ve.begin() +1;
			a[i].y = lower_bound(ve.begin(),ve.end(),a[i].y) - ve.begin() +1;
//			cout<<a[i].x<<" "<<a[i].y<<endl;
		}
		
		for(int i = 1;i<=2*n;i++){
			f[i]=i;
		}
		run();		
//		for(int i=1;i <= 2 * n;i++){
//			cout<<i<<": ";
//			for(auto it:st[i]){
//				cout<<it<<" ";
//			}cout<<endl;
//		}
//		for(int i = 1;i <= 2 *n;i++){
//			cout<<find(i)<<" ";
//		}
	}
	return 0;
}
2023/9/9 12:56
加载中...