比赛 |
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;
}