| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1109106 | dkim110807 | Cats or Dogs (JOI18_catdog) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using ll = long long;
constexpr int MAX = 100'001;
struct Node {
std::array<std::array<int, 2>, 2> dp{{{{0, 0}}, {{0, 0}}}};
friend Node operator+(const Node &left, const Node &right) {
Node ret{{{{{INT32_MAX, INT32_MAX}}, {{INT32_MAX, INT32_MAX}}}}};
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.dp[i][l] = std::min(ret.dp[i][l], left.dp[i][j] + right.dp[k][l] + (j != k));
}
}
}
}
return ret;
}
std::array<int, 2> &operator[](int i) {
return dp[i];
}
} tree[4 * MAX + 4];
struct Segtree {
void update(int node, int start, int end, int idx, Node v) {
if (idx < start || end < idx) return;
if (start == end) {
tree[node] = v;
return;
}
int mid = (start + end) >> 1;
update(node << 1, start, mid, idx, v), update(node << 1 | 1, mid + 1, end, idx, v);
tree[node] = tree[node << 1] + tree[node << 1 | 1];
}
Node query(int node, int start, int end, int left, int right) {
if (right < start || end < left) return {};
if (left <= start && end <= right) return tree[node];
int mid = (start + end) >> 1;
return query(node << 1, start, mid, left, right) + query(node << 1 | 1, mid + 1, end, left, right);
}
} seg;
struct HLD {
std::vector<int> graph[MAX + 1];
std::array<int, 2> light[MAX +
1]; // light[v][0] for 'v' in heavy edge : sum of all childs that are linked by light edge starting with '0' i.e. cat
int top[MAX + 1], bottom[MAX + 1], in[MAX + 1], depth[MAX + 1], sz[MAX + 1], parent[MAX + 1];
void add(int u, int v) {
graph[u].push_back(v), graph[v].push_back(u);
}
void init(int root = 1) {
dfs(root);
top[root] = root;
dfs2(root);
}
void dfs(int v = 1) {
sz[v] = 1;
for (auto &nv: graph[v]) {
parent[nv] = v, depth[nv] = depth[v] + 1;
graph[nv].erase(std::find(graph[nv].begin(), graph[nv].end(), v));
dfs(nv);
sz[v] += sz[nv];
if (sz[nv] > sz[graph[v][0]]) std::swap(nv, graph[v][0]);
}
}
void dfs2(int v = 1) {
static int dfs_num = 0;
in[v] = ++dfs_num;
for (const auto &nv: graph[v]) {
top[nv] = nv == graph[v][0] ? top[v] : nv;
dfs2(nv);
}
bottom[v] = graph[v].empty() ? v : bottom[graph[v][0]];
}
Node query(int u, int v) {
Node ret;
while (top[u] != top[v]) {
if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
int st = top[u];
ret = ret + seg.query(1, 1, MAX, in[st], in[u]);
u = parent[st];
}
if (depth[u] > depth[v]) std::swap(u, v);
ret = ret + seg.query(1, 1, MAX, in[u], in[v]);
return ret;
}
void update() {
}
} hld;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
int n, m;
std::cin >> n;
for (int i = n - 1, u, v; i--;) {
std::cin >> u >> v;
hld.add(u, v);
}
hld.init();
std::cin >> m;
// 0 : cat, 1 : dog, 2 : neighbor
std::vector<int> color(n + 1, 2);
auto update2 = [&](int v) {
seg.update(1, 1, n, hld.in[v],
{color[v] != 0 ? hld.light[v][0] : 1 << 28, 1 << 28,
1 << 28, color[v] != 1 ? hld.light[v][1] : 1 << 28}
);
};
auto update = [&](int v, int c) {
color[v] = c;
while (hld.top[v] != 1) {
// in[top[v]] < in[bottom[v]]
auto prv = seg.query(1, 1, n, hld.in[hld.top[v]], hld.in[hld.bottom[v]]);
update2(v);
auto nxt = seg.query(1, 1, n, hld.in[hld.top[v]], hld.in[hld.bottom[v]]);
v = hld.parent[hld.top[v]];
// update light edge
hld.light[v][0] += std::min({nxt[0][0], nxt[0][1], nxt[1][0] + 1, nxt[1][1] + 1}) -
std::min({prv[0][0], prv[0][1], prv[1][0] + 1, prv[1][1] + 1});
hld.light[v][1] += std::min({nxt[1][0], nxt[1][1], nxt[0][0] + 1, nxt[0][1] + 1}) -
std::min({prv[1][0], prv[1][1], prv[0][0] + 1, prv[0][1] + 1});
}
update2(v);
};
for (int c, v; m--;) {
std::cin >> c >> v;
update(v, --c);
std::cout << std::min({tree[1][0][0], tree[1][0][1], tree[1][1][0], tree[1][1][1]}) << "\n";
}
}