#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
#include "catdog.h"
constexpr int kInf = 1'000'000;
std::vector<std::vector<int>> g;
std::vector<int> tin, tout, sz, to, fa, fr, dep;
std::vector<std::vector<int>> dp;
std::vector<std::vector<int>> nd;
void Dfs(int x, int p) {
sz[x] = 1;
fa[x] = p;
for (int u : g[x]) {
if (u == p) continue;
dep[u] = dep[x] + 1;
Dfs(u, x);
sz[x] += sz[u];
if (to[x] == -1 || sz[u] > sz[to[x]]) to[x] = u;
}
}
void Link(int x, int f) {
static int tk = 0;
tin[x] = tk++;
fr[x] = f;
if (to[x] != -1) Link(to[x], f);
for (int u : g[x]) {
if (u == fa[x] || u == to[x]) continue;
Link(u, u);
}
tout[x] = tk;
}
struct IntervalTree {
int n;
std::vector<std::vector<int>> tree;
std::vector<std::vector<int>> aux;
IntervalTree() = default;
IntervalTree(int n)
: n(n), tree(n * 4, std::vector<int>(4)), aux(n, std::vector<int>(2)) {
for (auto &v : tree) {
v[1] = kInf;
v[2] = kInf;
}
}
std::vector<int> Merge(const std::vector<int> &a, const std::vector<int> &b,
int p) {
std::vector<int> res(4, kInf);
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
res[(i & 2) | (j & 1)] = std::min(
res[(i & 2) | (j & 1)],
a[i] + b[j] + ((i & 1) != (j >> 1 & 1)) + aux[p][j >> 1 & 1]);
}
}
return res;
}
void UpdateAux(int p, const std::vector<int> &v) {
auto Impl = [&](auto self, int l, int r, int o = 0) {
if (r - l == 1) {
aux[l] = v;
return;
}
int m = (l + r) >> 1;
if (p < m) {
self(self, l, m, o * 2 + 1);
} else {
self(self, m, r, o * 2 + 2);
}
tree[o] = Merge(tree[o * 2 + 1], tree[o * 2 + 2], m);
};
Impl(Impl, 0, n);
}
void Modify(int p, const std::vector<int> &v) {
auto Impl = [&](auto self, int l, int r, int o = 0) {
if (r - l == 1) {
std::fill(tree[o].begin(), tree[o].end(), kInf);
for (int i = 0; i < 2; ++i) tree[o][i << 1 | i] = v[i];
return;
}
int m = (l + r) >> 1;
if (p < m) {
self(self, l, m, o * 2 + 1);
} else {
self(self, m, r, o * 2 + 2);
}
tree[o] = Merge(tree[o * 2 + 1], tree[o * 2 + 2], m);
};
Impl(Impl, 0, n);
}
std::vector<int> Query(int ql, int qr) {
auto Impl = [&](auto self, int l, int r, int o = 0) {
if (l >= ql && r <= qr) return tree[o];
int m = (l + r) >> 1;
if (qr <= m) return self(self, l, m, o * 2 + 1);
if (ql >= m) return self(self, m, r, o * 2 + 2);
return Merge(self(self, l, m, o * 2 + 1), self(self, m, r, o * 2 + 2), m);
};
return Impl(Impl, 0, n);
}
};
std::vector<IntervalTree> tree;
void initialize(int n, std::vector<int> a, std::vector<int> b) {
g.resize(n);
for (int i = 0; i < n - 1; ++i) {
int u = a[i], v = b[i];
u--, v--;
g[u].push_back(v);
g[v].push_back(u);
}
tin.resize(n);
tout.resize(n);
sz.resize(n);
to.resize(n, -1);
fa.resize(n, -1);
fr.resize(n, -1);
dep.resize(n);
dp.resize(n, std::vector<int>(2));
tree.resize(n);
nd.resize(n);
Dfs(0, -1);
Link(0, 0);
for (int i = 0; i < n; ++i) {
nd[fr[i]].push_back(i);
}
for (int i = 0; i < n; ++i) {
if (fr[i] == i) {
tree[i] = IntervalTree(nd[i].size());
}
}
}
std::vector<int> GetAux(int v) {
int p = dep[v] - dep[fr[v]];
return tree[fr[v]].aux[p];
}
std::vector<int> GetValue(int v) {
int p = dep[v] - dep[fr[v]];
auto val = tree[fr[v]].Query(p, nd[fr[v]].size());
std::vector<int> res(2, kInf);
for (int i = 0; i < 4; ++i) {
res[i >> 1 & 1] = std::min(res[i >> 1 & 1], val[i]);
}
for (int i = 0; i < 2; ++i) res[i] += GetAux(v)[i];
return res;
}
void UpdateAux(int v, const std::vector<int> &aux) {
int p = dep[v] - dep[fr[v]];
tree[fr[v]].UpdateAux(p, aux);
}
int cat(int v) {
v--;
std::vector<std::vector<int>> hist;
for (int w = fr[v]; fa[w] != -1; w = fr[fa[v]]) {
hist.push_back(GetValue(w));
}
tree[fr[v]].Modify(dep[v] - dep[fr[v]], {0, kInf});
v = fr[v];
int ptr = 0;
while (fa[v] >= 0) {
auto aux = GetAux(fa[v]);
auto old = hist[ptr];
aux[0] -= std::min(old[0], old[1] + 1);
aux[1] -= std::min(old[1], old[0] + 1);
auto upd = GetValue(v);
aux[0] += std::min(upd[0], upd[1] + 1);
aux[1] += std::min(upd[1], upd[0] + 1);
ptr++;
// std::cerr << "v = " << v << " fa = " << fa[v] << " upd-aux = " << aux[0] << ", " << aux[1] << std::endl;
UpdateAux(fa[v], aux);
v = fr[fa[v]];
}
// for (int i = 0; i < g.size(); ++i) {
// auto gv = GetValue(i);
// std::cerr << "dp[" << i << "][0] = " << gv[0] << std::endl;
// std::cerr << "dp[" << i << "][1] = " << gv[1] << std::endl;
// auto aux = GetAux(i);
// std::cerr << "aux[" << i << "][0] = " << aux[0] << std::endl;
// std::cerr << "aux[" << i << "][1] = " << aux[1] << std::endl;
// }
// std::cerr << std::endl;
auto res = GetValue(0);
return std::min(res[0], res[1]);
}
int dog(int v) {
v--;
std::vector<std::vector<int>> hist;
for (int w = fr[v]; fa[w] != -1; w = fr[fa[v]]) {
hist.push_back(GetValue(w));
}
tree[fr[v]].Modify(dep[v] - dep[fr[v]], {kInf, 0});
v = fr[v];
int ptr = 0;
while (fa[v] >= 0) {
auto aux = GetAux(fa[v]);
auto old = hist[ptr];
aux[0] -= std::min(old[0], old[1] + 1);
aux[1] -= std::min(old[1], old[0] + 1);
auto upd = GetValue(v);
aux[0] += std::min(upd[0], upd[1] + 1);
aux[1] += std::min(upd[1], upd[0] + 1);
ptr++;
UpdateAux(fa[v], aux);
v = fr[fa[v]];
}
// for (int i = 0; i < g.size(); ++i) {
// auto gv = GetValue(i);
// std::cerr << "dp[" << i << "][0] = " << gv[0] << std::endl;
// std::cerr << "dp[" << i << "][1] = " << gv[1] << std::endl;
// auto aux = GetAux(i);
// std::cerr << "aux[" << i << "][0] = " << aux[0] << std::endl;
// std::cerr << "aux[" << i << "][1] = " << aux[1] << std::endl;
// }
// std::cerr << std::endl;
auto res = GetValue(0);
return std::min(res[0], res[1]);
}
int neighbor(int v) {
v--;
std::vector<std::vector<int>> hist;
for (int w = fr[v]; fa[w] != -1; w = fr[fa[v]]) {
hist.push_back(GetValue(w));
}
tree[fr[v]].Modify(dep[v] - dep[fr[v]], {0, 0});
v = fr[v];
int ptr = 0;
while (fa[v] >= 0) {
auto aux = GetAux(fa[v]);
auto old = hist[ptr];
aux[0] -= std::min(old[0], old[1] + 1);
aux[1] -= std::min(old[1], old[0] + 1);
auto upd = GetValue(v);
aux[0] += std::min(upd[0], upd[1] + 1);
aux[1] += std::min(upd[1], upd[0] + 1);
ptr++;
// std::cerr << "v = " << v << " fa = " << fa[v] << " upd-aux = " << aux[0] << ", " << aux[1] << std::endl;
UpdateAux(fa[v], aux);
v = fr[fa[v]];
}
// for (int i = 0; i < g.size(); ++i) {
// auto gv = GetValue(i);
// std::cerr << "dp[" << i << "][0] = " << gv[0] << std::endl;
// std::cerr << "dp[" << i << "][1] = " << gv[1] << std::endl;
// auto aux = GetAux(i);
// std::cerr << "aux[" << i << "][0] = " << aux[0] << std::endl;
// std::cerr << "aux[" << i << "][1] = " << aux[1] << std::endl;
// }
// std::cerr << std::endl;
auto res = GetValue(0);
return std::min(res[0], res[1]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Runtime error |
1793 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Runtime error |
1793 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Runtime error |
1793 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
