WA+TLE求助(带注释)

P1197 [JSOI2008] 星球大战

取啥名好 @ 2019-10-24 18:59:18

#include<bits/stdc++.h>
using namespace std;
int n,m,k,tx,ty,cnt=0;
int jl[2000001]={0},mark[2000001]={0},fa[2000001]={0},ans[2000001]={0};
struct node{
    int x,y;
}temp;
queue<node> q,qt,qk;
inline int r(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||'9'<c) c=getchar();
    while('0'<=c&&c<='9')   x=x*10+c-48,c=getchar();
    return x*f;
}
inline int find(int x){
    if(fa[x]==x)    return x;
    return fa[x]=find(fa[x]);
}
int main(){
    n=r(),m=r();
    for(int i=0;i<n;i++)    fa[i]=i;
    for(int i=1;i<=m;i++)temp.x=r(),temp.y=r(),q.push(temp);//存边到队列里 
    k=r();cnt=n-k;//现在的连通块数是全部的减去毁掉的 
    for(int i=1;i<=k;i++)   jl[i]=r(),mark[jl[i]]=1;//毁掉的标记一下 
    for(int i=k;i>=1;i--){
        while(!q.empty()){
            temp=q.front();
            qt.push(temp);//放到另一个队列里, 
            q.pop();
            if(!mark[temp.x]&&!mark[temp.y]){//如果可以连 
                tx=find(temp.x),ty=find(temp.y);
                if(tx!=ty){
                    fa[tx]=ty;
                    cnt--;//联通一个,所以连通块少一个 
                }
                qt.pop();//把用掉的或没用的扔了,只留下现在用不了的 
            }
        }
        q=qt;//把没用过的放进去 
        qt=qk;//把这个清空 
        ans[i]=cnt;//记录答案 
        cnt++;//新建一个 
        mark[jl[i]]=0;//改成完好的 
    }
    for(int i=1;i<=k;i++)   cout<<ans[i]<<endl;
    return 0;
}

by 取啥名好 @ 2019-10-24 18:59:34

已开大数组,不是数组问题


by Raging零 @ 2019-11-01 10:07:44

注意看题目,首先输出刚开始时联通快的数目
第一行是开始时星球的连通块个数。 接下来的 K 行,每行一个整数,表示经过该次打击后现存星球的连通块个数。


|