Submission #99308

#	Time	Username	Problem	Language	Result	Execution time	Memory
99308		youngyojun	Cats or Dogs (JOI18_catdog)	C++11	100 / 100	380 ms	20916 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define INF (0x3f3f3f3f)
using namespace std;

const int MAXN = 100055;

static int _int[MAXN<<5], *_intp=_int;
inline int* newint(const unsigned int SZ) {
	_intp += SZ;
	return _intp - SZ;
}

struct HLD {
	int *DCC, *DCD, *DDC, *DDD;
	int *CC, *CD;
	int n, MX, pc, pd;

	void init(int _n) {
		n = _n;
		for(MX = 1; MX < n; MX <<= 1);
		CC = newint(n);
		CD = newint(n);
		DCC = newint(MX<<1);
		DCD = newint(MX<<1);
		DDC = newint(MX<<1);
		DDD = newint(MX<<1);
		fill(DCD+1, DCD+MX, 1);
		fill(DDC+1, DDC+MX, 1);
		fill(DCD+MX, DCD+(MX<<1), INF);
		fill(DDC+MX, DDC+(MX<<1), INF);
	}

	void upd(int i) {
		DCC[i+MX] = CC[i];
		DDD[i+MX] = CD[i];
		for(i = (i+MX)>>1; i; i >>= 1) {
			int l = i<<1, r = l|1;
			DCC[i] = min({INF, DCC[l]+DCC[r], DCD[l]+DDC[r]
							, DCC[l]+DDC[r]+1, DCD[l]+DCC[r]+1});
			DDD[i] = min({INF, DDD[l]+DDD[r], DDC[l]+DCD[r]
							, DDD[l]+DCD[r]+1, DDC[l]+DDD[r]+1});
			DCD[i] = min({INF, DCC[l]+DCD[r], DCD[l]+DDD[r]
							, DCC[l]+DDD[r]+1, DCD[l]+DCD[r]+1});
			DDC[i] = min({INF, DDD[l]+DDC[r], DDC[l]+DCC[r]
							, DDD[l]+DCC[r]+1, DDC[l]+DDC[r]+1});
			if(!DCD[i]) DCD[i] = 1;
			if(!DDC[i]) DDC[i] = 1;
		}
	}
	int get() { return min({DCC[1], DCD[1], DDC[1], DDD[1]}); }
} hld[MAXN];

vector<int> G[MAXN];

int SC[MAXN], SD[MAXN];
int HI[MAXN], HJ[MAXN], HC[MAXN], HR[MAXN], Hn;
int prt[MAXN], dep[MAXN], cnt[MAXN];
bitset<MAXN> chk, isc;

int N, Q;

void g(int v) {
	auto &V = hld[HI[v]];
	int j = HJ[v];
	V.CC[j] = SC[v];
	V.CD[j] = SD[v];
	if(chk[v]) (isc[v] ? V.CD[j] : V.CC[j]) = INF;
}
void f(int v) {
	for(int p, j; v; v = p) {
		g(v);
		auto &V = hld[HI[v]];
		j = HJ[v]; p = prt[HR[HI[v]]];
		V.upd(j);
		SC[p] -= min(V.pc, V.pd+1);
		SD[p] -= min(V.pd, V.pc+1);
		V.pc = min(V.DCC[1], V.DCD[1]);
		V.pd = min(V.DDC[1], V.DDD[1]);
		SC[p] += min(V.pc, V.pd+1);
		SD[p] += min(V.pd, V.pc+1);
	}
}

void hfs(int i) {
	HC[HI[i]]++;
	int hi = -1, hc = 0;
	for(int v : G[i])
		if(v != prt[i] && hc < cnt[v]) {
			hi = v; hc = cnt[v];
		}
	if(!hc) return;
	HI[hi] = HI[i];
	HJ[hi] = HJ[i]+1;
	for(int v : G[i]) if(v != prt[i]) {
		if(v != hi) {
			HI[v] = ++Hn;
			HR[Hn] = v;
		}
		hfs(v);
	}
}
void dfs(int i) {
	cnt[i] = 1;
	for(int v : G[i]) if(!dep[v]) {
		dep[v] = dep[i] + 1;
		prt[v] = i;
		dfs(v);
		cnt[i] += cnt[v];
	}
}

void initialize(int N, std::vector<int> _A, std::vector<int> _B) {
	::N = N;
	for(int i = 1, a, b; i < N; i++) {
		a = _A[i-1]; b = _B[i-1];
		G[a].eb(b);
		G[b].eb(a);
	}

	dep[1] = 1; dfs(1);
	HI[1] = HR[1] = Hn = 1; hfs(1);
	for(int i = 1; i <= Hn; i++) hld[i].init(HC[i]);
}

int cat(int v) {
	chk[v] = isc[v] = true;
	f(v);
	return hld[1].get();
}

int dog(int v) {
	chk[v] = true; isc[v] = false;
	f(v);
	return hld[1].get();
}

int neighbor(int v) {
	chk[v] = isc[v] = false;
	f(v);
	return hld[1].get();
}

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