社区讨论
我被犇站卡了!!!
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 条回复,欢迎继续交流。
正在加载回复...