60pts求调,WA on #2#4#5#8
查看原帖
60pts求调,WA on #2#4#5#8
549846
dpACerFXing楼主2025/1/15 11:19
# include<iostream>
# include<algorithm>
# include<cmath>
# define endl "\n"
# define int long long
using namespace std;
const int maxn=1e6+5;
int t, n, l[maxn], r[maxn], e[maxn], fa[maxn], dct[maxn], cnt=0; 
int f(int u) {
	if(fa[u]==u) return u;
	fa[u]=f(fa[u]);
	return fa[u];
}
signed main() {
	cin >> t;
	while(t--) {
		cin >> n; cnt=0; 
		bool flag=true;
		for(int i=1; i<=n; i++) {
			cin >> l[i] >> r[i] >> e[i];
			if(l[i]==r[i]) {
				if(!e[i]) {
					flag=false;
					break;
				}
			} else dct[++cnt]=l[i], dct[++cnt]=r[i];
		}
		if(!flag) {
			cout << "NO" << endl;
			continue ;
		}
		
		sort(dct+1, dct+cnt+1);
		int tot=unique(dct+1, dct+cnt+1)-dct;
		for(int i=1; i<=n; i++) {
			l[i]=lower_bound(dct+1, dct+cnt+1, l[i])-dct;
			r[i]=lower_bound(dct+1, dct+cnt+1, r[i])-dct;
		}
		for(int i=1; i<=tot; i++) fa[i]=i;
		for(int i=1; i<=n; i++) {
			if(l[i]==r[i]) continue ;
			int fl=f(l[i]), fr=f(r[i]);
			if(e[i]==1) {
				if(fl!=fr) fa[fl]=fr;
			}
		}
		for(int i=1; i<=n; i++) {
			if(l[i]==r[i]) continue ;
			int fl=f(l[i]), fr=f(r[i]);
			if(!e[i]) {
				if(fl==fr) {
					flag=false;
					break;
				}
			}
		} 
		if(!flag) {
			cout << "NO" << endl;
			continue ;
		}
		cout << "YES" << endl;
	}
	return 0;
}
2025/1/15 11:19
加载中...