Submission #102577

#	Time	Username	Problem	Language	Result	Execution time	Memory
102577		IOrtroiii	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	513 ms	26784 KiB

catdog

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

const int N = 100100;
const int inf = 1e9;

struct Arr {
	array<array<int, 2>, 2> a;
	Arr() { a[0][0] = a[0][1] = a[1][0] = a[1][1] = inf; };
	array<int, 2>& operator [](int id) { return a[id]; }
};

Arr mrg(Arr x,Arr y) {
	Arr z;
	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) {
					z[i][l] = min(z[i][l], x[i][j] + (j ^ k) + y[k][l]);
				} 
			}
		}
	}
	return z;
}

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

struct SegTree {
	vector<Arr> t;
	void resize(int n) {
		t.resize((n + 1) << 2);
	}
	void build(int v,int l,int r) {
		if (l == r) {
			t[v][0][0] = t[v][1][1] = 0;
			return;
		}
		build(v << 1, l, md);
		build(v << 1 | 1, md + 1, r);
		t[v] = mrg(t[v << 1], t[v << 1 | 1]);
	}
	void add(int v,int l,int r,int p,int v0,int v1) {
		if (p < l || p > r) return;
		if (l == r) {
			t[v][0][0] += v0;
			t[v][1][1] += v1;
			return; 
		}
		add(v << 1, l, md, p, v0, v1);
		add(v << 1 | 1, md + 1, r, p, v0, v1);
		t[v] = mrg(t[v << 1], t[v << 1 | 1]);
	}
} t[N];

int a[N];
vector<int> g[N];
int child[N];
int up[N], par[N];
int tin[N], tt;
int ll[N], rr[N];

void dfs(int u) {
	child[u] = 1;
	for (int v : g[u]) {
		if (v != par[u]) {
			par[v] = u;
			dfs(v);
			child[u] += child[v];
		}
	} 
}

void hld(int u,int root) {
	up[u] = root;
	tin[u] = ++tt;
	int nxt = 0;
	for (int v : g[u]) {
		if (v != par[u]) {
			if (child[v] > child[nxt]) {
				nxt = v;
			}
		}
	}
	if (nxt) {
		hld(nxt, root);
	}
	for (int v : g[u]) {
		if (v != par[u] && v != nxt) {
			hld(v, v);
		}
	}
}

void initialize(int n, vector<int> a,vector<int> b) {
	for (int i = 0; i < n - 1; ++i) {
		g[a[i]].push_back(b[i]);
		g[b[i]].push_back(a[i]);
	}
	dfs(1);
	hld(1, 1);
	for (int i = 1; i <= n; ++i) ll[i] = n, rr[i] = 1;
	for (int i = 1; i <= n; ++i) {
		ll[up[i]] = min(ll[up[i]], tin[i]);
		rr[up[i]] = max(rr[up[i]], tin[i]);
	}
	for (int i = 1; i <= n; ++i) {
		if (up[i] == i) {
			t[i].resize(rr[i] - ll[i] + 1);
			t[i].build(1, ll[i], rr[i]);
		}
	}
}

void add(int u,int v0,int v1) {
	while (up[u] != up[1]) {
		int v = up[u];
		int nw[2], nx[2];
		nw[0] = nw[1] = inf;
		for (int i = 0; i < 2; ++i) {
			for (int j = 0; j < 2; ++j) {
				for (int k = 0; k < 2; ++k) {
					nw[i] = min(nw[i], (i ^ j) + t[v].t[1][j][k]);
				}
			} 
		} 
		t[v].add(1, ll[v], rr[v], tin[u], v0, v1);
		nx[0] = nx[1] = inf;
		for (int i = 0; i < 2; ++i) {
			for (int j = 0; j < 2; ++j) {
				for (int k = 0; k < 2; ++k) {
					nx[i] = min(nx[i], (i ^ j) + t[v].t[1][j][k]);
				}
			} 
		} 
		u = par[v], v0 = nx[0] - nw[0], v1 = nx[1] - nw[1];
	}
	t[1].add(1, ll[1], rr[1], tin[u], v0, v1);
}

int go() {
	int ans = inf;
	for (int i = 0; i < 2; ++i) {
		for (int j = 0; j < 2; ++j) {
			ans = min(ans, t[1].t[1][i][j]);
		}
	}
	return ans;
}

int cat(int u) {
	a[u] = 0; add(u, 0, inf); return go();
}

int dog(int u) {
	a[u] = 1; add(u, inf, 0); return go();
}

int neighbor(int u) {
	if (a[u]) add(u, -inf, 0);
	else add(u, 0, -inf);
	return go();
}

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