60分求条,4个WA
查看原帖
60分求条,4个WA
1056507
Andy1101楼主2025/8/2 12:45
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct node{
    int x,y,e;
}a[N];
bool cmp(node x,node y)
{
    return x.e>y.e;
}
int f[N];
int book[N*2];
int find(int x)
{
    if(f[x]==x) return x;
    else return f[x]=find(f[x]);
}
void solve()
{
    memset(book,0,sizeof book);
    memset(f,0,sizeof f);
    memset(a,0,sizeof a);
    int n;
    cin>>n;
    int idx=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y>>a[i].e;
        book[++idx]=a[i].x;
        book[++idx]=a[i].y;
    }
    sort(book+1,book+idx+1);
    int tot=unique(book+1,book+idx+1)-book;
    for(int i=1;i<=n;i++)
    {
        a[i].x=lower_bound(book+1,book+idx+1,a[i].x)-book;
a[i].y=lower_bound(book+1,book+idx+1,a[i].y)-book;
    }
    for(int i=1;i<=tot;i++) f[i]=i;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(a[i].e) f[find(a[i].x)]=find(a[i].y);
        else
        {
            if(find(a[i].x)==find(a[i].y))
            {
                cout<<"NO"<<'\n';
                return ;
            }
        }
    }
    cout <<"YES"<<'\n';
}
int main()
{
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}
2025/8/2 12:45
加载中...