#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxN = (int)3e3+10;
const int mxLg = 60;
const int LINF = (int)1e18+10;
int n, k, p[mxN], ans[mxN];
int dis[mxN][mxN], jmp[mxLg][mxN];
int getPath(int x, int k){
for(int i = 0; i<mxLg; i++)
if((k>>i)&1) x = jmp[i][x];
return x;
}
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> p[i], jmp[0][i]=p[i];
for(int i = 1; i < mxLg; i++)
for(int j = 1; j <= n; j++)
jmp[i][j] = jmp[i-1][jmp[i-1][j]];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
dis[i][j] = LINF;
for(int i = 1; i <= n; i++)
for(int j = 0; j <= n; j++)
if(dis[i][getPath(i,j)]==LINF)
dis[i][getPath(i,j)]=j;
int def = getPath(1,k);
for(int a = 1; a <= n; a++){
for(int b = 1; b <= n; b++){
if(dis[1][a]>=k) ans[def]++;
else{
int xd = k-dis[1][a]-1, cyc;
if(dis[b][a]>=k) ans[getPath(b,xd)]++;
else cyc = dis[b][a]+1, ans[getPath(b,xd%cyc)]++;
}
}
}
for(int i = 1; i <= n; i++) cout << ans[i] << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
980 KB |
Output is correct |
| 2 |
Correct |
2 ms |
980 KB |
Output is correct |
| 3 |
Correct |
1 ms |
980 KB |
Output is correct |
| 4 |
Correct |
3 ms |
980 KB |
Output is correct |
| 5 |
Correct |
2 ms |
980 KB |
Output is correct |
| 6 |
Correct |
4 ms |
980 KB |
Output is correct |
| 7 |
Correct |
3 ms |
980 KB |
Output is correct |
| 8 |
Correct |
3 ms |
980 KB |
Output is correct |
| 9 |
Correct |
4 ms |
980 KB |
Output is correct |
| 10 |
Correct |
3 ms |
980 KB |
Output is correct |
| 11 |
Correct |
2 ms |
980 KB |
Output is correct |
| 12 |
Correct |
4 ms |
980 KB |
Output is correct |
| 13 |
Correct |
2 ms |
980 KB |
Output is correct |
| 14 |
Correct |
2 ms |
980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
980 KB |
Output is correct |
| 2 |
Correct |
2 ms |
980 KB |
Output is correct |
| 3 |
Correct |
1 ms |
980 KB |
Output is correct |
| 4 |
Correct |
3 ms |
980 KB |
Output is correct |
| 5 |
Correct |
2 ms |
980 KB |
Output is correct |
| 6 |
Correct |
4 ms |
980 KB |
Output is correct |
| 7 |
Correct |
3 ms |
980 KB |
Output is correct |
| 8 |
Correct |
3 ms |
980 KB |
Output is correct |
| 9 |
Correct |
4 ms |
980 KB |
Output is correct |
| 10 |
Correct |
3 ms |
980 KB |
Output is correct |
| 11 |
Correct |
2 ms |
980 KB |
Output is correct |
| 12 |
Correct |
4 ms |
980 KB |
Output is correct |
| 13 |
Correct |
2 ms |
980 KB |
Output is correct |
| 14 |
Correct |
2 ms |
980 KB |
Output is correct |
| 15 |
Correct |
942 ms |
72432 KB |
Output is correct |
| 16 |
Correct |
901 ms |
72524 KB |
Output is correct |
| 17 |
Correct |
1018 ms |
72432 KB |
Output is correct |
| 18 |
Execution timed out |
2058 ms |
72416 KB |
Time limit exceeded |
| 19 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
980 KB |
Output is correct |
| 2 |
Correct |
2 ms |
980 KB |
Output is correct |
| 3 |
Correct |
1 ms |
980 KB |
Output is correct |
| 4 |
Correct |
3 ms |
980 KB |
Output is correct |
| 5 |
Correct |
2 ms |
980 KB |
Output is correct |
| 6 |
Correct |
4 ms |
980 KB |
Output is correct |
| 7 |
Correct |
3 ms |
980 KB |
Output is correct |
| 8 |
Correct |
3 ms |
980 KB |
Output is correct |
| 9 |
Correct |
4 ms |
980 KB |
Output is correct |
| 10 |
Correct |
3 ms |
980 KB |
Output is correct |
| 11 |
Correct |
2 ms |
980 KB |
Output is correct |
| 12 |
Correct |
4 ms |
980 KB |
Output is correct |
| 13 |
Correct |
2 ms |
980 KB |
Output is correct |
| 14 |
Correct |
2 ms |
980 KB |
Output is correct |
| 15 |
Correct |
942 ms |
72432 KB |
Output is correct |
| 16 |
Correct |
901 ms |
72524 KB |
Output is correct |
| 17 |
Correct |
1018 ms |
72432 KB |
Output is correct |
| 18 |
Execution timed out |
2058 ms |
72416 KB |
Time limit exceeded |
| 19 |
Halted |
0 ms |
0 KB |
- |
