50pts求调 #2#3#4#5#8
查看原帖
50pts求调 #2#3#4#5#8
549846
dpACerFXing楼主2025/1/15 11:18
# include<iostream>
# include<algorithm>
# include<cmath>
# define endl "\n"
# define int long long
using namespace std;
const int maxn=1e6+5;
struct Node{
	int l, r, e;
}a[maxn];
int t, n, fa[maxn], dct[maxn], cnt=0; 
bool cmp(Node a, Node b) {
	return a.e>b.e;
}
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 >> a[i].l >> a[i].r >> a[i].e;
			dct[++cnt]=a[i].l, dct[++cnt]=a[i].r;
		}
		
		sort(dct+1, dct+cnt+1);
		int tot=unique(dct+1, dct+cnt+1)-dct;
		for(int i=1; i<=n; i++) {
			a[i].l=lower_bound(dct+1, dct+cnt+1, a[i].l)-dct;
			a[i].r=lower_bound(dct+1, dct+cnt+1, a[i].r)-dct;
		}
		for(int i=1; i<=tot; i++) fa[i]=i;
		sort(a+1, a+n+1, cmp);
		for(int i=1; i<=n; i++) {
			if(a[i].l==a[i].r) continue ;
			int fl=f(a[i].l), fr=f(a[i].r);
			if(a[i].e) {
				fa[fl]=fr;
			} else if (fl==fr) {
				flag=false;
				break;
			}
		}
		if(!flag) {
			cout << "NO" << endl;
			continue ;
		}
		cout << "YES" << endl;
	}
	return 0;
}
2025/1/15 11:18
加载中...