이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |