求解为什么 MLE

Fraction @ 2018-04-21 11:44:16

//#define filreader
#include <bits/stdc++.h>
#define fp(i,l,r) for(register int i=(l);i<=(r);++i)
#define fd(i,l,r) for(register int i=(l);i>=(r);--i)
using namespace std;
const int MAXN=10001;

int fa[MAXN],n,m;

inline int stat(int n){
    fp(i,1,n){
        fa[i]=i;
    }
    return 0;
}

inline int find(int x){
    if(fa[x]!=x){
        fa[x]=find(fa[x]);
    }
    return fa[x];
}

inline int unit(int x,int y){
    fa[y]=x;
}

inline bool judg(int x,int y){
    return find(x)==find(y);
}

inline int init(){
    scanf("%d%d",&n,&m);
    int x,y,z;
    stat(n);
    fp(i,1,m){
        scanf("%d",&z);
        if(z==1){
            scanf("%d%d",&x,&y);
            unit(x,y);
        }
        if(z==2){
            scanf("%d%d",&x,&y);
            if(judg(x,y)==true){
                printf("Y\n");
            }
            else{
                printf("N\n"); 
            }
        }
    }
    return 0;
}
int main(){
    #ifdef filreader
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
    #endif
    init();
    return 0;
}

by Fraction @ 2018-04-21 11:47:54

现在不MLE了，WA：30分

//#define filreader
#include <bits/stdc++.h>
#define fp(i,l,r) for(register int i=(l);i<=(r);++i)
#define fd(i,l,r) for(register int i=(l);i>=(r);--i)
using namespace std;
const int MAXN=10001;

int fa[MAXN],n,m;

inline int stat(int n){
    fp(i,1,n){
        fa[i]=i;
    }
    return 0;
}

inline int find(int x){
    if(fa[x]!=x){
        fa[x]=find(fa[x]);
    }
    return fa[x];
}

inline int unit(int x,int y){
    if(find(x)!=find(y))
        fa[y]=x;
}

inline bool judg(int x,int y){
    return find(x)==find(y);
}

inline int init(){
    scanf("%d%d",&n,&m);
    int x,y,z;
    stat(n);
    fp(i,1,m){
        scanf("%d",&z);
        if(z==1){
            scanf("%d%d",&x,&y);
            unit(x,y);
        }
        if(z==2){
            scanf("%d%d",&x,&y);
            if(judg(x,y)==true){
                printf("Y\n");
            }
            else{
                printf("N\n"); 
            }
        }
    }
    return 0;
}

int main(){
    #ifdef filreader
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
    #endif
    init();
    return 0;
}

by AThousandSuns @ 2018-04-21 13:19:02

unit不应该是fa[fa[y]]=x吗