比赛 2024暑假C班集训E 评测结果 AAAAAAAAAA
题目名称 灾难 最终得分 100
用户昵称 flyfree 运行时间 0.806 s
代码语言 C++ 内存使用 11.21 MiB
提交时间 2024-07-14 11:34:11
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
//#define ll long long
#define MAXN 200010
int n,idx,num,x;
int cnt[MAXN],topsort[MAXN];
int p[MAXN][50],dep[MAXN];
int hd[MAXN],nxt[MAXN],ed[MAXN],siz[MAXN];
vector <int> s[100010];
queue <int> q;
void build(int x,int y){
    nxt[++idx]=hd[x];
    hd[x]=idx;
    ed[idx]=y;
}
void qs_p(int idx){
    dep[idx]=dep[p[idx][0]]+1;
    for(int i=1;i<=20;i++){
        p[idx][i]=p[p[idx][i-1]][i-1];
    }
}
int lca(int x,int y){
    if(dep[y]>dep[x])swap(x,y);
    for(int i=20;i>=0;i--){
        if(dep[p[x][i]]>=dep[y])x=p[x][i];
    }
    if(x==y)return x;
    for(int i=20;i>=0;i--){
        if(p[x][i]!=p[y][i]){
            x=p[x][i];
            y=p[y][i];
        }
    }
    return p[x][0];
}
int main(){
    freopen("catas.in","r",stdin);
    freopen("catas.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        while(cin>>x){
            if(x==0)break;
            build(x,i);
            s[i].push_back(x);
            cnt[i]++;
        }
        if(!cnt[i])q.push(i);
    }
    while(!q.empty()){
        int fst=q.front();
//        cout<<fst;
        topsort[++num]=fst;
        q.pop();
        for(int i=hd[fst];i;i=nxt[i]){
            int y=ed[i];
            cnt[y]--;
            if(!cnt[y])q.push(y);
        }
    }
//    cout<<endl;
    for(int z=1;z<=num;z++){
        int i=topsort[z];
//        cout<<s[i].size();
        if(!s[i].size()){
            dep[i]=1;
            continue;
        } 
        if(s[i].size()==1)p[i][0]=s[i][0];
        else{
            int pz=lca(s[i][0],s[i][1]);
            for(int j=2;j<s[i].size();j++){
//                cout<<pz<<endl;
                pz=lca(pz,s[i][j]);
            }
            p[i][0]=pz;
        }
//        cout<<p[i][0]<<endl;
        qs_p(i);
    }
    for(int z=num;z;z--){
        int i=topsort[z];
        siz[p[i][0]]+=siz[i]+1;
    }
    for(int i=1;i<=n;i++)cout<<siz[i]<<endl;
    return 0; 
}