看起来是道并查集水题……

可i和j最高可达1000000000，直接开个数组放注定会MLE，怎么办？

注意n最高为1000000，所以每组数据中出现的i和j最多会有2000000种，所以我们可以把i和j“映射”为不大于2000000的整数，这样就能避免MLE了！

这种技术，就是离散化

同时注意防卡常！

代码：

/**************************************************************
    Problem: 4195
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1628 ms
    Memory:4812 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
const int maxn=200000; // 常量
/*
    并查集
*/
int p[maxn],rank[maxn];
int find_set(int x){
    if(p[x]==x)
        return x;
    else
        return p[x]=find_set(p[x]);
}
inline void link(int x,int y){
    if(rank[x]>rank[y]){
        p[y]=x;
    }else{
        p[x]=y;
        if(rank[x]==rank[y])
            rank[y]++;
    }
    return;
}
void merge_set(int x,int y){
    link(find_set(x),find_set(y));
    return;
}
bool is_same(int x,int y){
    return find_set(x)==find_set(y);
}
inline void init_set(int n){
    for(register int i=0;i<n;i++)
        p[i]=i;
    memset(rank,0,sizeof(rank));
    return;
}
// 离散化
int A[maxn],a[maxn],b[maxn];
void init_lsh(int n){
    memcpy(b,A,sizeof(A));
    sort(A,A+n);
    register int size=unique(A,A+n)-A;
    for(register int i=0;i<n;i++)
        a[i]=lower_bound(A,A+n,b[i])-A;
}
// 解决问题
bool is_is[maxn/2];
void solve(int n){
    register int i;
    bool ok=true;
    init_lsh(2*n);
    init_set(2*n);
    for(i=0;i<n;i++)
        if(is_is[i])
            merge_set(a[i*2],a[i*2+1]);
    for(i=0;i<n;i++)
        if(!is_is[i] && is_same(a[i*2],a[i*2+1])){
            ok=false;
            puts("NO");
            break;
        }
    if(ok)
        puts("YES");
    return;
}
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int read_data(){
    register int i,n=readint();
    for(i=0;i<n;i++){
        A[i*2]=readint();
        A[i*2+1]=readint();
        is_is[i]=readint();
    }
    return n;
}
int main(){
    register int i,n,t=readint();
    for(i=0;i<t;i++){
        n=read_data();
        solve(n);
    }
    return 0;
}

• 相关文章
• 全局相关文章