#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
const int N = 100001;
vector<int> g[N], cl, l1;
ll a[N], pos[N], used[N], cyc[N], cnt[N], ps[N], st[N], vis[N], cu[N];
ll ans[N];
void dfs(int v) {
used[v] = 1;
for (int u : g[v])
if (!used[u])
dfs(u);
}
void dfs2(int v, int pos) {
used[v] = 1;
cnt[pos]++;
pos--;
if (pos < 0)
pos = cl.size() - 1;
for (int u : g[v])
if (!cyc[u])
dfs2(u, pos);
}
void dfs3(int v, int h, int fv, ll ck) {
vis[v] = 1;
st[h - 1] = v;
ans[st[(h - ck % h) % h]]++;
for (int u : g[v]) {
if (u == fv)
continue;
dfs3(u, h + 1, fv, ck);
}
}
void dfs4(int v, ll pos, int fv) {
assert(vis[v] != 2);
vis[v] = 2;
ans[cl[pos]]++;
for (int u : g[v])
if (u != fv && cu[u] != 2)
dfs4(u, (pos - 1 + (ll) cl.size()) % cl.size(), fv);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
ll n, k;
cin >> n >> k;
rep(i, n) {
cin >> a[i];
a[i]--;
g[a[i]].push_back(i);
pos[i] = -1;
}
ll c = 0, v = 0, bl, u, dv, bd;
while (pos[v] == -1) {
l1.push_back(v);
pos[v] = c++;
v = a[v];
}
bl = c - pos[v];
bd = pos[v];
ll dvp = (k - bd) % bl;
dv = l1[bd + dvp];
dfs(v);
ans[dv] += (n - c) * n;
// rep(i, bl) {
// ll of = (i - dvp + bl) % bl;
// rep(i, bd)
// ans[l1[bd + i]] += (c - 2 - i - of + bl - 1) / bl;
// }
/*rep(i, bd)
rep(j, c - 1 - i)
ans[l1[((k - bd - j) % bl + bl) % bl + bd]]++;
rep(i, n) {
if (used[i])
continue;
u = i;
cl.clear();
while (pos[u] == -1) {
pos[u] = -2;
u = a[u];
}
while (!cyc[u]) {
cnt[cl.size()] = 0;
cl.push_back(u);
cyc[u] = 1;
u = a[u];
}
int cls = cl.size();
rep(i, cls)
dfs2(cl[i], i);
rep(i, cls)
ps[i + 1] = ps[i] + cnt[i];
rep(i, cls) {
cout << cl[i] << ' ' << cnt[i] << '\n';
int rp = (i + k) % cls + 1, lp = (i + k - c % cls + 1) % cls;
cout << ' ' << lp << ' ' << rp << '\n';
if (lp < 0) {
lp += cls;
ans[cl[i]] += ps[cls];
}
ans[cl[i]] += c / cls * ps[cls] + ps[rp] - ps[lp];
}
}*/
if (n >= 3000) {
rep(i, c) {
rep(j, n)
vis[j] = cu[j] = 0;
dfs3(l1[i], 1, l1[i], k - i);
rep(j, n) {
if (vis[j])
continue;
cl.clear();
u = j;
while (!cu[u]) {
cu[u] = 1;
assert(!vis[u]);
u = a[u];
}
while (cu[u] == 1) {
cl.push_back(u);
cu[u] = 2;
assert(!vis[u]);
u = a[u];
}
rep(l, cl.size())
dfs4(cl[l], (l + k - i - 1) % cl.size(), l1[i]);
}
}
}
else {
rep(i, n)
if (!used[i])
ans[i] += c;
ans[dv] += c;
for (int i = 1; i < c; i++) {
int pos = c - i + (k - 1) % i + 1;
ans[l1[pos % c]] += (c - pos == 0 ? i : pos - c + i);
int cc = c - (c - pos == 0 ? i : pos - c + i);
// cout << pos << '\n';
while (cc > 0) {
pos = (pos + i) % c;
ans[l1[pos]] += min(cc, i);
cc -= min(cc, i);
}
// rep(j, c)
// cout << ans[l1[j]] << ' ';
// cout << '\n';
}
}
rep(i, n)
cout << ans[i] << '\n';
}
Compilation message
space_pirate.cpp: In function 'int main()':
space_pirate.cpp:19:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i, n) for (int i = 0; i < (n); i++)
^
space_pirate.cpp:154:17: note: in expansion of macro 'rep'
rep(l, cl.size())
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2078 ms |
10368 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
