Submission #776718

#	Time	Username	Problem	Language	Result	Execution time	Memory
776718		ymm	Cats or Dogs (JOI18_catdog)	C++17	38 / 100	3053 ms	12232 KiB

catdog

#include "catdog.h"

#include <bits/stdc++.h>
#define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const int N = 100'010;
int col[N], cntcol[N][3];
vector<int> A[N];
int cpar[N];
int cnt[N];
bool vis[N];

void dfs(int v, int p) {
	cnt[v] = 1;
	for (int u : A[v]) {
		if (u == p || vis[u])
			continue;
		dfs(u, v);
		cnt[v] += cnt[u];
	}
}

int centroid(int v, int n)
{
	for (int u : A[v]) {
		if (vis[u] || cnt[u] > cnt[v])
			continue;
		if (cnt[u]*2 > n)
			return centroid(u, n);
	}
	return v;
}

int decomp(int v)
{
	dfs(v, -1);
	v = centroid(v, cnt[v]);
	vis[v] = 1;
	for (int u : A[v]) {
		if (vis[u])
			continue;
		u = decomp(u);
		cpar[u] = v;
	}
	return v;
}

void dfsdard(int v, int p)
{
	cpar[v] = p;
	for (int u : A[v])
		if (u != p)
			dfsdard(u, v);
}

void initialize(int N, std::vector<int> V, std::vector<int> U) {
	Loop (i,0,N-1) {
		V[i]--; U[i]--;
		A[V[i]].push_back(U[i]);
		A[U[i]].push_back(V[i]);
	}
	dfsdard(0, -1);
	//int rt = decomp(0);
	//cpar[rt] = -1;
}

int calc(int v) { return col[v] == 0? min(cntcol[v][1], cntcol[v][2]): cntcol[v][3-col[v]]; }
int calccol(int v) {
	if (col[v])
		return col[v];
	if (cntcol[v][1] < cntcol[v][2])
		return 2;
	if (cntcol[v][1] == cntcol[v][2])
		return 0;
	if (cntcol[v][1] > cntcol[v][2])
		return 1;
	assert(false);
}


int Ans = 0;

void ch(int v, int from, int to)
{
	int c0 = calccol(v);
	Ans -= calc(v);
	cntcol[v][from]--;
	cntcol[v][to]++;
	Ans += calc(v);
	int c1 = calccol(v);
	if (cpar[v] != -1 && c0 != c1)
		ch(cpar[v], c0, c1);
}

int cat(int v) {
	--v;
	int c0 = calccol(v);
	Ans -= calc(v);
	col[v] = 1;
	Ans += calc(v);
	int c1 = calccol(v);
	if (cpar[v] != -1 && c0 != c1)
		ch(cpar[v], c0, c1);
	return Ans;
}

int dog(int v) {
	--v;
	int c0 = calccol(v);
	Ans -= calc(v);
	col[v] = 2;
	Ans += calc(v);
	int c1 = calccol(v);
	if (cpar[v] != -1 && c0 != c1)
		ch(cpar[v], c0, c1);
	return Ans;
}

int neighbor(int v) {
	--v;
	int c0 = calccol(v);
	Ans -= calc(v);
	col[v] = 0;
	Ans += calc(v);
	int c1 = calccol(v);
	if (cpar[v] != -1 && c0 != c1)
		ch(cpar[v], c0, c1);
	return Ans;
}

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