#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[0][(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[j][(b-d[j].first)%cycle[d[j].second]]]++;
}
}
}
}
rep(i,n){
printf("%d\n",ans[i]);
}
}
Compilation message
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 time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
