50pts求调
查看原帖
50pts求调
749175
114514xxx楼主2024/10/25 11:08
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e6+5;
int f[N],len;
struct problem{
    int x,y,e;
}a[N];
int disc[N];
bool cmp(problem a,problem b){
    if(a.x!=b.x)return a.x<b.x;
    else return a.y<b.y;
}
int cnt=0;
inline int get(int x){return x==f[x]?x:f[x]=get(f[x]);};
inline void merge(int x,int y){int p1=get(x),p2=get(y);f[p1]=f[p2];}
inline bool check(int x,int y){int p1=get(x),p2=get(y);if(p1==p2)return 0;else return 1;}
inline void Discretization(){
    sort(disc+1,disc+1+cnt);
    int len=unique(disc+1,disc+1+cnt)-disc;
    for(int i=1;i<=len;i++){
        a[i].x=lower_bound(disc+1,disc+1+len,a[i].x)-disc;
        a[i].y=lower_bound(disc+1,disc+1+len,a[i].y)-disc;
    }
}
int t,n;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        for(int i=1;i<=n;i++)
            a[i].x=0,a[i].y=0,a[i].e=0;
        for(int i=1;i<=cnt;i++)
            disc[i]=0;
        cnt=0;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i].x>>a[i].y>>a[i].e;
            disc[++cnt]=a[i].x;
            disc[++cnt]=a[i].y;
        }

        for(int i=1;i<=len;i++)
            f[i]=i;
        int flag=1;
        for(int i=1;i<=n;i++){
            if(a[i].e)merge(a[i].x,a[i].y);
            else {
                if(!check(a[i].x,a[i].y)){
                    cout<<"NO\n";
                    flag=0;
                    break;
                }
            }
        }
        if(flag)cout<<"YES\n";
    }
    return 0;
}

2024/10/25 11:08
加载中...