#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX = (int) 1e5;
int n, sz[MAX], pr[MAX], hd[MAX];
int from[MAX], to[MAX], col[MAX];
int ver[MAX], id[MAX], rt[MAX];
int dp_a[MAX], dp_b[MAX];
vector<int> g[MAX];
struct node {
int a[2][2];
node() {}
node(int v) {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
a[i][j] = v;
}
}
}
} st[8 * MAX];
const int inf = (int) 1e9;
node f(node l, node r) {
node res(inf);
for (int xl = 0; xl < 2; xl++) {
for (int yl = 0; yl < 2; yl++) {
for (int xr = 0; xr < 2; xr++) {
for (int yr = 0; yr < 2; yr++) {
res.a[xl][yr] = min(res.a[xl][yr], l.a[xl][yl] + r.a[xr][yr] + (yl != xr ? 1 : 0));
}
}
}
}
return res;
};
void pull(int v) {
st[v] = f(st[v * 2], st[v * 2 + 1]);
}
void Build(int v, int l, int r) {
if (l == r) {
st[v].a[0][0] = dp_a[ver[l]];
st[v].a[0][1] = inf;
st[v].a[1][0] = inf;
st[v].a[1][1] = dp_b[ver[l]];
return;
}
int mid = l + r >> 1;
Build(v * 2, l, mid);
Build(v * 2 + 1, mid + 1, r);
pull(v);
}
void Modify(int v, int l, int r, int i) {
if (l == r) {
st[v].a[0][0] = (col[ver[l]] != 1 ? dp_a[ver[l]] : inf);
st[v].a[0][1] = inf;
st[v].a[1][0] = inf;
st[v].a[1][1] = (col[ver[l]] != 0 ? dp_b[ver[l]] : inf);
return;
}
int mid = l + r >> 1;
if (i <= mid) {
Modify(v * 2, l, mid, i);
} else {
Modify(v * 2 + 1, mid + 1, r, i);
}
pull(v);
}
node Query(int v, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
return st[v];
}
int mid = l + r >> 1;
if (qr <= mid) {
return Query(v * 2, l, mid, ql, qr);
} else if (ql > mid) {
return Query(v * 2 + 1, mid + 1, r, ql, qr);
} else {
return f(Query(v * 2, l, mid, ql, qr), Query(v * 2 + 1, mid + 1, r, ql, qr));
}
}
void Update(int v) {
while (true) {
if (rt[v] != 0) {
int x = pr[rt[v]];
int y = rt[v];
node nd = Query(1, 0, n - 1, from[y], to[y]);
{
dp_a[x] -= min({nd.a[0][0], nd.a[0][1], nd.a[1][0] + 1, nd.a[1][1] + 1});
dp_b[x] -= min({nd.a[1][0], nd.a[1][1], nd.a[0][0] + 1, nd.a[0][1] + 1});
}
}
Modify(1, 0, n - 1, id[v]);
if (rt[v] != 0) {
int x = pr[rt[v]];
int y = rt[v];
node nd = Query(1, 0, n - 1, from[y], to[y]);
{
dp_a[x] += min({nd.a[0][0], nd.a[0][1], nd.a[1][0] + 1, nd.a[1][1] + 1});
dp_b[x] += min({nd.a[1][0], nd.a[1][1], nd.a[0][0] + 1, nd.a[0][1] + 1});
}
v = x;
} else {
return;
}
}
}
void initialize(int n, vector<int> x, vector<int> y) {
::n = n;
for (int i = 0; i < n - 1; i++) {
--x[i]; --y[i];
g[x[i]].push_back(y[i]);
g[y[i]].push_back(x[i]);
}
function<void(int, int)> dfs_hld = [&](int v, int p) {
sz[v] = 1;
hd[v] = -1;
pr[v] = p;
for (int u : g[v]) {
if (u == p) {
continue;
}
dfs_hld(u, v);
sz[v] += sz[u];
if (hd[v] == -1 || sz[u] > sz[hd[v]]) {
hd[v] = u;
}
}
};
dfs_hld(0, -1);
int cnt = 0;
function<void(int, int)> dfs = [&](int v, int p) {
if (hd[v] != -1) {
rt[hd[v]] = rt[v];
id[hd[v]] = cnt++;
dfs(hd[v], v);
}
for (int u : g[v]) {
if (u == p || u == hd[v]) {
continue;
}
id[u] = cnt++;
rt[u] = u;
dfs(u, v);
}
};
id[0] = cnt++;
dfs(0, -1);
for (int i = 0; i < n; i++) {
ver[id[i]] = i;
}
Build(1, 0, n - 1);
for (int i = 0; i < n; i++) {
from[i] = n;
to[i] = 0;
}
for (int i = 0; i < n; i++) {
from[rt[i]] = min(from[rt[i]], id[i]);
to[rt[i]] = max(to[rt[i]], id[i]);
}
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
return id[i] > id[j];
});
for (int i : order) {
for (int j : g[i]) {
if (j == pr[i] || hd[i] == j) {
continue;
}
node nd = Query(1, 0, n - 1, from[j], to[j]);
dp_a[i] += min({nd.a[0][0], nd.a[0][1], nd.a[1][0] + 1, nd.a[1][1] + 1});
dp_b[i] += min({nd.a[1][0], nd.a[1][1], nd.a[0][0] + 1, nd.a[0][1] + 1});
}
Modify(1, 0, n - 1, id[i]);
}
}
int solve() {
node nd = Query(1, 0, n - 1, from[0], to[0]);
int res = inf;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
res = min(res, nd.a[i][j]);
}
}
return res;
}
int cat(int v) {
--v;
col[v] = 0;
Update(v);
return solve();
}
int dog(int v) {
--v;
col[v] = 1;
Update(v);
return solve();
}
int neighbor(int v) {
--v;
col[v] = -1;
Update(v);
return solve();
}
Compilation message
catdog.cpp: In function 'void Build(int, int, int)':
catdog.cpp:54:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | int mid = l + r >> 1;
| ~~^~~
catdog.cpp: In function 'void Modify(int, int, int, int)':
catdog.cpp:68:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
68 | int mid = l + r >> 1;
| ~~^~~
catdog.cpp: In function 'node Query(int, int, int, int, int)':
catdog.cpp:81:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
81 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
