样例没过求调(悬赏2关注)
查看原帖
样例没过求调(悬赏2关注)
616996
Graph楼主2023/7/30 22:00

rt

#include<bits/stdc++.h>
using namespace std;

__inline__ __attribute__((always_inline)) int read()
{
	char ch=getchar();
	int f=1,x=0;
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch))x=x*10+(ch-'0'),ch=getchar();
	return x*f;
}

inline void _write(int x)
{
	if(x>9)_write(x/10);
	putchar((x%10)+'0');
}

__inline__ __attribute__((always_inline)) void write(int x)
{
	if(x<0)putchar('-'),x=-x;
	_write(x);
}

const int N=70000;
int n=read();
vector<int>nbr[N],fa[N],topo_ans,ans[N];
int deep[N],dp[N][105],big[N],lg[N],in[N];

void dfs(int cur,int fa)
{
	deep[cur]=deep[fa]+1;
	dp[cur][0]=fa;
	for(int i=1;(1<<i)<=deep[cur];i++)
		dp[cur][i]=dp[dp[cur][i-1]][i-1];
	for(int i=0;i<nbr[cur].size();i++)
	{
		int nxt=nbr[cur][i];
		if(nxt!=fa)
			dfs(nxt,cur);
	}
	return ;
}

int lca(int x,int y)
{
	if(deep[x]<deep[y])
		swap(x,y);
	while(deep[x]>deep[y])
		x=dp[x][lg[deep[x]-deep[y]]];
	if(x==y)
		return x;
	for(int i=lg[deep[x]];i>=0;i--)
		if(dp[x][i]!=dp[y][i])
		{
			x=dp[x][i];
			y=dp[y][i];
		}
	return dp[x][0];
}

void topo_sort()
{
	queue<int>q;
	for(int i=1;i<=n;i++)
		if(in[i]==0)
			q.push(i);
	while(q.empty()==false)
	{
		int cur=q.front();
		q.pop();
		for(int i=0;i<nbr[cur].size();i++)
		{
			int nxt=nbr[cur][i];
			in[nxt]--;
			if(in[nxt]==0)
				q.push(nxt);
		}
		topo_ans.push_back(cur);
	}
	return ;
}

void dfs_ans(int cur)
{
	big[cur]=1;
	for(int i=0;i<ans[cur].size();i++)
	{
		int nxt=ans[cur][i];
		dfs_ans(nxt);
		big[cur]+=big[nxt];
	}
	return ;
}

signed main()
{
	lg[0]=-1;
	for(int i=1;i<=n;i++)
	{
		lg[i]=lg[i/2]+1;
		int x=read();
		while(x!=0)
		{
			nbr[x].push_back(i);
			in[i]++;
			fa[i].push_back(x);
			x=read();
		}
		nbr[0].push_back(i);
	}
	topo_sort();
	dfs(0,n+1);
	for(int i=0;i<topo_ans.size();i++)
	{
		int cur=topo_ans[i],tmp;
		if(fa[cur].size()==0)
		{
			ans[0].push_back(cur);
			continue;
		}
		tmp=fa[cur][0];
		for(int j=1;j<fa[cur].size();j++)
			tmp=lca(tmp,fa[cur][j]);
		ans[tmp].push_back(cur);
	}
	dfs_ans(0);
	for(int i=1;i<=n;i++)
		write(big[i]-1),puts("");
	return 0;
}
2023/7/30 22:00
加载中...