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