求助,一个点没过,wa,样例过了

P1197 [JSOI2008] 星球大战

!!!A @ 2023-09-30 10:34:29

#include<bits/stdc++.h>
using namespace std;
int n,k,m,u,v,p,q,op;
int f[1000001];
int jl[1000001];
bool pd[1000001],kp;
int del[1000001];
int ans;
int anss[100001],ansk;
struct aaaa
{
    int l;
    int r;
}ma[1000001];
bool cmp(aaaa xx,aaaa yy)
{
    if(xx.l==yy.l)
    {
        return xx.r<yy.r;
    }
    return xx.l<yy.l;
}
inline int gf(int xx)
{
    if(f[xx]==xx)
    {
        return xx;
    }
    return f[xx]=gf(f[xx]);
}
int main()
{
    cin>>n>>m;
    for(int i=0; i<n; i++)
    {
        f[i]=i;
    }
    for(int i=1; i<=m; i++)
    {
        cin>>u>>v;
        ma[i*2-1].l=u;
        ma[i*2-1].r=v;
        ma[i*2].l=v;
        ma[i*2].r=u;
    }
    sort(ma+1,ma+2*m+1,cmp);
    for(int i=1; i<=2*m; i++)
    {
        jl[ma[i].l]++;
    }
    for(int i=1; i<n; i++)
    {
        jl[i]+=jl[i-1];
    }
    scanf("%d",&k);
    for(int i=1; i<=k; i++)
    {
        scanf("%d",&del[i]);
        pd[del[i]]=true;
    }
    for(int i=0; i<n; i++)
    {
        if(pd[i])
        {
            continue;
        }
        if(i==0)
        {
            for(int j=1; j<=jl[0]; j++)
            {
                if(pd[ma[j].r]==true)
                {
                    continue;
                }
                p=gf(ma[j].l);
                q=gf(ma[j].r);
                f[p]=q;
            }
            continue;
        }
        for(int j=jl[i-1]+1; j<=jl[i]; j++)
        {
            if(pd[ma[j].r]==true)
            {
                    continue;
            }
            p=gf(ma[j].l);
            q=gf(ma[j].r);
            f[p]=q;
        }
    }
    for(int i=0; i<n; i++)
    {
        if(pd[i]==true)
        {
            continue;
        }
        gf(i);
        if(i==f[i])
        {
            ans++;
        }
    }
    ansk++;
    anss[ansk]=ans;
    for(int i=k; i>=1; i--)
    {
        kp=false;
        pd[del[i]]=false;
        op=del[i];
        if(op==0)
        {
            for(int j=1; j<=jl[0]; j++)
            {
                if(pd[ma[j].r]==true)
                {
                    continue;
                }
                p=gf(ma[j].l);
                q=gf(ma[j].r);
                if(kp && p!=q)
                {
                    ans--;
                }
                f[p]=q;
                kp=true;
            }
            continue;
        }
        for(int j=jl[op-1]+1; j<=jl[op]; j++)
        {
            if(pd[ma[j].r]==true)
            {
                continue;
            }
            p=gf(ma[j].l);
            q=gf(ma[j].r);
            if(kp && p!=q)
            {
                ans--;
            }
            f[p]=q;
            kp=true;
        }
        ansk++;
        anss[ansk]=ans;
    }
    for(int i=ansk; i>=1; i--)
    {
        cout<<anss[i]<<endl;
    }
    return 0;
}

by andy_2005 @ 2023-12-04 22:22:57

153行超短代码


|