Submission #43671

#TimeUsernameProblemLanguageResultExecution timeMemory
43671gs14004Space Pirate (JOI14_space_pirate)C++14
80 / 100
2032 ms42276 KiB
#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]; 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); } } } void mod_gazua(int v, lint k, int s, int e){ for(int i=s; i<=e; i++){ ans[anc(v, k % i)]++; } } 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); int sz = (int)min(1ll * st - up[oneanc[i]], k - up[oneanc[i]] + 1); int c = lev[i] - lev[oneanc[i]]; lint u = k - up[oneanc[i]] + 1 + lev[i] - lev[oneanc[i]]; mod_gazua(i, u, c + 1, c + sz); } } for(int i=1; i<=n; i++){ if(cmp[i] && cnt[i] != 2){ for(int j=1; j<=n; j++){ if(cnt[j] == 2 && k >= up[j]){ int md = 0; if(up[j] < up[cmp[i]]) md = ed - st + 1 - (up[cmp[i]] - up[j] - 1) + lev[i]; else md = up[j] - up[cmp[i]] + 1 + lev[i]; ans[anc(i, (k - up[j]) % md)]++; } } } } clear_line(); for(int i=1; i<=n; i++) printf("%lld\n", ans[i]); }

Compilation message (stderr)

space_pirate.cpp: In function 'int main()':
space_pirate.cpp:164: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:166:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...