WA on #10 求调

P1197 [JSOI2008] 星球大战

DYH_bubble @ 2024-11-29 22:38:12

#include<bits/stdc++.h>
using namespace std;
const int MAXN=400001;
int n,m,k,f[MAXN],q[MAXN],lv[MAXN],I,J,j=1,cnt,ans[MAXN];
struct con{
    int a,b;
    bool operator < (con _) const {
        return max(lv[a],lv[b])<max(lv[_.a],lv[_.b]);
    }
} adj[MAXN];
int F(int i){
    if(f[i]==i) return i;
    else return f[i]=F(f[i]);
}
void merge(int i,int j){
    I=F(i);
    J=F(j);
    if(I==J) return;
    f[J]=I;
    cnt++;
}
void pre(){
    for(int i=1;i<=n;i++) f[i]=i;
}
int main(){
    cin>>n>>m;
    pre();
    for(int i=1;i<=m;i++){
        cin>>adj[i].a>>adj[i].b;
        adj[i].a++;adj[i].b++;
    }
    cin>>k;
    for(int i=1;i<=k;i++){
        cin>>q[i];
        q[i]++;
        lv[q[i]]=k-i+1;
    }
    sort(adj+1,adj+m+1);
    for(int i=k;i>=1;i--){
        for(;j<=m,max(lv[adj[j].a],lv[adj[j].b])<lv[q[i]];j++){
            merge(adj[j].a,adj[j].b);
        }
        ans[i]=n-cnt;
    }
    for(;j<=m;j++){
        merge(adj[j].a,adj[j].b);
    }
    ans[0]=n-cnt;
    for(int i=0;i<=k;i++) cout<<ans[i]-i<<'\n';
    return 0;
}

|