比赛 2026.3.14 评测结果 AWWWWWWWWWWWWWWWWWWW
题目名称 The Chase 最终得分 5
用户昵称 PXCZM 运行时间 2.727 s
代码语言 C++ 内存使用 32.63 MiB
提交时间 2026-03-14 12:09:39
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[500010];
int b[500010],c[500010],d[500010],e[500010];
int f[500010];
int z[500010][20];
bool r[500010],r1[500010],vis[500010];
int w[500010];
int ans[500010];
int find(int x)
{
	if(f[x]==x) return x;
	else return f[x]=find(f[x]);
}
int dfs1(int rt,int cnt,int p)
{
	if(rt==p)
	{
		b[rt]=cnt;
		return cnt;
	}
	b[rt]=dfs1(a[rt],cnt+1,p);
	return b[rt];
}
int dfs2(int rt)
{
	if(b[rt]) return 1;
	if(c[rt]) return c[rt]+1;
	else c[rt]=dfs2(a[rt]);
	return c[rt]+1;
}
int dfs3(int rt)
{
	if(b[rt]) return rt;
	if(d[rt]) return d[rt];
	else d[rt]=dfs3(a[rt]);
	return d[rt];
}
int solve(int x,int y)
{
	for(int i=18;i>=0;i--)
		if(y>>i)
			x=z[x][i];
	return x;
}
int main()
{
	freopen("Chase.in","r",stdin);
	freopen("Chase.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	cin>>n>>m;
	for(int i=1;i<=n;i++) ans[i]=-2;
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		int u=find(i),v=find(a[i]);
		if(u!=v) f[u]=v;
		else dfs1(a[i],1,i);
	}
	for(int i=1;i<=n;i++)
		if(b[i]) z[a[i]][0]=i;
	for(int i=1;i<=18;i++)
		for(int j=1;j<=n;j++)
		{
			if(!b[i]) continue;
			z[j][i]=z[z[j][i-1]][i-1];
		}
	for(int i=1;i<=n;i++)
		if(!b[i]&&!c[i]) dfs2(i);
	for(int i=1;i<=n;i++)
		if(c[i]&&!d[i]) dfs3(i);
	for(int i=1;i<=m;i++)
	{
		cin>>w[i];
		r[w[i]]=1;
		ans[w[i]]=-1;
		if(c[w[i]])
		{
			int tmp=solve(d[w[i]],c[w[i]]);
			r1[tmp]=1;
			e[w[i]]=tmp;
		}
	}
	for(int i=1;i<=m;i++)
	{
		if(b[w[i]])
		{
			if(vis[w[i]]) continue;
			vis[w[i]]=1;
			for(int i=1,j=a[w[i]],k=0;i<b[w[i]];i++,j=a[j])
			{
				if(vis[j]) continue;
				vis[j]=1;
				if(r[j]||r1[j])
				{
					ans[j]=-1;
					k=0;
				}
				else ans[j]=k++;
			}
		}
	}
	for(int i=1;i<=m;i++)
	{
		if(c[w[i]])
		{
			if(vis[w[i]]) continue;
			vis[w[i]]=1;
			for(int i=1,j=a[w[i]],jj=a[e[w[i]]],k=0;i<c[w[i]];i++,j=a[j],jj=a[jj])
			{
				if(vis[j]) continue;
				vis[j]=1;
				if(r[jj]||r1[jj])
				{
					ans[j]=-1;
					k=0;
				}
				else ans[j]=k++;
			}
		}
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';
	return 0;
}