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