Guest User

Untitled

a guest
Nov 15th, 2017
208
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.46 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define pb push_back
  3. using namespace std;
  4. const int maxN = 100010;
  5. int n,m,q,indeg[maxN],dis[maxN],edge[maxN],dat[maxN],p,ans[maxN];
  6. vector<int>path;
  7. void dfs(int cn)
  8. {
  9.     if(dis[cn]!=-1 || !cn) return void(dis[cn]=0);
  10.     dis[cn]=0;
  11.     path.pb(cn),dfs(edge[cn]);
  12.     dis[cn]=dis[edge[cn]]+1,dat[dis[cn]]=cn;
  13. }
  14. int main()
  15. {
  16.     scanf("%d %d %d",&n,&m,&q);
  17.     for(int i=1;i<=m;i++)
  18.     {
  19.         scanf("%d",&p);
  20.         edge[i]=p-1;
  21.         indeg[p-1]++;
  22.     }
  23.     memset(dis,-1,sizeof(dis));
  24.     for(int i=1;i<=m;i++) if(indeg[i]==0) dfs(i);
  25.     int mxmove=n-m+1;
  26.     for(int i=1;i<=m;i++)
  27.         if(dis[i]!=-1)
  28.         {
  29.            if(dis[i]<=mxmove) ans[dis[i]]=i;
  30.            else ans[dat[dis[i]-mxmove]+n-m+1]=i;
  31.         }
  32.     for(int i=m+1;i<=n;i++)
  33.     {
  34.         mxmove=n-i+1;
  35.         if(dis[m]<=mxmove) ans[dis[m]+i-m]=i;
  36.            else ans[dat[dis[m]-mxmove]+n-m+1]=i;
  37.     }
  38.     mxmove=n-m+1;
  39.     for(int i=1;i<=m;i++)
  40.     {
  41.         if(dis[i]==-1)
  42.         {
  43.             path.clear(),dfs(i);
  44.             for(int j=0;j<path.size();j++)
  45.             {
  46.                 int cur=path[j],fnodes=path.size()-j-1;
  47.                 if(fnodes>=mxmove) ans[path[j+mxmove]+n-m+1]=cur;
  48.                 else ans[path[(mxmove-fnodes-1)%path.size()]+n-m+1]=cur;
  49.             }
  50.         }
  51.     }
  52.     reverse(ans+1,ans+1+n);
  53.     for(int i=1;i<=q;i++)
  54.     {
  55.         scanf("%d",&p);
  56.         printf("%d\n",ans[p]);
  57.     }
  58. }
Add Comment
Please, Sign In to add comment