#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;
lint k;
int n, a[100005];
int par[60][100005];
vector<int> gph[100005];
int anc(int x, lint k){
for(int i=0; k; i++){
if((k >> i) & 1){
k ^= (1ll << i);
x = par[i][x];
}
}
return x;
}
lint ans[100005];
int cnt[100005], up[100005], lev[100005], cmp[100005];
int din[100005], dout[100005], piv;
bool sub(int s, int t){
return din[s] <= din[t] && dout[t] <= dout[s];
}
void dfs(int x, int p){
din[x] = piv++;
for(auto &i : gph[x]){
if(i != p && cnt[i] != 2){
lev[i] = lev[x] + 1;
cmp[i] = cmp[x];
dfs(i, x);
}
}
dout[x] = piv;
}
vector<pi> qry[100005];
int deg[100005], levl[100005], cmpl[100005];
int cn[100005], cg[100005], csz[100005], ch[100005], rev[100005], piv2, piv3;
lint dx1[100005], dx2[100005];
void dfs2(int x, int p){
for(auto &i : gph[x]){
if(i != p && !deg[i]){
levl[i] = levl[x] + 1;
cmpl[i] = cmpl[x];
dfs2(i, x);
}
}
}
void dfs3(int x, int p){
for(auto &i : gph[x]){
if(i != p && !deg[i]){
dfs3(i, x);
dx1[x] += dx1[i];
}
}
}
void clear_line(){
queue<int> que;
for(int i=1; i<=n; i++){
if(!deg[i]) que.push(i);
}
while(!que.empty()){
int x = que.front();
que.pop();
deg[a[x]]--;
if(deg[a[x]] == 0) que.push(a[x]);
}
for(int i=1; i<=n; i++){
if(deg[i]){
cmpl[i] = i;
dfs2(i, -1);
}
}
for(int i=1; i<=n; i++){
if(deg[i] && !cn[i]){
piv2++;
ch[piv2] = i;
for(int j=i; !cn[j]; j=a[j]){
cg[j] = piv2;
cn[j] = ++piv3;
csz[piv2]++;
}
}
}
for(int i=1; i<=n; i++){
rev[cn[i]] = i;
}
for(int i=1; i<=n; i++){
for(auto &j : qry[i]){
int cnt = j.first;
int len = j.second;
if(len > levl[i]){
dx1[i] += cnt;
dx1[cmpl[i]] -= cnt;
len -= levl[i];
int compidx = cg[cmpl[i]];
int compnum = cn[cmpl[i]];
int compsize = csz[compidx];
int comphead = ch[compidx];
int p = cmpl[i];
if(compnum + len - 1 >= compsize + cn[comphead]){
dx2[compnum] += cnt;
dx2[cn[comphead] + compsize] -= cnt;
len -= compsize + cn[comphead] - compnum;
dx2[cn[comphead]] += 1ll * cnt * (len / compsize);
dx2[cn[comphead] + compsize] -= 1ll * cnt * (len / compsize);
len %= compsize;
dx2[cn[comphead]] += cnt;
dx2[cn[comphead] + len] -= cnt;
}
else{
dx2[compnum] += cnt;
dx2[compnum + len] -= cnt;
}
}
else{
dx1[i] += cnt;
dx1[anc(i, len)] -= cnt;
}
}
}
for(int i=1; i<=piv3; i++){
dx2[i] += dx2[i-1];
if(deg[i]) dfs3(i, -1);
}
for(int i=1; i<=n; i++){
if(deg[i]) ans[i] += dx2[cn[i]];
ans[i] += dx1[i];
}
}
void update(int s, lint l1, lint l2, int x){
s = anc(s, l1);
qry[s].push_back(pi(x, l2 - l1 + 1));
}
int oneanc[100005];
void dfs4(int x, int p){
for(auto &i : gph[x]){
if(cnt[i] != 1 && i != p){
oneanc[i] = oneanc[x];
dfs4(i, x);
}
}
}
int main(){
scanf("%d %lld",&n,&k);
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
deg[a[i]]++;
gph[a[i]].push_back(i);
par[0][i] = a[i];
}
for(int i=1; i<60; i++){
for(int j=1; j<=n; j++){
par[i][j] = par[i-1][par[i-1][j]];
}
}
int idx = 0, st = 1e9, ed = -1e9;
for(int p=1; cnt[p]<2; p=a[p]) cnt[p]++;
for(int p=1; !up[p]; p=a[p]) up[p] = ++idx;
for(int i=1; i<=n; i++){
if(cnt[i] == 2){
st = min(st, up[i]);
ed = max(ed, up[i]);
cmp[i] = i;
dfs(i, -1);
}
if(cnt[i] == 1){
oneanc[i] = i;
dfs4(i, -1);
}
}
ans[anc(1, k)] += n * (max(0ll, ed - k) + count(cnt + 1, cnt + n + 1, 0));
for(int i=1; i<=n; i++){
if(max(k - ed, 0ll) <= k - st && cmp[i] == 0) update(i, max(k - ed, 0ll), k - st, 1);
if(max(k - st + 1, 0ll) <= k - 1) update(i, max(k - st + 1, 0ll), k - 1, 1);
if(up[i] == st && up[i] <= k){
for(int j=1; j<=ed-st+1; j++){
int iter = min(k - up[i] + 1, ed - st + 1ll);
lint cnt = ed - st + 2 - j + k - up[i];
for(int it=0; ; it++){
int p = (k - up[i]) % j - j + 1 + it * j;
int q = (k - up[i]) % j + it * j;
if(p >= iter) break;
int nxt = anc(i, cnt - ((k - up[i] - q) / j) * j);
ans[nxt] += min(q, iter - 1) - max(0, p) + 1;
}
}
}
if(oneanc[i] > 0){
lint ved = k - up[oneanc[i]];
lint vst = k - st + 1;
vst = max(vst, 0ll);
if(vst <= ved) update(i, vst, ved, -1);
}
}
for(int i=1; i<=n; i++){
if(k < up[i] || cnt[i] == 0 || n > 3000) continue;
if(cnt[i] == 1){
for(int j=1; j<=n; j++){
lint t = k - up[i];
if(sub(i, j)){
t %= lev[j] - lev[i] + 1;
ans[anc(j, t)]++;
}
}
}
if(cnt[i] == 2){
for(int j=1; j<=n; j++){
lint t = k - up[i];
if(cmp[j] && cnt[j] != 2){
if(up[i] < up[cmp[j]]) t %= (ed - st + 1) - (up[cmp[j]] - up[i] - 1) + lev[j];
else t %= (up[i] - up[cmp[j]] + 1) + lev[j];
ans[anc(j, t)]++;
}
}
}
}
clear_line();
for(int i=1; i<=n; i++) printf("%lld\n", ans[i]);
}
Compilation message
space_pirate.cpp: In function 'void clear_line()':
space_pirate.cpp:110:9: warning: unused variable 'p' [-Wunused-variable]
int p = cmpl[i];
^
space_pirate.cpp: In function 'int main()':
space_pirate.cpp:159:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %lld",&n,&k);
^
space_pirate.cpp:161:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
38748 KB |
Output is correct |
| 2 |
Correct |
3 ms |
38748 KB |
Output is correct |
| 3 |
Correct |
0 ms |
38748 KB |
Output is correct |
| 4 |
Correct |
0 ms |
38748 KB |
Output is correct |
| 5 |
Correct |
3 ms |
38748 KB |
Output is correct |
| 6 |
Correct |
3 ms |
38748 KB |
Output is correct |
| 7 |
Correct |
0 ms |
38748 KB |
Output is correct |
| 8 |
Correct |
3 ms |
38748 KB |
Output is correct |
| 9 |
Correct |
3 ms |
38748 KB |
Output is correct |
| 10 |
Correct |
0 ms |
38748 KB |
Output is correct |
| 11 |
Correct |
0 ms |
38748 KB |
Output is correct |
| 12 |
Correct |
0 ms |
38748 KB |
Output is correct |
| 13 |
Correct |
0 ms |
38748 KB |
Output is correct |
| 14 |
Correct |
0 ms |
38748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
39012 KB |
Output is correct |
| 2 |
Correct |
6 ms |
38880 KB |
Output is correct |
| 3 |
Correct |
16 ms |
38880 KB |
Output is correct |
| 4 |
Correct |
89 ms |
38880 KB |
Output is correct |
| 5 |
Correct |
43 ms |
38880 KB |
Output is correct |
| 6 |
Correct |
213 ms |
38880 KB |
Output is correct |
| 7 |
Correct |
376 ms |
38880 KB |
Output is correct |
| 8 |
Correct |
126 ms |
38880 KB |
Output is correct |
| 9 |
Correct |
379 ms |
39052 KB |
Output is correct |
| 10 |
Correct |
86 ms |
39044 KB |
Output is correct |
| 11 |
Correct |
3 ms |
38880 KB |
Output is correct |
| 12 |
Correct |
83 ms |
38880 KB |
Output is correct |
| 13 |
Correct |
106 ms |
38880 KB |
Output is correct |
| 14 |
Correct |
123 ms |
38880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
446 ms |
44952 KB |
Output is correct |
| 2 |
Correct |
446 ms |
41916 KB |
Output is correct |
| 3 |
Correct |
449 ms |
43500 KB |
Output is correct |
| 4 |
Correct |
179 ms |
44952 KB |
Output is correct |
| 5 |
Correct |
483 ms |
41916 KB |
Output is correct |
| 6 |
Correct |
379 ms |
43632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
239 ms |
43204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
