#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define forr(i,a,b,c) for(int i=a;i<b;i+=c)
#define fort(i,a,b) forr(i,a,b,1)
#define forn(i,n) fort(i,1,n)
#define fori(i,n) fort(i,0,n)
#define forrb(i,a,b,c) for(int i=b-1;i>=a;i-=c)
#define fortb(i,a,b) forrb(i,a,b,1)
#define fornb(i,n) fortb(i,1,n)
#define forib(i,n) fortb(i,0,n)
using namespace std;
#define into(x) cin >> x;
typedef vector<int> veci;
typedef long long lol;
typedef pair<lol,lol> point;
#define def(x) lol x; into(x)
#define logn 60
int main() {
ios::sync_with_stdio();
def(n) def(m)
veci a(n);
vector<veci> x(n, veci(n+1));
vector<veci> y(n, veci(n,-1));
vector<veci> f(logn, veci(n));
fori(i, n) {
into(a[i])
a[i]--;
}
fori(i, n) {
x[i][0]=i;
int cur = a[i];
forn(j, n+1) {
x[i][j] = cur;
if (y[i][cur] != -1) {
break;
}
y[i][cur] = j;
cur = a[cur];
}
f[0][i] = a[i];
}
forn(i, logn) {
fori(j, n) {
f[i][j] = f[i-1][f[i-1][j]];
}
}
int norm = 0;
lol mm = m;
fori(k, logn) {
if (mm % 2 == 1) {
norm = f[k][norm];
}
mm /= 2;
}
veci b(n);
fori(i, n) {
lol mm = m - y[0][i] - 1;
if (i == 0) {
mm = m-1;
}else if (y[0][i] == -1) {
b[norm] += n;
continue;
}
fori(j, n) {
if (j == i) {
b[i]++;
} else
if (y[j][i] == -1) {
int ans = j;
fori(k, logn) {
if (mm&((lol)1<<k)) {
ans = f[k][ans];
}
}
b[ans]++;
}else {
b[x[j][mm % (y[j][i]+1)]]++;
}
}
}
fori(i, n) {
cout << b[i] << endl;
}
return 0 ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
512 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
512 KB |
Output is correct |
| 6 |
Correct |
5 ms |
512 KB |
Output is correct |
| 7 |
Correct |
6 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
512 KB |
Output is correct |
| 13 |
Correct |
5 ms |
384 KB |
Output is correct |
| 14 |
Correct |
5 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
512 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
512 KB |
Output is correct |
| 6 |
Correct |
5 ms |
512 KB |
Output is correct |
| 7 |
Correct |
6 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
512 KB |
Output is correct |
| 13 |
Correct |
5 ms |
384 KB |
Output is correct |
| 14 |
Correct |
5 ms |
512 KB |
Output is correct |
| 15 |
Correct |
93 ms |
71672 KB |
Output is correct |
| 16 |
Correct |
51 ms |
71736 KB |
Output is correct |
| 17 |
Correct |
103 ms |
71800 KB |
Output is correct |
| 18 |
Correct |
1594 ms |
71800 KB |
Output is correct |
| 19 |
Correct |
1163 ms |
71800 KB |
Output is correct |
| 20 |
Correct |
684 ms |
71800 KB |
Output is correct |
| 21 |
Execution timed out |
2091 ms |
71672 KB |
Time limit exceeded |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
286 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
512 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
512 KB |
Output is correct |
| 6 |
Correct |
5 ms |
512 KB |
Output is correct |
| 7 |
Correct |
6 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
512 KB |
Output is correct |
| 13 |
Correct |
5 ms |
384 KB |
Output is correct |
| 14 |
Correct |
5 ms |
512 KB |
Output is correct |
| 15 |
Correct |
93 ms |
71672 KB |
Output is correct |
| 16 |
Correct |
51 ms |
71736 KB |
Output is correct |
| 17 |
Correct |
103 ms |
71800 KB |
Output is correct |
| 18 |
Correct |
1594 ms |
71800 KB |
Output is correct |
| 19 |
Correct |
1163 ms |
71800 KB |
Output is correct |
| 20 |
Correct |
684 ms |
71800 KB |
Output is correct |
| 21 |
Execution timed out |
2091 ms |
71672 KB |
Time limit exceeded |
| 22 |
Halted |
0 ms |
0 KB |
- |
