Submission #67477

#	Time	Username	Problem	Language	Result	Execution time	Memory
67477		aome	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	473 ms	81024 KiB

catdog

#include "catdog.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;
const int INF = 1e9;

int n;
int a[N];
int par[N], nchild[N];
int T, head[N], pos[N], L[N], R[N];
vector<int> G[N];

struct Node {
	int f[2][2];

	Node() {
		f[0][0] = f[1][1] = f[0][1] = f[1][0] = INF;
 	}

 	Node operator + (Node x) {
 		Node ret;
 		for (int i = 0; i < 2; ++i) {
 			for (int j = 0; j < 2; ++j) {
 				for (int k = 0; k < 2; ++k) {
 					for (int l = 0; l < 2; ++l) {
 						ret.f[i][l] = min(ret.f[i][l], f[i][j] + x.f[k][l] + (j ^ k));
 					}
 				}
 			}
 		}
 		return ret;
 	}
};

struct SegmentTree {
	vector<Node> T;

	#define mid ((l + r) >> 1)

	void build(int i, int l, int r) {
		if (l == r) {
			T[i].f[0][0] = T[i].f[1][1] = 0; return;
		}
		build(i << 1, l, mid);
		build(i << 1 | 1, mid + 1, r);
		T[i] = T[i << 1] + T[i << 1 | 1];
	}

	void upd(int i, int l, int r, int p, int v0, int v1) {
		if (l == r) {
			T[i].f[0][0] += v0, T[i].f[1][1] += v1; return;
		}
		if (mid >= p) upd(i << 1, l, mid, p, v0, v1);
		else upd(i << 1 | 1, mid + 1, r, p, v0, v1);
		T[i] = T[i << 1] + T[i << 1 | 1];
	} 

	#undef mid
} IT[N];

void dfs(int u) {
	nchild[u] = 1;
	for (auto v : G[u]) {
		if (v == par[u]) continue;
		par[v] = u, dfs(v), nchild[u] += nchild[v];
	}
}

void dfsHld(int u) {
	if (head[u] == -1) head[u] = u;
	pos[u] = ++T;
	int nx = -1;
	for (auto v : G[u]) {
		if (v == par[u]) continue;
		if (nx == -1 || nchild[nx] < nchild[v]) nx = v;
	}
	if (nx != -1) { head[nx] = head[u], dfsHld(nx); }
	for (auto v : G[u]) {
		if (v == par[u] || v == nx) continue; dfsHld(v);
	}
}

void initialize(int _n, vector<int> A, vector<int> B) {
	n = _n;
	for (int i = 0; i < (n - 1); ++i) {
		--A[i], --B[i];
		G[A[i]].push_back(B[i]), G[B[i]].push_back(A[i]);
	}
	memset(head, -1, sizeof head);
	dfs(0), dfsHld(0);
	for (int i = 0; i < n; ++i) L[i] = n, R[i] = 1;
	for (int i = 0; i < n; ++i) {
		L[head[i]] = min(L[head[i]], pos[i]);
		R[head[i]] = max(R[head[i]], pos[i]);
	}
	for (int i = 0; i < n; ++i) {
		if (head[i] != i) continue;
		int tmp = R[i] - L[i] + 1;
		IT[i].T.assign(tmp * 4 + 5, Node());
		IT[i].build(1, L[i], R[i]);
	}
}

void upd(int u, int v0, int v1) {
	while (head[u] != head[0]) {
		int p = head[u];
		int x[2], y[2];
		x[0] = x[1] = INF;
		for (int i = 0; i < 2; ++i) {
			for (int j = 0; j < 2; ++j) {
				for (int k = 0; k < 2; ++k) {
					x[i] = min(x[i], IT[p].T[1].f[j][k] + (i ^ j));
				}
			}
		}
		IT[p].upd(1, L[p], R[p], pos[u], v0, v1);
		y[0] = y[1] = INF;
		for (int i = 0; i < 2; ++i) {
			for (int j = 0; j < 2; ++j) {
				for (int k = 0; k < 2; ++k) {
					y[i] = min(y[i], IT[p].T[1].f[j][k] + (i ^ j));
				}
			}
		}
		u = par[p], v0 = y[0] - x[0], v1 = y[1] - x[1];
	}
	IT[0].upd(1, L[0], R[0], pos[u], v0, v1);
}

int get() {
	int ret = INF;
	for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) {
		ret = min(ret, IT[0].T[1].f[i][j]);
	}
	return ret;
}

int cat(int v) {
	--v, a[v] = 0, upd(v, 0, INF); return get();
}

int dog(int v) {
	--v, a[v] = 1, upd(v, INF, 0); return get();
}

int neighbor(int v) {
	--v; if (!a[v]) upd(v, 0, -INF); else upd(v, -INF, 0); return get();
}

Compilation message (stderr)

catdog.cpp: In function 'void dfsHld(int)':
catdog.cpp:82:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if (v == par[u] || v == nx) continue; dfsHld(v);
   ^~
catdog.cpp:82:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   if (v == par[u] || v == nx) continue; dfsHld(v);
                                         ^~~~~~

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