萌新求调,AC 3个点,RE 1个点,剩下的全WA
查看原帖
萌新求调,AC 3个点,RE 1个点,剩下的全WA
298561
sundavid123楼主2023/1/13 19:20
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2000008;
int n,btop = 0,ctop = 0,T;
bool ans;
int b[maxn * 2],c[maxn * 2];
int fa[maxn * 2];
struct node{
	int x,y,z;
}a[maxn];
int finder(int x){
	if(fa[x] == x) return x;
	return fa[x] = finder(fa[x]);
}
void cpy(int x,int y){
	if(finder(x) != finder(y)){
		fa[y] = x;
	}
}
void push_in_b(int x){
	b[++btop] = x;
}
void initer(){
	btop = 0;
	ctop = 0;
	memset(b,0,sizeof(b));
	memset(c,0,sizeof(c));
	for(int i = 0; i < maxn; i++) a[i] = {0,0,0};
	for(int i = 0; i < maxn * 2; i++) fa[i] = i;
	ans = 1;
}
int main(){
	cin>>T;
	while(T--){
		initer();
		scanf("%d",&n);
		for(int i = 1; i <= n; i++){
			scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
			push_in_b(a[i].x);
			push_in_b(a[i].y);
			if(a[i].x == a[i].y && a[i].z == 0){
				ans = 0;
			}
		}
		sort(b+1,b+1+btop);
		for(int i = 1; i <= btop; i++){
			if(b[i] != b[i-1]) 
				c[++ctop] = b[i];
		}
		for(int i = 1; i <= ctop; i++){
			a[i].x = lower_bound(c+1,c+1+ctop,a[i].x) - c;
			a[i].y = lower_bound(c+1,c+1+ctop,a[i].y) - c;
		}
		for(int i = 1; i <= n; i++){
			if(a[i].z) cpy(a[i].y,a[i].x);
		}
		
		for(int i = 1; i <= n; i++){
			if(a[i].z == 0){
				if(finder(a[i].x) == finder(a[i].y)){
					ans = 0;
					break;
				}
			}
		}
		printf("%s\n",(ans ? "YES" : "NO"));
	}
	return 0;
} 

qwq

2023/1/13 19:20
加载中...