RE是什么情况

P1197 [JSOI2008] 星球大战

Richard21477 @ 2020-11-06 20:04:53

萌新求助

#include<bits/stdc++.h>
using namespace std;
// start from zero
int f[100010];
int father(int x){
    return (x==f[x])?x:f[x]=father(f[x]);
}
int p[100010],ed[400050],ne[400050];
int cnt=1;
void insert(int u,int v){
    ed[cnt]=v;
    ne[cnt]=p[u];
    p[u]=cnt++;
    return;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    int x,y;
    for (int i=0;i<m;i++){
        scanf("%d%d",&x,&y);
        insert(x,y);
        insert(y,x);
    }
    int k;
    scanf("%d",&k);
    bool ext[n];
    int cut[k];
    for (int i=0;i<n;i++)
        ext[i]=true;
    for (int i=0;i<n;i++)
        f[i]=i;
    for (int i=0;i<k;i++){
        scanf ("%d",&cut[i]);
        ext[cut[i]]=false;
    }
    int ans[k+1];
    int cnt=n;
    int u,v,fv,fu;
    for (u=0;u<n;u++){
        if (!ext[u]){
            cnt--;
            continue;
        }
        for (int i=p[u];i!=0;i=ne[i]){
            v=ed[i];
            if (!ext[v])
                continue;
            fu=father(u);
            fv=father(v);
            if (fu!=fv){
                cnt--;
                f[fu]=fv;
            }
        }
    }
    ans[k]=cnt;
    for (int t=k-1;t>=0;t--){
        //cut[i]
        u=cut[t];
        ext[u]=true;
        cnt++;
        for (int i=p[u];i!=0;i=ne[i]){
            v=ed[i];
            if (!ext[v])
                continue;
            fu=father(u);
            fv=father(v);
            if (fu!=fv){
                cnt--;
                f[fu]=fv;
            }
        } 
        ans[t]=cnt;
    }
    for (int i=0;i<=k;i++)
        printf("%d\n",ans[i]);
    //printf("\n");
    return 0;

}

3RE1WA


by Richard21477 @ 2020-11-06 20:28:36

啊这

这道题第9个点WA/TLE的同学注意


|