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[5100],ansq[5100],tt;
- map<int,int>qno;
- 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;
- }
- void up(int pos,int val)
- {
- int rpos=n-pos+1;
- if(qno.find(rpos)==qno.end()) return;
- ansq[qno[rpos]]=val;
- }
- int main()
- {
- scanf("%d %d %d",&n,&m,&q);
- for(int i=1; i<=m; i++)
- {
- scanf("%d",&tt);
- edge[i]=tt-1;
- indeg[tt-1]++;
- }
- for(int i=1; i<=q; i++)
- {
- scanf("%d",&p[i]);
- qno[p[i]]=i;
- }
- memset(dis,-1,sizeof(dis)),memset(ansq,-1,sizeof(ansq));
- 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) up(dis[i],i);//ans[dis[i]]=i;
- else up(dat[dis[i]-mxmove]+n-m+1,i);//ans[dat[dis[i]-mxmove]+n-m+1]=i;
- }
- for(int i=max(m+1,n-m); i<=n; i++)
- {
- mxmove=n-i+1;
- if(dis[m]<=mxmove) up(dis[m]+i-m,i);//ans[dis[m]+i-m]=i;
- else up(dat[dis[m]-mxmove]+n-m+1,i);//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) up(path[j+mxmove]+n-m+1,cur);//ans[path[j+mxmove]+n-m+1]=cur;
- else up(path[(mxmove-fnodes-1)%path.size()]+n-m+1,cur);//ans[path[(mxmove-fnodes-1)%path.size()]+n-m+1]=cur;
- }
- }
- }
- for(int i=1; i<=q; i++)
- {
- if(ansq[i]==-1) ansq[i]=(n-p[i]+1)+m-dis[m];
- printf("%d\n",ansq[i]);
- }
- }
Add Comment
Please, Sign In to add comment