Submission #101808

#	Time	Username	Problem	Language	Result	Execution time	Memory
101808		KCSC	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	387 ms	36732 KiB

catdog

#include <bits/stdc++.h>
using namespace std;

const int DIM = 100005;
const int INF = 1000000005;

struct Matrix {
	long long dp[2][2];
	
	Matrix operator *(const Matrix &other) {
		Matrix result;
		for (int i1 = 0; i1 <= 1; ++i1) {
		for (int j2 = 0; j2 <= 1; ++j2) {
			long long aux = 1LL * INF * INF;
			for (int j1 = 0; j1 <= 1; ++j1) {
			for (int i2 = 0; i2 <= 1; ++i2) {
				aux = min(aux, (*this).dp[i1][j1] + other.dp[i2][j2] + (j1 != i2)); } }
			result.dp[i1][j2] = aux; } } 
		return result; }
}; 

int szt[DIM], msk[DIM], wtc[DIM], pic[DIM], ftc[DIM];
vector<Matrix> sgt[DIM]; vector<int> chn[DIM], edg[DIM];

void preDfs(int x, int f, int &m) {	
	int big = 0; szt[x] = 1;
	for (int y : edg[x]) if (y != f) {
		preDfs(y, x, m); szt[x] += szt[y];
		if (!big or szt[big] < szt[y]) {
			big = y; } }
	if (!big) {
		wtc[x] = ++m; }
	else {
		wtc[x] = wtc[big];
		for (int y : edg[x]) 
			if (y != f and y != big) {
				ftc[wtc[y]] = x; } }
	chn[wtc[x]].push_back(x); }

void build(int ch, int nd, int le, int ri) {
	if (le == ri) {
		sgt[ch][nd].dp[0][0] = sgt[ch][nd].dp[1][1] = 0;
		sgt[ch][nd].dp[0][1] = sgt[ch][nd].dp[1][0] = INF; }
	else {
		int md = (le + ri) >> 1;
		build(ch, nd << 1, le, md);
		build(ch, nd << 1 | 1, md + 1, ri);
		sgt[ch][nd] = sgt[ch][nd << 1] * sgt[ch][nd << 1 | 1]; } }

void update(int ch, int nd, int le, int ri, int ps, long long vl, long long vr) {
	if (le == ri) {
		sgt[ch][nd].dp[0][0] += vl; sgt[ch][nd].dp[1][1] += vr; }
	else {
		int md = (le + ri) >> 1;
		if (ps <= md) {
			update(ch, nd << 1, le, md, ps, vl, vr); }
		else {
			update(ch, nd << 1 | 1, md + 1, ri, ps, vl, vr); }
		sgt[ch][nd] = sgt[ch][nd << 1] * sgt[ch][nd << 1 | 1]; } }

void updateChain(int x, long long vl, long long vr) {
	int ch = wtc[x];
	long long vl1 = min(sgt[ch][1].dp[0][0], sgt[ch][1].dp[0][1]),
			  vr1 = min(sgt[ch][1].dp[1][0], sgt[ch][1].dp[1][1]);
	update(ch, 1, 1, chn[ch][0], pic[x], vl, vr);
	long long vl2 = min(sgt[ch][1].dp[0][0], sgt[ch][1].dp[0][1]),
			  vr2 = min(sgt[ch][1].dp[1][0], sgt[ch][1].dp[1][1]);
 	if (ftc[ch]) {
		updateChain(ftc[ch], min(vl2, vr2 + 1) - min(vl1, vr1 + 1), 
							 min(vr2, vl2 + 1) - min(vr1, vl1 + 1)); } }

void initialize(int n, vector<int> end1, vector<int> end2) {
	for (int i = 1; i < n; ++i) {
		int x = end1[i - 1], y = end2[i - 1];
		edg[x].push_back(y); edg[y].push_back(x); }
	int m = 0; preDfs(1, 0, m);
	for (int i = 1; i <= m; ++i) {
		chn[i].push_back(chn[i].size());
		reverse(chn[i].begin(), chn[i].end());
		sgt[i].resize(chn[i][0] << 2);
		for (int j = 1; j <= chn[i][0]; ++j) {	
			pic[chn[i][j]] = j; }
		build(i, 1, 1, chn[i][0]);  } }

inline int answer(void) {
	int ch = wtc[1]; long long mn = 1LL * INF * INF;
	for (int i = 0; i <= 1; ++i) {
	for (int j = 0; j <= 1; ++j) {
		mn = min(mn, sgt[ch][1].dp[i][j]); } }
	return mn; }

int cat(int x) {
	updateChain(x, INF, 0); msk[x] = 1;
	return answer(); }

int dog(int x) {
	updateChain(x, 0, INF); msk[x] = 2; 
	return answer(); }

int neighbor(int x) {
	if (msk[x] == 1) {
		updateChain(x, -INF, 0); }
	else {
		updateChain(x, 0, -INF); }
	return answer(); }

#ifdef HOME
int main(void) {
	freopen("catdog.in", "r", stdin);
	freopen("catdog.out", "w", stdout);
	int n; cin >> n;
	vector<int> a(n - 1), b(n - 1);
	for (int i = 0; i <= n - 2; ++i) {
		cin >> a[i] >> b[i]; }
	initialize(n, a, b);
	int q; cin >> q;
	while (q--) {
		int t, x; cin >> t >> x;
		if (t == 1) { cout << cat(x) << endl; }
		if (t == 2) { cout << dog(x) << endl; }
		if (t == 3) { cout << neighbor(x) << endl; } }
	return 0; }
#endif

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