Submission #122603

#	Time	Username	Problem	Language	Result	Execution time	Memory
122603		WhipppedCream	Cats or Dogs (JOI18_catdog)	C++17	0 / 100	4 ms	2816 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxn = 1e5+5;
int n;
vector<int> adj[maxn];
int par[22][maxn];
int dep[maxn];
int cnt[maxn];
int prf[maxn];
int pos[maxn];
int head[maxn];
int stat[maxn]; //1 cat 2 Dog
int run = 0;

struct segtree
{
	ll st[4*maxn];
	ll lz[4*maxn];
	void push(int p, int L, int R)
	{
		if(!lz[p]) return;
		st[p] += lz[p];
		if(L != R)
		{
			lz[2*p] += lz[p];
			lz[2*p+1] += lz[p];
		}
		lz[p] = 0;
	}
	void pull(int p)
	{
		st[p] = st[2*p] + st[2*p+1];
	}
	void update(int i, int j, int dx, int p = 1, int L = 1, int R = n)
	{
		push(p, L, R);
		if(i> R || j< L) return;
		if(i<= L && R<= j)
		{
			lz[p] += dx;
			push(p, L, R);
			return;
		}
		int M = (L+R)/2;
		update(i, j, dx, 2*p, L, M);
		update(i, j, dx, 2*p+1, M+1, R);
		pull(p);
	}
	int ask(int i, int j, int p = 1, int L = 1, int R = n)
	{
		if(i> R || j< L) return 0;
		push(p, L, R);
		if(i<= L && R<= j) return st[p];
		int M = (L+R)/2;
		int x = ask(i, j, 2*p, L, M);
		int y = ask(i, j, 2*p+1, M+1, R);
		return x+y;
	}
};

segtree Cat, Dog, sum;

void changeme(segtree &st, int u, int v, int dx)
{
	if(dep[u]< dep[v]) return;
	while(head[u] != head[v])
	{
		st.update(pos[head[u]], pos[u], dx);
		u = par[0][head[u]];
	}
	st.update(pos[v], pos[u], dx);
}

int gimme(segtree &st, int u, int v)
{
	//v higher than u, v an ancestor of u
	if(v == 0) v = 1;
	int res = 0;
	while(head[u] != head[v])
	{
		res += st.ask(pos[head[u]], pos[u]);
		u = par[0][head[u]];
	}
	res += st.ask(pos[v], pos[u]);
	return res;
}

void dfs(int u = 1, int p = 0)
{
	dep[u] = dep[p]+1;
	par[0][u] = p;
	for(int i = 1; i<= 20; i++) par[i][u] = par[i-1][par[i-1][u]];
	cnt[u] = 1;
	ii big = {0, -1};
	for(int v : adj[u])
	{
		if(v == p) continue;
		dfs(v, u);
		big = max(big, {cnt[v], v});
		cnt[u] += cnt[v];
	}
	prf[u] = big.Y;
}

void hld()
{
	for(int i = 1; i<= n; i++)
	{
		if(prf[par[0][i]] == i) continue;
		for(int j = i; j != -1; j = prf[j])
		{
			head[j] = i;
			pos[j] = ++run;
		}
	}
}

void initialize(int N, vector<int> A, vector<int> B)
{
	n = N;
	for(int i = 0; i< n-1; i++)
	{
		adj[A[i]].pb(B[i]);
		adj[B[i]].pb(A[i]);
	}
	dfs(); hld();
}

int cat(int u)
{
	int c = gimme(Cat, u, u);
	int d = gimme(Dog, u, u);
	int cc = min(c, d+1);
	int dd = min(d, c+1);
	int cx = c;
	int dx = c+1;
	int cur = u;
	for(int i = 20; i>= 0; i--)
	{
		if(gimme(sum, u, par[i][cur]) == 0)
		{
			cur = par[i][cur];
		}	
	}
	cur = par[0][cur];
	bool iszero = (cur == 0);
	if(cur == 0) cur = 1;
	changeme(Cat, par[0][u], cur, cx-cc);
	changeme(Dog, par[0][u], cur, dx-dd);
	if(!iszero)
	{
		int st = stat[cur];
		assert(st);
		if(st == 1)
		{
			dd = cc+1;
			dx = cx+1;
		}
		else
		{
			cc = dd+1;
			cx = dx+1;
		}
		cur = par[0][cur];
		if(cur)
		{
			changeme(Cat, cur, 1, cx-cc);
			changeme(Dog, cur, 1, dx-dd);
		}
	}
	stat[u] = 1;
	changeme(sum, u, u, 1);
	for(int i = 1; i<= n; i++) printf("%d ", gimme(Cat, i, i));
	printf("\n");
	for(int i = 1; i<= n; i++) printf("%d ", gimme(Dog, i, i));
	printf("\n");
	if(stat[u] == 1) return gimme(Cat, 1, 1);
	if(stat[u] == 2) return gimme(Dog, 1, 1);
	return min(gimme(Cat, 1, 1), gimme(Dog, 1, 1));
}

int dog(int u)
{
	int c = gimme(Cat, u, u);
	int d = gimme(Dog, u, u);
	int cc = min(c, d+1);
	int dd = min(d, c+1);
	int cx = d+1;
	int dx = d;
	int cur = u;
	for(int i = 20; i>= 0; i--)
	{
		if(gimme(sum, u, par[i][cur]) == 0)
		{
			cur = par[i][cur];
		}	
	}	
	cur = par[0][cur];
	bool iszero = (cur == 0);
	if(cur == 0) cur = 1;
	changeme(Cat, par[0][u], cur, cx-cc);
	changeme(Dog, par[0][u], cur, dx-dd);
	if(!iszero)
	{
		int st = stat[cur];
		assert(st);
		if(st == 1)
		{
			dd = cc+1;
			dx = cx+1;
		}
		else
		{
			cc = dd+1;
			cx = dx+1;
		}
		cur = par[0][cur];
		if(cur)
		{
			changeme(Cat, cur, 1, cx-cc);
			changeme(Dog, cur, 1, dx-dd);
		}
	}
	stat[u] = 2;
	changeme(sum, u, u, 1);
	for(int i = 1; i<= n; i++) printf("%d ", gimme(Cat, i, i));
	printf("\n");
	for(int i = 1; i<= n; i++) printf("%d ", gimme(Dog, i, i));
	printf("\n");
	if(stat[u] == 1) return gimme(Cat, 1, 1);
	if(stat[u] == 2) return gimme(Dog, 1, 1);
	return min(gimme(Cat, 1, 1), gimme(Dog, 1, 1));
}

int neighbor(int u)
{
	int c = gimme(Cat, u, u);
	int d = gimme(Dog, u, u);
	int cc, dd;
	if(stat[u] == 1)
	{
		cc = c;
		dd = c+1;
	}
	else
	{
		cc = d+1;
		dd = d;
	}
	int cx = min(c, d+1);
	int dx = min(c+1, d);
	int cur = u;
	changeme(sum, u, u, -1);
	for(int i = 20; i>= 0; i--)
	{
		if(gimme(sum, u, par[i][cur]) == 0)
		{
			cur = par[i][cur];
		}	
	}	
	cur = par[0][cur];
	bool iszero = (cur == 0);
	if(cur == 0) cur = 1;
	changeme(Cat, par[0][u], cur, cx-cc);
	changeme(Dog, par[0][u], cur, dx-dd);
	if(!iszero)
	{
		int st = stat[cur];
		assert(st);
		if(st == 1)
		{
			dd = cc+1;
			dx = cx+1;
		}
		else
		{
			cc = dd+1;
			cx = dx+1;
		}
		cur = par[0][cur];
		if(cur)
		{	
			changeme(Cat, cur, 1, cx-cc);
			changeme(Dog, cur, 1, dx-dd);
		}
	}
	stat[u] = 0;
	for(int i = 1; i<= n; i++) printf("%d ", gimme(Cat, i, i));
	printf("\n");
	for(int i = 1; i<= n; i++) printf("%d ", gimme(Dog, i, i));
	printf("\n");
	if(stat[u] == 1) return gimme(Cat, 1, 1);
	if(stat[u] == 2) return gimme(Dog, 1, 1);
	return min(gimme(Cat, 1, 1), gimme(Dog, 1, 1));
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 30
• Subtask 3: 0 / 62