Guest User

Untitled

a guest
Nov 15th, 2017
242
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.93 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[5100],ansq[5100],tt;
  6. map<int,int>qno;
  7. vector<int>path;
  8. void dfs(int cn)
  9. {
  10.     if(dis[cn]!=-1 || !cn) return void(dis[cn]=0);
  11.     dis[cn]=0;
  12.     path.pb(cn),dfs(edge[cn]);
  13.     dis[cn]=dis[edge[cn]]+1,dat[dis[cn]]=cn;
  14. }
  15. void up(int pos,int val)
  16. {
  17.     int rpos=n-pos+1;
  18.     if(qno.find(rpos)==qno.end()) return;
  19.     ansq[qno[rpos]]=val;
  20. }
  21. int main()
  22. {
  23.     scanf("%d %d %d",&n,&m,&q);
  24.     for(int i=1; i<=m; i++)
  25.     {
  26.         scanf("%d",&tt);
  27.         edge[i]=tt-1;
  28.         indeg[tt-1]++;
  29.     }
  30.     for(int i=1; i<=q; i++)
  31.     {
  32.         scanf("%d",&p[i]);
  33.         qno[p[i]]=i;
  34.     }
  35.     memset(dis,-1,sizeof(dis)),memset(ansq,-1,sizeof(ansq));
  36.     for(int i=1; i<=m; i++) if(indeg[i]==0) dfs(i);
  37.     int mxmove=n-m+1;
  38.     for(int i=1; i<=m; i++)
  39.         if(dis[i]!=-1)
  40.         {
  41.             if(dis[i]<=mxmove) up(dis[i],i);//ans[dis[i]]=i;
  42.             else up(dat[dis[i]-mxmove]+n-m+1,i);//ans[dat[dis[i]-mxmove]+n-m+1]=i;
  43.         }
  44.     for(int i=max(m+1,n-m); i<=n; i++)
  45.     {
  46.         mxmove=n-i+1;
  47.         if(dis[m]<=mxmove) up(dis[m]+i-m,i);//ans[dis[m]+i-m]=i;
  48.         else up(dat[dis[m]-mxmove]+n-m+1,i);//ans[dat[dis[m]-mxmove]+n-m+1]=i;
  49.     }
  50.     mxmove=n-m+1;
  51.     for(int i=1; i<=m; i++)
  52.     {
  53.         if(dis[i]==-1)
  54.         {
  55.             path.clear(),dfs(i);
  56.             for(int j=0; j<path.size(); j++)
  57.             {
  58.                 int cur=path[j],fnodes=path.size()-j-1;
  59.                 if(fnodes>=mxmove) up(path[j+mxmove]+n-m+1,cur);//ans[path[j+mxmove]+n-m+1]=cur;
  60.                 else up(path[(mxmove-fnodes-1)%path.size()]+n-m+1,cur);//ans[path[(mxmove-fnodes-1)%path.size()]+n-m+1]=cur;
  61.             }
  62.         }
  63.     }
  64.  
  65.     for(int i=1; i<=q; i++)
  66.     {
  67.         if(ansq[i]==-1) ansq[i]=(n-p[i]+1)+m-dis[m];
  68.         printf("%d\n",ansq[i]);
  69.     }
  70. }
Add Comment
Please, Sign In to add comment