Submission #1143796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143796		raspy	Cats or Dogs (JOI18_catdog)	C++20	0 / 100	3095 ms	6208 KiB

catdog

#include <bits/stdc++.h>
// #include "catdog.h"

using namespace std;

const int64_t inf = 1e5+5;

struct Node {
	int64_t dp[2][2];
};

struct SegT
{
	vector<Node> seg;
	int n;
	int s;
	SegT() {
	}
	SegT(int _n) {
		n=_n;
		s=1;
		while (s<n)s*=2;
		seg.resize(2*s);
		for (int i=s; i<2*s; i++) {
			seg[i].dp[0][0]=seg[i].dp[1][1]=0;
			seg[i].dp[0][1]=seg[i].dp[1][0]=inf;
		}
		for (int i = s-1; i; i--)
			upd(i);
	}
	void upd(int i) {
		seg[i].dp[0][0]=seg[i].dp[1][1]=inf;
		seg[i].dp[0][1]=seg[i].dp[1][0]=inf;
		for (int a = 0; a < 2; a++)
			for (int b = 0; b < 2; b++)
				for (int c = 0; c < 2; c++)
					for (int d = 0; d < 2; d++)
						seg[i].dp[a][d] = min(seg[i].dp[a][d], seg[i*2].dp[a][b]+
							seg[i*2+1].dp[c][d]+(b!=c));
	}
	void get(int& mc, int& ps) {
		int a = min(seg[1].dp[0][0],seg[1].dp[0][1]);
		int b = min(seg[1].dp[1][0],seg[1].dp[1][1]);
		ps=min(a, b+1);
		mc=min(a+1, b);
	}
	void add(int i, int dc, int dp) {
		i+=s;
		seg[i].dp[0][0]+=dp;
		seg[i].dp[1][1]+=dc;
		while (i)
		{
			upd(i);
			i/=2;
		}
	}
};

vector<int> graf[100005];
int hut[100005];
int par[100005];
int heavy[100005];
int gl[100005];
int skp[100005];
int hsz[100005];
int pos[100005];
int m;
SegT seg[100005];

int dfs(int u)
{
	int sz = 1, mx_sz = 0;
	for (int v:graf[u]) {
		if (v == par[v]) continue;
		par[v]=u;
		gl[v]=gl[u]+1;
		int t_sz = dfs(v);
		if (t_sz > mx_sz)
			mx_sz=t_sz, heavy[u]=v;
		sz+=t_sz;
	}
	return sz;
}

void hld(int u, int id)
{
	skp[u]=id;
	pos[u]=hsz[id]++;
	if (heavy[u] != -1)
		hld(heavy[u], id);
	for (int v:graf[u]) {
		if (v==heavy[u] || v == par[u]) continue;
		hld(v, m++);
	}
}

int upd(int v, int dm, int dp) {
	while (1)
	{
		int t_sk = skp[v];
		int cm, cp;
		seg[t_sk].get(cm, cp);
		seg[t_sk].add(pos[v], dm, dp);
		int nm, np;
		seg[t_sk].get(nm, np);
		dm = nm-cm;
		dp = np-cp;
		if (v==0)
			break;
	}
	int mc, p;
	seg[0].get(mc, p);
	return min(mc, p);
}

void initialize(int n, vector<int> a, vector<int> b)
{
	memset(heavy, -1, sizeof(heavy));
	for (int i = 0; i < n-1; i++)
	{
		graf[a[i]-1].push_back(b[i]-1);
		graf[b[i]-1].push_back(a[i]-1);
	}
	dfs(0);
	hld(0, m++);
	for (int i = 0; i < m; i++)
		seg[i] = SegT(hsz[i]);
}

int cat(int v)
{
	v--;
	hut[v] = 1;
	return upd(v, 0, inf);
}

int dog(int v)
{
	v--;
	hut[v] = 2;
	return upd(v, inf, 0);
}

int neighbor(int v)
{
	v--;
	int r = 0;
	if (hut[v] == 1)
		r = upd(v, 0, -inf);
	else if (hut[v] == 2)
		r = upd(v, -inf, 0);
	hut[v] = 0;
	return r;
}

// int main() {
// 	return 0;
// }

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