Submission #110808

#TimeUsernameProblemLanguageResultExecution timeMemory
110808autumn_eelSpace Pirate (JOI14_space_pirate)C++14
0 / 100
5 ms896 KiB
#include <bits/stdc++.h> #define rep(i,n)for(int i=0;i<(n);i++) using namespace std; typedef pair<int,int>P; typedef long long ll; vector<int>E[3100]; int a[3100]; int ans[3100]; int vis[3100]; int cycle[3100]; P d[3100]; int d1[3100]; int dist[3100]; int id[3100][3100]; int cnt=0; void dfs(int v){ vis[v]=cnt; if(vis[a[v]]!=-1){ if(cycle[a[v]])return; cycle[a[v]]=cnt+1-vis[a[v]]; } cnt++; dfs(a[v]); } void bfs(queue<int>&que,int d[]){ while(!que.empty()){ int p=que.front();que.pop(); for(int u:E[p]){ if(d[u]==-1){ d[u]=d[p]+1; que.push(u); } } } } int main(){ int n;ll K;cin>>n>>K; if(n>3000)abort(); rep(i,n){ scanf("%d",&a[i]);a[i]--; E[a[i]].push_back(i); } rep(i,n){ int x=i; rep(j,n+1){ id[i][j]=x; x=a[x]; } } memset(vis,-1,sizeof(vis)); rep(i,n){ if(vis[i]==-1){ dfs(i); } } queue<int>que; rep(i,n)d[i]=P(-1,i); rep(i,n){ if(cycle[i]){ d[i]=P(0,i); que.push(i); } } while(!que.empty()){ int p=que.front();que.pop(); for(int u:E[p]){ if(d[u].first==-1){ d[u]=P(d[p].first+1,d[p].second); que.push(u); } } } memset(d1,-1,sizeof(d1)); int x=0; d1[0]=0; while(1){ if(d1[a[x]]!=-1)break; d1[a[x]]=d1[x]+1; x=a[x]; } rep(i,n){ if(d1[i]>=K||d1[i]==-1){ if(K<d[0].first)ans[id[0][K]]+=n; else{ ans[id[d[0].second][(K-d[0].first)%cycle[d[0].second]]]+=n; } continue; } memset(dist,-1,sizeof(dist)); dist[i]=0; que.push(i); bfs(que,dist); ll b=K-d1[i]; rep(j,n){ if(dist[j]!=-1){ int cy=dist[j]+1; if(b%cy==0){ ans[i]++; } else ans[id[j][b%cy-1]]++; } else{ if(b<d[j].first)ans[id[j][b-1]]++; else{ ans[id[d[j].second][(b-d[j].first)%cycle[d[j].second]]]++; } } } } rep(i,n){ printf("%d\n",ans[i]); } }

Compilation message (stderr)

space_pirate.cpp: In function 'int main()':
space_pirate.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);a[i]--;
   ~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...