30pts求调
查看原帖
30pts求调
1283045
NOI109_bjh楼主2024/10/8 09:46

求!!!调!!!

#include<bits/stdc++.h>
#define int long long
#define ci const int
#define elif else if

using namespace std;

ci E=2e5+10;
int t,n,fa[E],dis[E],tot,flag;

struct node{
    int a,b,e;
}a[E];

int get(int x){
    return fa[x]==x?x:fa[x]=get(fa[x]);
}

bool cmp(node x,node y){
    return x.e>y.e;
}

signed main(){
	ios::sync_with_stdio(0),
	cin.tie(0),cout.tie(0);
	
	cin>>t;
    while(t--){
        memset(a,0,sizeof(a));
        memset(dis,0,sizeof(dis));
        memset(fa,0,sizeof(fa));
        tot=0,flag=1;

        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i].a>>a[i].b>>a[i].e,
            dis[++tot]=a[i].a,dis[++tot]=a[i].b;
        
        sort(dis+1,dis+1+tot);
        sort(a+1,a+1+n,cmp);
        tot=unique(dis+1,dis+1+tot)-dis+1;
        for(int i=1;i<=tot;i++)fa[i]=i;

        for(int i=1;i<=n;i++)
            a[i].a=lower_bound(dis+1,dis+1+tot,a[i].a)-dis,
            a[i].b=lower_bound(dis+1,dis+1+tot,a[i].b)-dis;

        for(int i=1;i<=n;i++){
            if(a[i].e)
                fa[a[i].a]=get(a[i].b);
            else
                if(get(fa[a[i].a])==get(fa[a[i].b]))flag=0;
        }

        if(flag)cout<<"YES\n";
        else cout<<"NO\n";
    }
	
	return 0;
}
2024/10/8 09:46
加载中...