oj.uz

Submission #252319

# Submission time Handle Problem Language Result Execution time Memory
252319 2020-07-25T09:17:06 Z frodakcin Space Pirate (JOI14_space_pirate) C++11
47 / 100
 304 ms 43380 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];
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 12288 KB Output is correct
2 Correct 10 ms 12288 KB Output is correct
3 Correct 7 ms 12288 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 7 ms 12288 KB Output is correct
9 Correct 7 ms 12288 KB Output is correct
10 Correct 8 ms 12288 KB Output is correct
11 Correct 7 ms 12160 KB Output is correct
12 Correct 8 ms 12292 KB Output is correct
13 Correct 7 ms 12288 KB Output is correct
14 Correct 7 ms 12288 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12288 KB Output is correct
2 Correct 10 ms 12288 KB Output is correct
3 Correct 7 ms 12288 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 7 ms 12288 KB Output is correct
9 Correct 7 ms 12288 KB Output is correct
10 Correct 8 ms 12288 KB Output is correct
11 Correct 7 ms 12160 KB Output is correct
12 Correct 8 ms 12292 KB Output is correct
13 Correct 7 ms 12288 KB Output is correct
14 Correct 7 ms 12288 KB Output is correct
15 Correct 9 ms 12800 KB Output is correct
16 Correct 9 ms 12800 KB Output is correct
17 Correct 10 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 13056 KB Output is correct
21 Correct 11 ms 13056 KB Output is correct
22 Correct 13 ms 13056 KB Output is correct
23 Correct 11 ms 13056 KB Output is correct
24 Correct 10 ms 13056 KB Output is correct
25 Correct 14 ms 12800 KB Output is correct
26 Correct 11 ms 13056 KB Output is correct
27 Correct 10 ms 12928 KB Output is correct
28 Correct 10 ms 12928 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 29304 KB Output is correct
2 Incorrect 304 ms 43380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12288 KB Output is correct
2 Correct 10 ms 12288 KB Output is correct
3 Correct 7 ms 12288 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 7 ms 12288 KB Output is correct
9 Correct 7 ms 12288 KB Output is correct
10 Correct 8 ms 12288 KB Output is correct
11 Correct 7 ms 12160 KB Output is correct
12 Correct 8 ms 12292 KB Output is correct
13 Correct 7 ms 12288 KB Output is correct
14 Correct 7 ms 12288 KB Output is correct
15 Correct 9 ms 12800 KB Output is correct
16 Correct 9 ms 12800 KB Output is correct
17 Correct 10 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 13056 KB Output is correct
21 Correct 11 ms 13056 KB Output is correct
22 Correct 13 ms 13056 KB Output is correct
23 Correct 11 ms 13056 KB Output is correct
24 Correct 10 ms 13056 KB Output is correct
25 Correct 14 ms 12800 KB Output is correct
26 Correct 11 ms 13056 KB Output is correct
27 Correct 10 ms 12928 KB Output is correct
28 Correct 10 ms 12928 KB Output is correct
29 Correct 181 ms 29304 KB Output is correct
30 Incorrect 304 ms 43380 KB Output isn't correct
31 Halted 0 ms 0 KB -