Submission #126573

#	Time	Username	Problem	Language	Result	Execution time	Memory
126573		WhipppedCream	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	890 ms	34436 KiB

catdog

#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;

vector<int> adj[maxn];

int n;

int par[22][maxn];
int dep[maxn];
int cnt[maxn];
int pref[maxn];
int pos[maxn];
int head[maxn];
int tail[maxn];

ii per[maxn];

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

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

struct node
{
	int val[4];
	node()
	{
		memset(val, 0, sizeof val);
	}
	node operator + (node &other) const
	{
		node res;
		for(int i = 0; i< 4; i++) res.val[i] = 1e9;
		for(int i = 0; i< 4; i++)
		{
			int b1 = (i&2)> 0;
			int b2 = (i&1)> 0;
			for(int j = 0; j< 4; j++)
			{
				int b3 = (j&2)> 0;
				int b4 = (j&1)> 0;
				res.val[b1*2+b4] = min(res.val[b1*2+b4], val[i]+other.val[j]+(b2!= b3));
			}
		}
		return res;
	}
};

node st[4*maxn];

void build(int p = 1, int L = 1, int R = n)
{
	if(L == R)
	{
		st[p] = node();
		st[p].val[1] = st[p].val[2] = 1e9;
		return;
	}
	int M = (L+R)>>1;
	build(p<<1, L, M);
	build(p<<1|1, M+1, R);
	st[p] = st[p<<1]+st[p<<1|1];
}

void update(int x, ii v, int p = 1, int L = 1, int R = n)
{
	if(L == R)
	{
		st[p].val[0] += v.X;
		st[p].val[3] += v.Y;
		return;
	}
	int M = (L+R)>>1;
	if(x<= M) update(x, v, p<<1, L, M);
	else update(x, v, p<<1|1, M+1, R);
	st[p] = st[p<<1] + st[p<<1|1];
}

node ask(int i, int j, int p = 1, int L = 1, int R = n)
{
	if(i> R || j< L)
	{
		node res;
		res.val[1] = res.val[2] = 1e9;
		return res;	
	}
	if(i<= L && R<= j) return st[p];
	int M = (L+R)>>1;
	node x = ask(i, j, p<<1, L, M);
	node y = ask(i, j, p<<1|1, M+1, R);
	return x+y;
}

void change(int u, ii x)
{
	// printf("change %d\n", u);
	while(u)
	{
		// printf("go %d {%d, %d}\n", u, x.X, x.Y);
		update(pos[u], x);
		node tmp = ask(pos[head[u]], pos[tail[head[u]]]);
		// for(int i = 0; i< 4; i++) printf("%d ", tmp.val[i]);
		// printf("\n");
		int v0 = min(tmp.val[0], tmp.val[1]);
		int v1 = min(tmp.val[2], tmp.val[3]);
		ii res = {min(v0, v1+1), min(v0+1, v1)};
		x = ii(res.X-per[head[u]].X, res.Y-per[head[u]].Y);
		per[head[u]] = res;
		u = par[0][head[u]];
	}
}

int gimme()
{
	node res = ask(pos[1], pos[tail[1]]);
	return *min_element(res.val, res.val+4);
}

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();
	build();
}

int stat[maxn];

int cat(int u)
{
	stat[u] = 1;
	change(u, {0, 1e9});
	return gimme();
}

int dog(int u)
{
	stat[u] = 2;
	change(u, {1e9, 0});
	return gimme();
}

int neighbor(int u)
{
	if(stat[u] == 1) change(u, {0, -1e9});
	if(stat[u] == 2) change(u, {-1e9, 0});
	stat[u] = 0;
	return gimme();
}

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