Submission #848019

#	Time	Username	Problem	Language	Result	Execution time	Memory
848019		LeonaRaging	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	484 ms	28280 KiB

catdog

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

#define pb push_back

const int maxn = 1e5 + 4;
const int INF = 1e9;

int n, sz[maxn], R[maxn], B[maxn], col[maxn], par[maxn], id[maxn];
int chain[maxn], head[maxn], from[maxn], to[maxn], tin[maxn];
vector<int> adj[maxn];

struct Node {
	int a[2][2];
	Node() {
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++)
				a[i][j] = INF;
	}
};

struct seg_tree {
	vector<Node> t;
	seg_tree() {
		t.resize(4 * maxn);
	}
	Node merge(Node L, Node R) {
		Node res;
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++)
				for (int x = 0; x < 2; x++)
					for (int y = 0; y < 2; y++)
						res.a[i][j] = min(res.a[i][j], L.a[i][x] + R.a[y][j] + (x != y));
		return res;
	}
	void update(int pos, int v = 1, int l = 1, int r = maxn - 1) {
		if (l == r) {
			t[v].a[0][0] = (col[id[l]] == 1 ? INF : R[id[l]]);
			t[v].a[1][1] = (col[id[l]] == 0 ? INF : B[id[l]]);
			t[v].a[0][1] = t[v].a[1][0] = INF;
			return;
		}
		int m = (l + r) / 2;
		if (pos <= m) update(pos, 2 * v, l, m);
		else update(pos, 2 * v + 1, m + 1, r);
		t[v] = merge(t[2 * v], t[2 * v + 1]);
	}
	Node get(int l, int r, int v = 1, int tl = 1, int tr = maxn - 1) {
		if (tl >= l && tr <= r) return t[v];
		int m = (tl + tr) / 2;
		if (r <= m) return get(l, r, 2 * v, tl, m);
		else if (l > m) return get(l, r, 2 * v + 1, m + 1, tr);
		else return merge(get(l, r, 2 * v, tl, m), get(l, r, 2 * v + 1, m + 1, tr));
	}
} IT;

void dfs(int u, int p) {
	sz[u] = 1;
	for (int v : adj[u]) if (v != p) {
		par[v] = u;
		dfs(v, u);
		sz[u] += sz[v];
	}
}

void hld(int u) {
	tin[u] = ++tin[0];
	id[tin[0]] = u;
	chain[u] = chain[0];
	if (!head[chain[0]]) head[chain[0]] = u;
	int mx = 0;
	for (int v : adj[u])
		if (v != par[u] && sz[v] > sz[mx])
			mx = v;
	if (mx) hld(mx);
	for (int v : adj[u])
		if (v != par[u] && v != mx) {
			chain[0]++;
			hld(v);
		}
}

void update(int v) {
	while (v) {
		int u = par[head[chain[v]]];
		Node cur = IT.get(from[chain[v]], to[chain[v]]);
		R[u] -= min({cur.a[0][0], cur.a[0][1], cur.a[1][0] + 1, cur.a[1][1] + 1});
		B[u] -= min({cur.a[0][0] + 1, cur.a[0][1] + 1, cur.a[1][0], cur.a[1][1]});
		IT.update(tin[v]);
		cur = IT.get(from[chain[v]], to[chain[v]]);
		R[u] += min({cur.a[0][0], cur.a[0][1], cur.a[1][0] + 1, cur.a[1][1] + 1});
		B[u] += min({cur.a[0][0] + 1, cur.a[0][1] + 1, cur.a[1][0], cur.a[1][1]});
		v = u;
	}
}

int get() {
	Node cur = IT.get(from[0], to[0]);
	int res = INF;
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			res = min(res, cur.a[i][j]);
	return res;
}

void initialize(int N, vector<int> A, vector<int> B) {
	n = N;
	for (int i = 0; i < n - 1; i++) {
		adj[A[i]].pb(B[i]);
		adj[B[i]].pb(A[i]);
	}
	dfs(1, 0);
	hld(1);
	for (int i = 0; i <= chain[0]; i++)
		from[i] = INF;
	for (int i = 1; i <= n; i++) {
		from[chain[i]] = min(from[chain[i]], tin[i]);
		to[chain[i]] = max(to[chain[i]], tin[i]);
		col[i] = -1;
	}
	for (int i = 1; i <= n; i++)
		IT.update(i);
}

int cat(int v) {
	col[v] = 0;
	update(v);
	return get();
}

int dog(int v) {
	col[v] = 1;
	update(v);
	return get();
}

int neighbor(int v) {
	col[v] = -1;
	update(v);
	return get();
}

// int main()
// {
	// ios::sync_with_stdio(0);
	// cin.tie(0); cout.tie(0);
	// if (fopen("Pets.INP", "r")) {
		// freopen("Pets.INP", "r", stdin);
		// freopen("Pets.OUT", "w", stdout);
	// }
	// cin >> n;
	// for (int i = 1, u, v; i < n; i++) {
		// cin >> u >> v;
		// adj[u].pb(v);
		// adj[v].pb(u);
	// }
	// dfs(1, 0);
	// hld(1);
	// for (int i = 0; i <= chain[0]; i++)
		// from[i] = INF;
	// for (int i = 1; i <= n; i++) {
		// from[chain[i]] = min(from[chain[i]], tin[i]);
		// to[chain[i]] = max(to[chain[i]], tin[i]);
		// col[i] = -1;
	// }
	// for (int i = 1; i <= n; i++)
		// IT.update(i);
	// int q; cin >> q;
	// while (q--) {
		// int t, u; cin >> t >> u;
		// if (t == 1) col[u] = 0;
		// if (t == 2) col[u] = 1;
		// if (t == 3) col[u] = -1;
		// update(u);
		// cout << get() << '\n';
	// }
// }

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