# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
497992 | 600Mihnea | Space Pirate (JOI14_space_pirate) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int) 1e5 + 7;
int n;
int nxt[N];
bool vis[N];
ll solution[N];
ll k;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
//freopen ("input", "r", stdin);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> nxt[i];
}
for (int a = 1; a <= n; a++) {
int init = nxt[a];
for (int b = 1; b <= n; b++) {
for (int i = 1; i <= n; i++) {
vis[i] = 0;
}
vector<int> path, cycle;
nxt[a] = b;
int c = solve();
int current = 1;
ll need = 0;
for (ll step = 1; step <= k; step++) {
if (!vis[current]) {
vis[current] = 1;
path.push_back(current);
} else {
need = k - step + 1;
assert(need > 0);
bool has = 0;
for (auto &x : path) {
if (x == current) {
has = 1;
}
if (has) {
cycle.push_back(x);
}
}
break;
}
current = nxt[current];
}
/**
1 2 3
**/
if (need) {
need %= (int) cycle.size();
for (int step = 1; step <= need; step++) {
current = nxt[current];
}
}
solution[current]++;
}
nxt[a] = init;
}
for (int i = 1; i <= n; i++) {
cout << solution[i] << "\n";
}
return 0;
}