WA on #3 求调
查看原帖
WA on #3 求调
829369
Hiusiudou楼主2023/1/19 14:13
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
struct disc{int original,no;}all[2000010],set[2000010];
struct relation{int mem1,mem2;}is_equal[1000010],not_equal[1000010];
int f[1000010];
int find(int begin,int end,int original){
    //cout<<"find:"<<original<<endl;
    int mid=(begin+end)>>1;
    if(set[mid].original==original)return mid;
    else if(mid>begin&&set[mid].original>original)return find(begin,mid,original);
    else if(mid<end&&set[mid].original<original)return find(mid+1,end,original);
    return -1;//找不到
}
void sort(disc *begin,int l,int r){//从小到大
    //cout<<"sort:"<<l<<' '<<r<<endl;
    int i=l,j=r,mid=(l+r)/2;
    disc temp,mid_data=*(begin+mid);
    do {
        while((begin+i)->original<mid_data.original)i++;
        while((begin+j)->original>mid_data.original)j--;
        if(i<=j){
            temp=*(begin+i),*(begin+i)=*(begin+j),*(begin+j)=temp;
            i++,j--;
        }
    } while (i<=j);
    if(l<j)sort(begin,l,j);
    if(r>i)sort(begin,i,r);
}
int find(int i){return i==f[i]?i:f[i]= find(f[i]);}
int t,n,ii,jj,e;
int eq_size,neq_size,set_size;
bool is;
int main(){
    scanf("%d",&t);
    for (int i = 0; i < t; ++i) {
        //cout<<"i="<<t<<endl;
        eq_size=neq_size=0;
        set_size=1;
        is= true;
        cin>>n;
        for (int j = 0; j < n; ++j) {
            scanf("%d%d%d",&ii,&jj,&e);
            all[j*2].original=ii,all[1+j*2].original=jj;
            if(e)is_equal[eq_size++]={ii,jj};
            else not_equal[neq_size++]={ii,jj};
        }
        sort(all,0,n*2-1);
        set[set_size]=all[0];
        for(int j = 1; j < (n<<1); ++j) {
            if(all[j].original==all[j-1].original)continue;
            set[set_size++]=all[j];
        }
        set_size--;
        for(int j=1;j<=set_size;j++){
            set[j].no=j,f[j]=j;
        }
        for (int j = 0; j < eq_size; ++j) {
            f[find(find(1,set_size,is_equal[j].mem1))]= find(find(1,set_size,is_equal[j].mem2));
        }
        for (int j = 0; j < neq_size; ++j) {
            if(find(find(1,set_size,not_equal[j].mem1))==find(find(1,set_size,not_equal[j].mem2)))
            {
                is= false;
                break;
            }
        }
        if(is)cout<<"YES\n";
        else cout<<"NO\n";
    }
}
2023/1/19 14:13
加载中...