제출 #357732

#제출 시각아이디문제언어결과실행 시간메모리
357732KoDCats or Dogs (JOI18_catdog)C++17
100 / 100
627 ms27392 KiB
#include "catdog.h" #include <vector> #include <algorithm> #include <utility> #include <array> namespace Solver { template <class T> using Vec = std::vector<T>; constexpr int MAX = 100000; struct Monoid { static constexpr Monoid ID() { return Monoid { { 0, MAX, MAX, 0 } }; } std::array<std::array<long long, 2>, 2> value; Monoid operator + (const Monoid &other) const { Monoid ret{ { MAX, MAX, MAX, MAX }}; for (int i: { 0, 1 }) { for (int j: { 0, 1 }) { for (int k: { 0, 1 }) { for (int l: { 0, 1 }) { ret.value[i][l] = std::min(ret.value[i][l], value[i][j] + other.value[k][l] + (j ^ k)); } } } } return ret; } }; struct Segtree { int size; Vec<Monoid> data; void fix(const int k) { data[k] = data[k << 1 | 0] + data[k << 1 | 1]; } Segtree(const int n = 0): size(n), data(2 * n, Monoid::ID()) { } void set(int k, const std::array<long long, 2> &arr) { k += size; data[k].value[0][0] = arr[0]; data[k].value[1][1] = arr[1]; while (k > 1) { k >>= 1; fix(k); } } std::array<long long, 2> get(int r) const { int l = size; r += size; Monoid ml = Monoid::ID(); Monoid mr = Monoid::ID(); while (l < r) { if (l & 1) { ml = ml + data[l]; l += 1; } if (r & 1) { r -= 1; mr = data[r] + mr; } l >>= 1; r >>= 1; } Monoid tmp = ml + mr; std::array<long long, 2> ret{ MAX, MAX }; for (int i: { 0, 1 }) { for (int j: { 0, 1 }) { ret[i] = std::min(ret[i], tmp.value[i][j]); } } return ret; } }; std::array<Vec<int>, MAX> graph; std::array<int, MAX> parent, size, head, label, state; std::array<Segtree, MAX> trees; std::array<std::array<long long, 2>, MAX> vals; void precalc(const int u, const int p) { parent[u] = p; size[u] = 1; for (const auto v: graph[u]) { if (v != parent[u]) { precalc(v, u); size[u] += size[v]; } } } void decomp(const int u, const int h, const int l) { head[u] = h; label[u] = l; int c = -1; for (const auto v: graph[u]) { if (v != parent[u]) { if (c == -1 || size[c] < size[v]) { c = v; } } } if (c == -1) { trees[h] = Segtree(l + 1); } else { decomp(c, h, l + 1); for (const auto v: graph[u]) { if (v != parent[u] && v != c) { decomp(v, v, 0); } } } } long long set(int u, std::array<long long, 2> arr) { while (true) { const auto v = head[u]; const auto cur = trees[v].get(trees[v].size); trees[v].set(label[u], arr); const auto next = trees[v].get(trees[v].size); if (v == 0) { break; } u = parent[v]; for (int i: { 0, 1 }) { vals[u][i] -= std::min(cur[i], cur[i ^ 1] + 1); vals[u][i] += std::min(next[i], next[i ^ 1] + 1); arr[i] = (state[u] == 2 - i ? (long long) MAX : vals[u][i]); } } const auto tmp = trees[0].get(trees[0].size); return std::min(tmp[0], tmp[1]); } } void initialize(int N, std::vector<int> A, std::vector<int> B) { for (int i = 0; i < N - 1; ++i) { A[i] -= 1; B[i] -= 1; Solver::graph[A[i]].push_back(B[i]); Solver::graph[B[i]].push_back(A[i]); } Solver::precalc(0, -1); Solver::decomp(0, 0, 0); } int cat(int v) { using namespace Solver; v -= 1; state[v] = 1; return set(v, std::array<long long, 2>{ vals[v][0], MAX }); } int dog(int v) { using namespace Solver; v -= 1; state[v] = 2; return set(v, std::array<long long, 2>{ MAX, vals[v][1] }); } int neighbor(int v) { using namespace Solver; v -= 1; state[v] = 0; return set(v, vals[v]); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...