比赛 |
2024暑假C班集训E |
评测结果 |
EEEEEEEEEW |
题目名称 |
灾难 |
最终得分 |
0 |
用户昵称 |
袁书杰 |
运行时间 |
1.980 s |
代码语言 |
C++ |
内存使用 |
5.69 MiB |
提交时间 |
2024-07-14 11:59:22 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int n,ans;
struct edge {
int u,v,nxt;
} e[1000005],e1[1000005];
int etot,head[1000005],etot1,head1[1000005],deep[1000005],ancester[20][500005],in[500005],dad[500005],size[500005];
void adde(int u,int v) {
e[++etot]= {u,v,head[u]};
head[u]=etot;
}
void adde1(int u,int v) {
e1[++etot]= {u,v,head1[u]};
head1[u]=etot1;
}
int lca(int x,int y) {
if(x==y){
return x;
}
if(deep[x]<deep[y]) {
swap(x,y);
}
for(int i=18; i>=0; i--) {
if(deep[ancester[x][i]]>=deep[y]) {
x=ancester[x][i];
}
}
if(x==y) {
return x;
}
for(int i=18; i>=0; i--) {
if(ancester[x][i]!=ancester[y][i]){
x=ancester[x][i];
y=ancester[y][i];
}
}
return ancester[x][0];
}
void dfs(int u) {
size[u]=1;
for (long long i = head1[u]; i; i = e1[i].nxt) {
long long v = e1[i].v;
dfs(v);
size[u]+=size[v];
}
}
void toposort() {
queue<int> S;
for (int i = 1; i <= n; i++)
if (in[i] == 0) S.push(i),dad[i]=0;
while (!S.empty()) {
int u = S.front();
S.pop();
adde1(dad[u],u);
ancester[u][0]=dad[u];
deep[u]=deep[dad[u]]+1;
for(int i=1; i<=20; i++) {
ancester[u][i]=ancester[ancester[u][i-1]][i-1];
}
for (long long j = head[u]; j; j = e[j].nxt) {
long long v = e[j].v;
if(dad[v]==-1) {
dad[v]=u;
} else {
dad[v]=lca(dad[v],u);
}
if(--in[v]==0){
S.push(v);
}
}
}
}
int main() {
freopen("catas.in","r",stdin);
freopen("catas.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
for(int i=1; i<=500000; i++) {
dad[i]=-1;
}
cin>>n;
for(int i=1; i<=n; i++) {
int x;
while(cin>>x,x!=0) {
adde(x,i);
in[i]++;
}
}
toposort();
dfs(1);
for(int i=1; i<=n; i++) {
cout<<size[i]-1<<endl;
}
return 0;
}