oj.uz

Submission #252323

# Submission time Handle Problem Language Result Execution time Memory
252323 2020-07-25T09:23:48 Z frodakcin Space Pirate (JOI14_space_pirate) C++11
100 / 100
 390 ms 43508 KB 
#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*2];
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 dfs1(int n, int offset)//case 3A
{
	vis[n]=1;
	for(auto x:b[n])
		if(!vis[x])
			dfs1(x, offset);
	int d=Y[n];
	ll l = K-d-1-offset, r = K-d-1;
	psum[0]-=l/L, ++psum[l%L];
	psum[0]+=r/L, --psum[r%L];
}

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-path.size());//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());

	//printf("CHECK  2: "); for(int i=1;i<=N;++i) printf("%lld%c", f[i], " \n"[i==N]);
	//memset(f+1, 0, N*sizeof*f);//TEMPORARY FOR TESTING
	//CHECK #1 SEEMS TO WORK

	//non-cyc -> non-subtree (case 3A)
	if(L<path.size())
	{
		memset(vis+1, 0, N*sizeof*vis);
		for(auto x:path) vis[x]=1;
		for(int i=0;i+1<path.size();++i)
			dfs1(path[i], path.size()-std::max(L, i+1));
		ll cv=0;
		for(int i=0;i<L;++i)
			f[path[L-i-1]]+=cv+=psum[i];
		memset(psum, 0, L*sizeof*psum);
	}
	//printf("CHECK 3A: "); for(int i=1;i<=N;++i) printf("%lld%c", f[i], " \n"[i==N]);
	//memset(f+1, 0, N*sizeof*f);//TEMPORARY FOR TESTING

	//cyc -> 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-path.size()+L)%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(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]);
	//memset(f+1, 0, N*sizeof*f);//TEMP RESET

	//path -> subtree (case 3C)
	memset(psum, 0, N*sizeof*psum);
	for(int i=0;i<=N;++i) invmap[i].clear();
	for(int i=1;i<=N;++i)// 0 = node -> itself. also N is impossible..
	{
		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);
	}
	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%c", f[i], " \n"[i==N]);
	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:193:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<path.size();++i)
              ~^~~~~~~~~~~~
space_pirate.cpp:213:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(L<path.size())
     ~^~~~~~~~~~~~
space_pirate.cpp:217:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i+1<path.size();++i)
               ~~~^~~~~~~~~~~~
space_pirate.cpp:247: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:269: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:181: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:182: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);
                        ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12160 KB Output is correct
2 Correct 7 ms 12160 KB Output is correct
3 Correct 6 ms 12160 KB Output is correct
4 Correct 7 ms 12288 KB Output is correct
5 Correct 7 ms 12288 KB Output is correct
6 Correct 7 ms 12160 KB Output is correct
7 Correct 7 ms 12288 KB Output is correct
8 Correct 6 ms 12160 KB Output is correct
9 Correct 7 ms 12160 KB Output is correct
10 Correct 6 ms 12160 KB Output is correct
11 Correct 7 ms 12160 KB Output is correct
12 Correct 7 ms 12288 KB Output is correct
13 Correct 7 ms 12288 KB Output is correct
14 Correct 8 ms 12160 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12160 KB Output is correct
2 Correct 7 ms 12160 KB Output is correct
3 Correct 6 ms 12160 KB Output is correct
4 Correct 7 ms 12288 KB Output is correct
5 Correct 7 ms 12288 KB Output is correct
6 Correct 7 ms 12160 KB Output is correct
7 Correct 7 ms 12288 KB Output is correct
8 Correct 6 ms 12160 KB Output is correct
9 Correct 7 ms 12160 KB Output is correct
10 Correct 6 ms 12160 KB Output is correct
11 Correct 7 ms 12160 KB Output is correct
12 Correct 7 ms 12288 KB Output is correct
13 Correct 7 ms 12288 KB Output is correct
14 Correct 8 ms 12160 KB Output is correct
15 Correct 9 ms 12800 KB Output is correct
16 Correct 9 ms 12800 KB Output is correct
17 Correct 9 ms 12800 KB Output is correct
18 Correct 11 ms 13056 KB Output is correct
19 Correct 10 ms 12928 KB Output is correct
20 Correct 11 ms 12928 KB Output is correct
21 Correct 10 ms 13056 KB Output is correct
22 Correct 10 ms 12928 KB Output is correct
23 Correct 10 ms 12928 KB Output is correct
24 Correct 10 ms 12952 KB Output is correct
25 Correct 9 ms 12800 KB Output is correct
26 Correct 11 ms 12964 KB Output is correct
27 Correct 10 ms 12928 KB Output is correct
28 Correct 10 ms 12928 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 29176 KB Output is correct
2 Correct 306 ms 42796 KB Output is correct
3 Correct 211 ms 39516 KB Output is correct
4 Correct 135 ms 29048 KB Output is correct
5 Correct 314 ms 43508 KB Output is correct
6 Correct 206 ms 39240 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12160 KB Output is correct
2 Correct 7 ms 12160 KB Output is correct
3 Correct 6 ms 12160 KB Output is correct
4 Correct 7 ms 12288 KB Output is correct
5 Correct 7 ms 12288 KB Output is correct
6 Correct 7 ms 12160 KB Output is correct
7 Correct 7 ms 12288 KB Output is correct
8 Correct 6 ms 12160 KB Output is correct
9 Correct 7 ms 12160 KB Output is correct
10 Correct 6 ms 12160 KB Output is correct
11 Correct 7 ms 12160 KB Output is correct
12 Correct 7 ms 12288 KB Output is correct
13 Correct 7 ms 12288 KB Output is correct
14 Correct 8 ms 12160 KB Output is correct
15 Correct 9 ms 12800 KB Output is correct
16 Correct 9 ms 12800 KB Output is correct
17 Correct 9 ms 12800 KB Output is correct
18 Correct 11 ms 13056 KB Output is correct
19 Correct 10 ms 12928 KB Output is correct
20 Correct 11 ms 12928 KB Output is correct
21 Correct 10 ms 13056 KB Output is correct
22 Correct 10 ms 12928 KB Output is correct
23 Correct 10 ms 12928 KB Output is correct
24 Correct 10 ms 12952 KB Output is correct
25 Correct 9 ms 12800 KB Output is correct
26 Correct 11 ms 12964 KB Output is correct
27 Correct 10 ms 12928 KB Output is correct
28 Correct 10 ms 12928 KB Output is correct
29 Correct 137 ms 29176 KB Output is correct
30 Correct 306 ms 42796 KB Output is correct
31 Correct 211 ms 39516 KB Output is correct
32 Correct 135 ms 29048 KB Output is correct
33 Correct 314 ms 43508 KB Output is correct
34 Correct 206 ms 39240 KB Output is correct
35 Correct 187 ms 33968 KB Output is correct
36 Correct 207 ms 33912 KB Output is correct
37 Correct 200 ms 32888 KB Output is correct
38 Correct 390 ms 42408 KB Output is correct
39 Correct 251 ms 39200 KB Output is correct
40 Correct 306 ms 41340 KB Output is correct
41 Correct 308 ms 43120 KB Output is correct
42 Correct 270 ms 39548 KB Output is correct
43 Correct 234 ms 39796 KB Output is correct
44 Correct 264 ms 39156 KB Output is correct
45 Correct 128 ms 26488 KB Output is correct
46 Correct 309 ms 42612 KB Output is correct
47 Correct 198 ms 36464 KB Output is correct
48 Correct 215 ms 37108 KB Output is correct