比赛 2024暑假C班集训E 评测结果 AAAAAAAAAA
题目名称 灾难 最终得分 100
用户昵称 小金 运行时间 0.199 s
代码语言 C++ 内存使用 6.00 MiB
提交时间 2024-07-14 11:34:09
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=656000,maxm=1000010;
struct edge{
    int to,next;
}e[maxm];
int n,x,op,path[maxn],tot,in[maxn],size[maxn],q[maxn],head,tail,d[maxn],fa[maxn][20];
void tp()
{
    head=1;
    tail=1;
    for(int i=1;i<=n;i++)
    {
        if(!in[i]) q[tail++]=i;
    }
    while(head<tail)
    {
        int x=q[head++];
        for(int i=path[x];i;i=e[i].next)
        {
            in[e[i].to]--;
            if(!in[e[i].to]) q[tail++]=e[i].to;
        }
    }
}
void add(int x,int y)
{
    e[++tot].to=y;
    e[tot].next=path[x];
    path[x]=tot;
}
int lca(int x,int y)
{
    if(d[x]<d[y]) swap(x,y);
    for(int i=op;i>=0;i--)
    { 
        if(d[fa[x][i]]>=d[y]) x=fa[x][i];
    } 
    if(x==y) return x;
    for(int i=op;i>=0;i--)
    {
        if(fa[x][i]!=fa[y][i])
        {
            x=fa[x][i];
            y=fa[y][i];
        } 
    } 
    return fa[x][0];
}
int main()
{
    freopen("catas.in","r",stdin);
    freopen("catas.out","w",stdout);
    scanf("%d",&n);
    op=log2(n);
    int a;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        if(!a) add(i,0);
        while(a)
        {
            add(i,a);
            in[a]++;
            scanf("%d",&a);
        }
    }
    tp();
    for(int i=n;i>=1;i--)
    {
        int x=q[i],t=e[path[x]].to;
        for(int j=e[path[x]].next;j;j=e[j].next)
        {
            t=lca(t,e[j].to);
        }
        fa[x][0]=t;
        d[x]=d[t]+1;
        for(int t=1;t<=op;t++)
        {
            fa[x][t]=fa[fa[x][t-1]][t-1];
        }
    }
    for(int i=1;i<=n;i++)
    {
        size[q[i]]++;
        size[fa[q[i]][0]]+=size[q[i]];
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d\n",size[i]-1);
    }
    return 0;
}