评测记录

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5,M=1e7+5;
const int mod=1000003;

struct hashmap
{
    struct node{long long key,val;};
    vector<node> mp[mod];
    long long& operator[](long long index)
    {
        for(int i=0;i<mp[index%mod].size();i++)
            if(mp[index%mod][i].key==index)
                return mp[index%mod][i].val;
        mp[index%mod].push_back(node{index,0});
        return mp[index%mod][mp[index%mod].size()-1].val;
    }
};
struct mergeset
{
    int st[M];
    mergeset(){for(int i=0;i<M;i++) st[i]=i;}
    int find(int pos){return (st[pos]==pos?pos:st[pos]=find(st[pos]));}
    void merge(int a,int b){a=find(a);b=find(b);st[a]=b;}
};
struct oper{int e,i,j;}op[N];
bool cmp(oper a,oper b) {return (a.e>b.e);}

int main()
{
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(false);
    int T;cin>>T;
    while(T--)
    {
        int n,i;cin>>n;
        bool flag=true;
        for(int i=0;i<n;i++) cin>>op[i].i>>op[i].j>>op[i].e;
        sort(op,op+n,cmp);
        hashmap a;
        mergeset ms;
        for(int i=0,j=1;i<n;i++)
        {
            if(!a[op[i].i]) a[op[i].i]=j++;
            if(!a[op[i].j]) a[op[i].j]=j++;
        }
        for(i=0;op[i].e&&i<n;i++)
            ms.merge(op[i].i,op[i].j);
        for(;i<n;i++)
            if(ms.find(op[i].i)==ms.find(op[i].j))
            {flag=false;break;}
        if(flag) cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}

qwq