Submission #527396

#	Time	Username	Problem	Language	Result	Execution time	Memory
527396		Qingyu	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	802 ms	33724 KiB

catdog

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

const int N = 1e5 + 50;
int n, fa[N], top[N], dep[N], g[N][2], siz[N], son[N], dfn[N], dp[N][2], tot, tail[N], delta[N][2], id[N];
std::vector<int> G[N];

inline int lc(int o) { return o << 1; }
inline int rc(int o) { return o << 1 | 1; }

struct matrix_t {
	int M[2][2], n, m;
	matrix_t(int n = 0, int m = 0) : n(n), m(m) {
		memset(M, 0x3f, sizeof M);
	}
	void set(int g0, int g1) {
		M[0][0] = g0, M[1][0] = g0 + 1;
		M[0][1] = g1 + 1, M[1][1] = g1;
	}
} gm[N], tr[N << 2];

matrix_t operator*(const matrix_t &lhs, const matrix_t &rhs) {
	matrix_t res;
	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 2; ++j)
			for (int k = 0; k < 2; ++k)
				res.M[i][j] = std::min(res.M[i][j], lhs.M[i][k] + rhs.M[k][j]);
	return res;
}

void dfs(int x, int f, int d) {
	fa[x] = f, dep[x] = d, siz[x] = 1;
	int mx = -1;
	dp[x][0] = dp[x][1] = 0;
	for (int y : G[x])
		if (y != f) {
			dfs(y, x, d + 1);
			siz[x] += siz[y];
			if (siz[y] > mx) {
				mx = siz[y];
				son[x] = y;
			}
			dp[x][0] = std::min(dp[y][0], dp[y][1] + 1);
			dp[x][1] = std::min(dp[y][1], dp[y][0] + 1);
		}
}

void dfs2(int x, int topf) {
	dfn[x] = ++tot;
	id[tot] = x;
	top[x] = topf;
	tail[topf] = x;
	g[x][0] = g[x][1] = 0;
	if (son[x]) {
		dfs2(son[x], topf);
		for (int y : G[x])
			if (y != fa[x] && y != son[x]) {
				dfs2(y, y);
				g[x][0] += std::min(dp[y][0], dp[y][1] + 1);
				g[x][1] += std::min(dp[y][1], dp[y][0] + 1);
			}
	}
	gm[x].set(g[x][0], g[x][1]);
}

void push_up(int o) {
	tr[o] = tr[rc(o)] * tr[lc(o)];
}

void build(int o, int l, int r) {
	if (l == r) {
		tr[o] = gm[id[l]];
	}
	else {
		const int mid = l + r >> 1;
		build(lc(o), l, mid);
		build(rc(o), mid + 1, r);
		push_up(o);
	}
}

matrix_t query(int o, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr)
		return tr[o];
	const int mid = l + r >> 1;
	if (qr <= mid) return query(lc(o), l, mid, ql, qr);
	if (ql > mid) return query(rc(o), mid + 1, r, ql, qr);
	return query(rc(o), mid + 1, r, ql, qr) * query(lc(o), l, mid, ql, qr);
}

void modify(int o, int l, int r, int p) {
	if (l == r) {
		tr[o] = gm[id[l]];
	}
	else {
		const int mid = l + r >> 1;
		if (p <= mid) modify(lc(o), l, mid, p);
		else modify(rc(o), mid + 1, r, p);
		push_up(o);
	}
}

void initialize(int N, std::vector<int> A, std::vector<int> B) {
	n = N;
	for (int i = 0; i < A.size(); ++i) {
		G[A[i]].push_back(B[i]);
		G[B[i]].push_back(A[i]);
	}
	dfs(1, 0, 1);
	dfs2(1, 1);
	assert(tot == N);
	build(1, 1, N);
}

void cancel(int v) {
	g[v][0] -= delta[v][0];
	g[v][1] -= delta[v][1];
}
void update(int v) {
	g[v][0] += delta[v][0];
	g[v][1] += delta[v][1];
	gm[v].set(g[v][0], g[v][1]);
}

void travel(int x) {
	while (x) {
		matrix_t old = query(1, 1, n, dfn[top[x]], dfn[tail[top[x]]]);
		modify(1, 1, n, dfn[x]);
		matrix_t now = query(1, 1, n, dfn[top[x]], dfn[tail[top[x]]]);
		x = fa[top[x]];
		if (!x) break;
		{
			int f0 = std::min(old.M[0][0], old.M[1][0]);
			int f1 = std::min(old.M[0][1], old.M[1][1]);
			g[x][0] -= std::min(f0, f1 + 1);
			g[x][1] -= std::min(f1, f0 + 1);
		}
		{
			int f0 = std::min(now.M[0][0], now.M[1][0]);
			int f1 = std::min(now.M[0][1], now.M[1][1]);
			g[x][0] += std::min(f0, f1 + 1);
			g[x][1] += std::min(f1, f0 + 1);
		}
		gm[x].set(g[x][0], g[x][1]);
	}
}
int getans() {
	auto M = query(1, 1, n, dfn[1], dfn[tail[top[1]]]);
	int ans = std::min(M.M[0][0], M.M[0][1]);
	ans = std::min(ans, M.M[1][0]);
	ans = std::min(ans, M.M[1][1]);
	return ans;
}
int cat(int v) {
	cancel(v);
	delta[v][0] = 0, delta[v][1] = 0x3f3f3f3f;
	update(v);
	travel(v);
	return getans();
}

int dog(int v) {
	cancel(v);
	delta[v][0] = 0x3f3f3f3f, delta[v][1] = 0;
	update(v);
	travel(v);
	return getans();
}

int neighbor(int v) {
	cancel(v);
	delta[v][0] = delta[v][1] = 0;
	update(v);
	travel(v);
	return getans();
}

Compilation message (stderr)

catdog.cpp: In function 'void build(int, int, int)':
catdog.cpp:75:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |   const int mid = l + r >> 1;
      |                   ~~^~~
catdog.cpp: In function 'matrix_t query(int, int, int, int, int)':
catdog.cpp:85:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |  const int mid = l + r >> 1;
      |                  ~~^~~
catdog.cpp: In function 'void modify(int, int, int, int)':
catdog.cpp:96:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |   const int mid = l + r >> 1;
      |                   ~~^~~
catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:105:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |  for (int i = 0; i < A.size(); ++i) {
      |                  ~~^~~~~~~~~~

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