Submission #210123

#TimeUsernameProblemLanguageResultExecution timeMemory
210123waynetuinforCats or Dogs (JOI18_catdog)C++17
100 / 100
961 ms52984 KiB
#include <algorithm> #include <cassert> #include <iostream> #include <vector> #include "catdog.h" constexpr int kInf = 1'000'000; std::vector<std::vector<int>> g, nd; std::vector<int> sz, to, fa, fr, dep, ksz; 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) { 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); } } 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); } sz.assign(n, 0); ksz.assign(n, 0); to.assign(n, -1); fa.assign(n, -1); fr.assign(n, -1); dep.assign(n, 0); tree.assign(n, IntervalTree()); Dfs(0, -1); Link(0, 0); for (int i = 0; i < n; ++i) ksz[fr[i]]++; for (int i = 0; i < n; ++i) { if (fr[i] == i) { tree[i] = IntervalTree(ksz[i]); } } } 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, ksz[fr[v]]); 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[w]]) { 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[w]]) { 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[w]]) { 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...