O(nlogn) TLE 70pts求助
查看原帖
O(nlogn) TLE 70pts求助
1517143
Psy_Chen楼主2024/11/26 21:20
// #pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll =long long;
const int MAXNUM =1e6+5;
int fa[MAXNUM*2]={0};
ll num[MAXNUM*2]={0};
bool flag[MAXNUM]={0};

int equal(int x){
    if(fa[x]==x) return x;
    return equal(fa[x]);
}

void merge(int x,int y){
    int fx=equal(x),fy=equal(y);
    if(fx!=fy)fa[fx]=fa[fy];
    return;
}

struct XX{
    long long xnum;
    int numc;
}xi[MAXNUM*2];


int main(){
    // freopen("P1955_2.in","r",stdin);
    int t;
    cin>>t;
    for(int x=1;x<=t;x++){
        int n;
        memset(fa,0,sizeof(fa));
        memset(num,0,sizeof(num));
        memset(flag,0,sizeof(flag));
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>xi[i].xnum>>xi[i+n].xnum>>flag[i];
            num[i]=xi[i].xnum,num[i+n]=xi[i+n].xnum;
        }
        sort(num+1,num+1+2*n);
        auto len = unique(num+1,num+1+2*n)-(num+1);
        for(int i=1;i<=n;i++){//O(nlogn)
            xi[i].numc=lower_bound(num+1,num+len,xi[i].xnum)-num;
            xi[i+n].numc=lower_bound(num+1,num+len,xi[i+n].xnum)-num;           
            fa[xi[i].numc]=xi[i].numc;fa[xi[i+n].numc]=xi[i+n].numc;
        }
        bool yes=true;
        for(int i=1;i<=n;i++){
            if(flag[i]&&equal(xi[i].numc)!=equal(xi[i+n].numc)){
                merge(xi[i].numc,xi[i+n].numc);
            }
        }
        for(int i=1;i<=n;i++){
            if(!flag[i]){
                if(equal(xi[i].numc)==equal(xi[i+n].numc)){
                    yes=false;
                    break;
                }
            }
        }
        if(yes){
            cout<<"YES"<<endl;
        }
        else{
            cout<<"NO"<<endl;
        }
    }
    return 0;
}
2024/11/26 21:20
加载中...