社区讨论

我被犇站卡了!!!

P1197[JSOI2008] 星球大战参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mi6ho52h
此快照首次捕获于
2025/11/20 05:02
4 个月前
此快照最后确认于
2025/11/20 05:02
4 个月前
查看原帖
同样的代码,犇站50,主站AC、
···cpp
CPP
#include<cstdio>
#include<algorithm>
const int maxn=4e5+10;
const int maxm=2e5+10;
int n,m,k,now;
int t[maxn],f[maxn],ans[maxn];
struct edge{int u,v,time;}e[maxm];
bool comp(edge x,edge y){return x.time<y.time;}
int find(int k){return f[k]==k?k:f[k]=find(f[k]);}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++) scanf("%d%d",&e[i].u,&e[i].v);
    scanf("%d",&k);
    int a,b;
    for(int i=k;i>0;i--){
        scanf("%d",&a);
        t[a]=i;
    }
    for(int i=1;i<=m;i++) e[i].time=std::max(t[e[i].u],t[e[i].v]);
    std::sort(e+1,e+m+1,comp);
    now=n;
    for(int i=0,j=1;i<=k;i++){
        while(e[j].time<=i&&j<=m){
            a=find(e[j].u),b=find(e[j].v);
            if(a!=b){
                f[a]=b;
                now--;
            }
            j++;
        }
        ans[k-i]=now-k+i;
    }
    for(int i=0;i<=k;i++) printf("%d\n",ans[i]);
    return 0;
}
··· 求神犇解惑、

回复

4 条回复,欢迎继续交流。

正在加载回复...