Submission #252323

#	Time	Username	Problem	Language	Result	Execution time	Memory
252323		frodakcin	Space Pirate (JOI14_space_pirate)	C++11	100 / 100	390 ms	43508 KiB

space_pirate

#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 (stderr)

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 / 10
• Subtask 2: 37 / 37
• Subtask 3: 33 / 33
• Subtask 4: 20 / 20