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