Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define pb push_back
- using namespace std;
- const int maxN = 100010;
- int n,m,q,indeg[maxN],dis[maxN],edge[maxN],dat[maxN],p,ans[maxN];
- vector<int>path;
- void dfs(int cn)
- {
- if(dis[cn]!=-1 || !cn) return void(dis[cn]=0);
- dis[cn]=0;
- path.pb(cn),dfs(edge[cn]);
- dis[cn]=dis[edge[cn]]+1,dat[dis[cn]]=cn;
- }
- int main()
- {
- scanf("%d %d %d",&n,&m,&q);
- for(int i=1;i<=m;i++)
- {
- scanf("%d",&p);
- edge[i]=p-1;
- indeg[p-1]++;
- }
- memset(dis,-1,sizeof(dis));
- for(int i=1;i<=m;i++) if(indeg[i]==0) dfs(i);
- int mxmove=n-m+1;
- for(int i=1;i<=m;i++)
- if(dis[i]!=-1)
- {
- if(dis[i]<=mxmove) ans[dis[i]]=i;
- else ans[dat[dis[i]-mxmove]+n-m+1]=i;
- }
- for(int i=m+1;i<=n;i++)
- {
- mxmove=n-i+1;
- if(dis[m]<=mxmove) ans[dis[m]+i-m]=i;
- else ans[dat[dis[m]-mxmove]+n-m+1]=i;
- }
- mxmove=n-m+1;
- for(int i=1;i<=m;i++)
- {
- if(dis[i]==-1)
- {
- path.clear(),dfs(i);
- for(int j=0;j<path.size();j++)
- {
- int cur=path[j],fnodes=path.size()-j-1;
- if(fnodes>=mxmove) ans[path[j+mxmove]+n-m+1]=cur;
- else ans[path[(mxmove-fnodes-1)%path.size()]+n-m+1]=cur;
- }
- }
- }
- reverse(ans+1,ans+1+n);
- for(int i=1;i<=q;i++)
- {
- scanf("%d",&p);
- printf("%d\n",ans[p]);
- }
- }
Add Comment
Please, Sign In to add comment