#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <functional>
using ll = long long;
const int MN = 101000;
int N, a[MN], X[MN], Y[MN], L, _map[MN*2], *map=_map+MN, p[MN][17], s[MN];
ll K, f[MN], psum[MN];
bool vis[MN];
std::vector<int> b[MN], path, invmap[MN*2], invmap2[MN*2];
void dfs(int n)
{
for(int i=0;p[n][i]&&p[p[n][i]][i];++i)
p[n][i+1]=p[p[n][i]][i];
vis[n]=1;
s[n] = 1;
for(auto x:b[n])
if(vis[x])
{
assert(x==path.front());
L=X[n];
assert(path[L]==n);
}
else
{
if(!~X[x]) X[x]=X[n];
Y[x]=Y[n]+1;
p[x][0]=n, dfs(x);
s[n]+=s[x];
}
//printf("%d: [X: %d, Y: %d, s: %d]\n", n, X[n], Y[n]);
}
void case2(int n, int gL)
{
std::vector<int> q(0);
for(;;n=a[n])
{
if(vis[n]) break;
q.push_back(n);
vis[n]=1;
}
std::reverse(q.begin(), q.end());
assert(a[q.front()] == n);
int L=0;
for(;q[L]!=n;++L);
++L;
ll cv=0;
std::vector<int> p(L,0);
int KmL = K%L;
auto upd = [&](int depth)//reaches zero after [depth] steps
{
//end up at start_node - K
//(depth + v + 1) - K
// for all v = [0,gL)
// inc(depth+1-K, depth+gL+1-K); inc-exc
int l=(depth+1-KmL+L)%L;
int r=l+gL;
if(r-l>L)
{
int d = (r-l)/L;
r-=d*L;
cv+=d;
}
assert(r<2*L);
if(r<L) ++p[l], --p[r];
else ++cv, --p[r-L], ++p[l];
};
std::function<void(int, int)> dfs=[&](int n, int d)
{
upd(d);
vis[n]=1;
for(auto x:b[n])
if(!vis[x])
dfs(x, d+1);
};
for(int i=0;i<q.size();++i) dfs(q[i], i);
for(int i=0;i<L;++i)
f[q[i]] += cv += p[i];//impact
}
int mup(int n, int d)
{
assert(d<=Y[n]);//minor assert
for(int i=0;d;++i, d>>=1)
if(d&1)
n=p[n][i];
assert(n);//minor assert
return n;
}
void dfs2(int n)//case 3B
{
vis[n]=1;
for(auto x:b[n])
if(!vis[x])
dfs2(x);
//now, we do the black magic
int D, E;
//top (inclusive)
D = Y[n]-(X[n]+1);
E = map[D];
assert(E>=D+1 || Y[n]>=E); assert(Y[n]>=D); //true
if(E<Y[n])
{
int t=mup(n, Y[n]-E);
if(D>=0) f[t]+=s[n];// Upper Normal (+E)
}
else
{
E-=D+1;
if(D>=0) f[path[E]]+=s[n];// Upper Boundary (+E')
}
//bottom (exclusive)
D = Y[n]-L;
E = map[D];
assert(E>=D+1 || Y[n]>=E); assert(Y[n]>=D); //true
if(E<Y[n])
{
int t=mup(n, Y[n]-E);
f[t]-=s[n];// Bottom Normal (-E)
}
else
{
E-=D+1;
f[path[E]]-=s[n];// Bottom Boundary (-E')
}
//self : D in (Y-L, Y-X) (exc, exc)
int x=std::distance(std::upper_bound(invmap[Y[n]].begin(), invmap[Y[n]].end(), Y[n]-L), std::lower_bound(invmap[Y[n]].begin(), invmap[Y[n]].end(), Y[n]-X[n]));
f[n]+=(ll)x*s[n];// Boundary Normal (+E)
psum[Y[n]]+=s[n];
}
void dfs3(int n)
{
vis[n]=1;
for(auto x:b[n])
if(!vis[x])
dfs3(x);
//black magic part 2
int D, E;
//top(inc)
D = Y[n];
if(D>0)//aka D exists
{
E = Y[n]-(Y[n]-map[D]+D+1)%(D+1);
f[mup(n, Y[n]-E)] += s[n]; // Top Normal
}
//bot(exc)
D = Y[n]-X[n]-1;
if(D>0)//again, D exists
{
E = (Y[n]-1)-(Y[n]-1-map[D]+D+1)%(D+1);
f[mup(n, Y[n]-E)] -= s[n]; // Bot Normal
}
//self: [Y[n]-X[n], Y[n]) (inc, exc). If you map to yourself, then it's already accounted for
int x=std::distance(std::lower_bound(invmap[Y[n]].begin(), invmap[Y[n]].end(), Y[n]-X[n]), std::lower_bound(invmap[Y[n]].begin(), invmap[Y[n]].end(), Y[n]));
f[n]+=(ll)x*s[n];
psum[Y[n]]+=s[n];
}
int main()
{
scanf("%d%lld", &N, &K);
for(int i=1;i<=N;++i) scanf("%d", a+i), b[a[i]].push_back(i);
for(int n=1;;n=a[n])
{
if(vis[n])
break;
vis[n]=1;
path.push_back(n);
}
memset(vis+1, 0, N*sizeof*vis);
memset(X+1, -1, N*sizeof*X);
std::reverse(path.begin(), path.end());//path[0] = root of tree
for(int i=0;i<path.size();++i)
X[path[i]]=i;
dfs(path.front());
++L;//# of nodes, not index
//printf("PATH:"); for(int i=0;i<path.size();++i) printf(" %d", path[i]); printf("\n");
f[path[L-(K-path.size())%L-1]] += (ll)N*(N-L);//other -> ALL
//at this point, every vis[(main)] = true
//path -> non-main (Case 2)
for(int i=1;i<=N;++i)
if(!vis[i])
case2(i, path.size());
//for(int i=1;i<=N;++i) printf("%lld%c", f[i], " \n"[i==N]);
//CHECK #1 SEEMS TO WORK
//setup
//X, Y arrays
//path -> non-subtree (case 3B)
for(int i=-L;i<=N;++i)//technically 1-L is the true bound, but whatever. should be identical
{
int nL=L+i+1;
map[i]=nL-K%nL-1, invmap[map[i]].push_back(i);//L'=L+D+1
if(map[i]>i-1)//technically >=, but invmap2[0] is never used...
invmap2[map[i]-i-1].push_back(i);
//printf("MAP: %d -> %d\n", i, map[i]);
}
//memset(f+1, 0, N*sizeof*f);//TEMPORARY FOR TESTING
memset(vis+1, 0, N*sizeof*vis);
for(auto x:path)vis[x]=1;
/*
For each triangle D:
- Definition: E = expected depth = par at depth map[D]
- Definition: E'= special path node = path[map[D]-D-1]
- Upper: +E' if boundary deeper, else +E. Equality: +E'
- Bound: -E'+E if boundary exists in triangle, inclusive on both top&bot
- Lower: -E' if boundary deeper, else -E. Equality: -E'
*/
if(L<path.size()) for(int i=0;i<L;++i) s[path[i]]-=s[path[L]];
for(int i=0;i<L;++i)
{
dfs2(path[i]);
for(auto D:invmap2[i])
{
//cutoff point = true E = i+D+1
//X-value must be strictly less than E-D = strictly less than i+1 = less than eq to i
int E = i+D+1;
//check to see if removing this is actually warranted
assert(0<=E);//actually I daresay 0 < E is assertable. check line 206
if(0<=E && E<D+L)//E is (inclusively) in triangle of D. (D+1 or D?) <= E is guaraunteed, so E is definitely low enough. Just have to check if it's too low
f[path[i]] -= psum[E];//-E'
//Very interesting dynamic happened in above line. path[E-D-1]=target => implying sum of boundary = (sum s[n], provided [Y[n]==E && X[n]<=E-D-1])
//X[n]<=E-D-1, because triangle D, Y[n]=E => path[E-D] is valid A node, so (X[n] < X[path[E-D]] = E-D)
}
}
for(int i=-L;i<0;++i)
{
assert(0 <= map[i]-i-1 && map[i]-i-1 < L);
f[path[map[i]-i-1]]+=s[path[0]];//Upper Special (+E')
}
if(L<path.size()) for(int i=0;i<L;++i) s[path[i]]+=s[path[L]];
//printf("CHECK 3B: "); for(int i=1;i<=N;++i) printf("%lld%c", f[i], " \n"[i==N]);
//path -> subtree (case 3C)
//memset(f+1, 0, N*sizeof*f);//TEMP RESET
memset(psum, 0, N*sizeof*psum);
for(int i=N;i>0;--i)// 0 = node -> itself. also N is impossible..
{
invmap[i].clear();
map[i]=i-(K-path.size())%(i+1);
//printf("MAP %d -> %d\n", i, map[i]);
for(int j=map[i];j<=N;j+=i+1)
invmap[j].push_back(i);
}
invmap[0].clear();
memset(vis+1, 0, N*sizeof*vis);
for(auto x:path) vis[x]=1;
for(int i=path.size()-1;i>=0;--i)
{
for(auto x:invmap[i])
if(i+x+1<N)
f[path[i]] -= psum[i+x+1];
dfs3(path[i]);
}
for(auto x:path) ++f[x];
//printf("CHECK 3C: "); for(int i=1;i<=N;++i) printf("%lld%c", f[i], " \n"[i==N]);
for(int i=1;i<=N;++i) printf("%lld\n", f[i]);
return 0;
}
Compilation message
space_pirate.cpp: In function 'void case2(int, int)':
space_pirate.cpp:82:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<q.size();++i) dfs(q[i], i);
~^~~~~~~~~
space_pirate.cpp: In function 'int main()':
space_pirate.cpp:180:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<path.size();++i)
~^~~~~~~~~~~~
space_pirate.cpp:222:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(L<path.size()) for(int i=0;i<L;++i) s[path[i]]-=s[path[L]];
~^~~~~~~~~~~~
space_pirate.cpp:244:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(L<path.size()) for(int i=0;i<L;++i) s[path[i]]+=s[path[L]];
~^~~~~~~~~~~~
space_pirate.cpp:168:7: 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:169:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=N;++i) scanf("%d", a+i), b[a[i]].push_back(i);
~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
136 ms |
28904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
