Submission #1150553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150553		pinbu	Cats or Dogs (JOI18_catdog)	C++20	100 / 100	191 ms	28232 KiB

catdog

// What a ~tricky problem!

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

const int MxN = 100005, oo = 1e9 + 7;
void mini(int &X, int Y) {
    if (X > Y) X = Y;
}

using node = array<array<int, 2>, 2>;
node operator + (const node &A, const node &B) {
    node res = {{{oo, oo}, {oo, oo}}};
    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++) {
                    mini(res[i][j], A[i][k] + B[l][j] + (k ^ l));
                }
            }
        }
    }
    return res;
}
struct ST {
	int n;
	vector<node> nut;
	void build(int id, int l, int r) {
		if (l == r) {
			nut[id][0][0] = nut[id][1][1] = 0;
			nut[id][0][1] = nut[id][1][0] = oo;
			return;
		}
		
		int mid = l + r >> 1;
		build(id << 1, l, mid);
		build(id << 1 | 1, mid + 1, r);
		nut[id] = nut[id << 1] + nut[id << 1 | 1];
	}
	void rsz(int sz) {
		n = sz;
		nut.resize(4 * sz);
		build(1, 1, sz);
	}
	void update(int i, int v1, int v2, int id, int l, int r) {
		if (l == r) {
			nut[id][0][0] += v1;
			nut[id][1][1] += v2;
			return;
		}
		
		int mid = l + r >> 1;
		i <= mid ? update(i, v1, v2, id << 1, l, mid) : update(i, v1, v2, id << 1 | 1, mid + 1, r);
		nut[id] = nut[id << 1] + nut[id << 1 | 1];
	}
	void update(int i, int v1, int v2) {
		update(i, v1, v2, 1, 1, n);
	}
	pair<int, int> get(void) {
		node t = nut[1];
		int a = t[0][0], b = t[0][1], c = t[1][0], d = t[1][1];
		return {min({a, b, c + 1, d + 1}), min({a + 1, b + 1, c, d})};
	}
} tri[MxN];

vector<int> adj[MxN];
int par[MxN], sz[MxN];
void DFS(int u, int p) {
	sz[u] = 1;
	pair<int, int> best = {-1, -1};
	int i = -1;
	for (int v: adj[u]) {
		i++;
		if (v == p) continue;
		par[v] = u;
		DFS(v, u);
		sz[u] += sz[v];
		best = max(best, {sz[v], i});
	}
	if (best.first > 0) swap(adj[u][0], adj[u][best.second]);
}
int head[MxN], st[MxN], timer = 0, cnt[MxN];
void HLD(int u, int p, int h) {
	head[u] = h;
	cnt[h]++;
	st[u] = ++timer;
	int nxt = -1;
	if (adj[u].size() && adj[u][0] != par[u]) nxt = adj[u][0];
	if (nxt > 0) HLD(nxt, u, h);
	for (int v: adj[u]) if (v != nxt && v != p) HLD(v, u, v);
}
void initialize(int n, std::vector<int> A, std::vector<int> B) {
    for (int i = 0; i < n - 1; i++) {
        int u = A[i], v = B[i];
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    DFS(1, 0);
    HLD(1, 0, 1);
    for (int h = 1; h <= n; h++) if (cnt[h]) tri[h].rsz(cnt[h]);
}


int cur[MxN];
int update(int u, int c) {
	int uwu = u;
	int v1, v2;
	if (c == 1) tie(v1, v2) = make_tuple(0, oo);
	else if (c == 2) tie(v1, v2) = make_tuple(oo, 0);
	else tie(v1, v2) = make_tuple(-(cur[u] == 2) * oo, -(cur[u] == 1) * oo);
	while (u) {
		int h = head[u];
		pair<int, int> p1 = tri[h].get();
		tri[h].update(st[u] - st[h] + 1, v1, v2);
		pair<int, int> p2 = tri[h].get();
		v1 = p2.first - p1.first; v2 = p2.second - p1.second;
		u = par[h];
	}
	cur[uwu] = c;
	node t = tri[1].nut[1];
	return min({t[0][0], t[0][1], t[1][0], t[1][1]});
}
int cat(int u) {
	return update(u, 1);
}
int dog(int u) {
	return update(u, 2);
}
int neighbor(int u) {
	return update(u, 3);
}

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