Submission #1213336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213336		catch_me_if_you_can	Cats or Dogs (JOI18_catdog)	C++20	100 / 100	262 ms	27976 KiB

catdog

#include<bits/stdc++.h>
#include "catdog.h"
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int MX = 1e5+5;
const int INF = 1e9;

in col[3] = {{0, INF}, {INF, 0}, {0, 0}};

in contrib(in a)
{
	return {min(a[0], a[1]+1), min(a[0]+1, a[1])};
}

struct cdata
{
	int v[2][2];
	void init(in ab)
	{
		v[0][0] = ab[0];
		v[1][1] = ab[1];
		v[0][1] = v[1][0] = INF;
		return;
	}
	cdata operator+(const cdata &m)
	{
		cdata x;
		if((v[0][0] < 0))
			return m;
		if((m.v[0][0] < 0))
		{
			for(int i = 0; i < 2; i++)
				for(int j = 0; j < 2; j++)
					x.v[i][j] = v[i][j];
			return x;
		}
		for(int i = 0; i < 2; i++)
		{
			for(int j = 0; j < 2; j++)
			{
				x.v[i][j] = INF;
				for(int jp = 0; jp < 2; jp++)
				{
					for(int ip = 0; ip < 2; ip++)
						x.v[i][j] = min(x.v[i][j], v[i][jp] + m.v[ip][j] + (ip^jp));
				}
			}
		}
		return x;
	}
};

cdata cope;

struct seg_tree
{
	vector<cdata> tree;
	void init(int n)
	{
		tree.resize(4*n+13);
		for(auto &s: tree)
			s.init(col[2]);
		return;
	}
	void upd(in val, int p, int id, int l, int r)
	{
		if(l == r)
		{
			tree[id].init(val);
			return;
		}
		int m = (l+r)/2;
		if(p <= m)
			upd(val, p, 2*id, l, m);
		else
			upd(val, p, 2*id+1, m+1, r);
		tree[id] = tree[2*id] + tree[2*id+1];
		return;
	}
	cdata query(int ql, int qr, int id, int l, int r)
	{
		if(qr < l || r < ql)
			return cope;
		if((ql <= l) && (r <= qr))
			return tree[id];
		int m = (l+r)/2;
		return query(ql, qr, 2*id, l, m) + query(ql, qr, 2*id+1, m+1, r);
	}
};

int NN;// = n.

seg_tree work;

vector<int> temp;//serves no real purpose honestly, for convenience.
vector<int> adj[MX];

vector<int> head(MX);
vector<int> lv(MX);
vector<int> pa(MX);
vector<int> sub(MX);

void dfs1(int u, int p)
{
	sub[u] = 1;
	pa[u] = p;
	temp.clear();
	for(int v: adj[u])
	{
		if(v == p)
			continue;
		temp.pb(v);
	}
	swap(adj[u], temp);
	in bst = {-1, -1};
	for(int s = 0; s < adj[u].size(); s++)
	{
		dfs1(adj[u][s], u);
		sub[u]+=sub[adj[u][s]];
		bst = max(bst, {sub[adj[u][s]], s});
	}
	if(bst[1] > 0)
		swap(adj[u][0], adj[u][bst[1]]);
	return;
}

int tin[MX];

int TIMER;

void dfs2(int u)
{
	tin[u] = ++TIMER;
	if(adj[u].empty())
	{
		lv[u] = u;
		return;
	}
	head[adj[u][0]] = head[u];
	dfs2(adj[u][0]);
	lv[u] = lv[adj[u][0]];
	for(int v: adj[u])
	{
		if(v == adj[u][0]) continue;
		head[v] = v; dfs2(v);
	}
	return; 
}

vector<in> dp(MX);//current total contribution. it is really only important for the Heads.
vector<in> light(MX);//current contribution from ONLY light children. we maintain this for everyone.
vector<in> cur(MX);//current stuff.

void initialize(int n, vector<int> a, vector<int> b)
{
	NN = n;
	for(int i = 0; i < 2; i++)
		for(int j = 0; j < 2; j++)
			cope.v[i][j] = -1;
	for(int i = 0; i < n-1; i++)
	{
		adj[a[i]].pb(b[i]);
		adj[b[i]].pb(a[i]);
	}
	for(int i = 1; i <= n; i++)
	{
		cur[i] = {0, 0};
		light[i] = {0, 0};
		dp[i] = {0, 0};
	}
	dfs1(1, 0);
	head[1] = 1;
	TIMER = 0;
	dfs2(1);
	work.init(n);
	return;
}

int upd_light(int u, in LT)
{
	int x = head[u];
	light[u] = LT;
	work.upd(LT, tin[u], 1, 1, NN);
	cdata C = work.query(tin[x], tin[lv[u]], 1, 1, NN);
	in ndp = {min(C.v[0][0], C.v[0][1]), min(C.v[1][0], C.v[1][1])};
	
	in noww = contrib(ndp);
	in earli = contrib(dp[x]);
	dp[x] = ndp;//correct the dp value

	int z = pa[x];
	if(z == 0)
		return min(dp[x][0], dp[x][1]);

	in LTp;//we need to compute LTp
	LTp[0] = noww[0] - earli[0] + light[z][0];
	LTp[1] = noww[1] - earli[1] + light[z][1];
	return upd_light(z, LTp);
}

int upd(int u, in Lt)
{
	in dlt = {Lt[0]-cur[u][0], Lt[1]-cur[u][1]};
	cur[u] = Lt;
	in Ltp = {light[u][0] + dlt[0], light[u][1] + dlt[1]};
	return upd_light(u, Ltp);
}

int cat(int v)
{
	return upd(v, {0, INF});
}

int dog(int v)
{
	return upd(v, {INF, 0});
}

int neighbor(int v)
{
	return upd(v, {0, 0});
}

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