#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
using int64 = long long;
using ld = long double;
constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;
template<class node, class F = std::function<node(const node &, const node &)>>
class SegTree {
int n = 0;
std::vector<node> t;
F unite;
void build(const int x, const int l, const int r, const std::vector<node> &a) {
if (l == r) {
t[x] = a[l];
return;
}
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
build(x + 1, l, mid, a);
build(y, mid + 1, r, a);
t[x] = unite(t[x + 1], t[y]);
}
void update(const int x, const int l, const int r, const int p, const node &v) {
if (l == p and p == r) {
t[x] = v;
return;
}
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
if (p <= mid) {
update(x + 1, l, mid, p, v);
} else {
update(y, mid + 1, r, p, v);
}
t[x] = unite(t[x + 1], t[y]);
}
node query(const int x, const int l, const int r, const int ql, const int qr) const {
if (ql <= l and r <= qr) {
return t[x];
}
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
if (qr <= mid) {
return query(x + 1, l, mid, ql, qr);
} else if (mid < ql) {
return query(y, mid + 1, r, ql, qr);
} else {
return unite(query(x + 1, l, mid, ql, qr), query(y, mid + 1, r, ql, qr));
}
}
public:
SegTree() = default;
explicit SegTree(const int n, const node e, F f) : n(n), t(2 * n - 1, e), unite(std::move(f)) {}
explicit SegTree(const std::vector<node> &a, F f) : n(a.size()), t(2 * (a.size()) - 1), unite(std::move(f)) {
build(0, 0, n - 1, a);
}
void update(const int p, const node &v) {
assert(0 <= p and p < n);
update(0, 0, n - 1, p, v);
}
[[nodiscard]] node query(const int l, const int r) const {
assert(0 <= l and l <= r and r < n);
return query(0, 0, n - 1, l, r);
}
};
class HeavyLight {
int n;
vector<vector<int>> g;
public:
vector<int> parent;
vector<int> heavy;
vector<int> depth;
vector<int> in;
vector<int> out;
vector<int> head;
vector<int> size;
private:
void dfs(const int x) {
size[x] = 1;
int max_size = 0;
for (const int y : g[x]) {
if (y == parent[x]) continue;
depth[y] = depth[x] + 1;
parent[y] = x;
dfs(y);
if (size[y] > max_size) {
heavy[x] = y;
max_size = size[y];
}
size[x] += size[y];
}
}
int timer = 0;
void dfs2(const int x) {
head[x] = (parent[x] == -1 or heavy[parent[x]] != x ? x : head[parent[x]]);
in[x] = timer++;
if (heavy[x] != -1) {
dfs2(heavy[x]);
}
for (const int y : g[x]) {
if (y == parent[x] or y == heavy[x]) continue;
dfs2(y);
}
out[x] = timer - 1;
}
public:
HeavyLight() = default;
explicit HeavyLight(const vector<vector<int>> &t)
: n(t.size()), g(t),
parent(n, -1), heavy(n, -1), depth(n),
in(n), out(n), head(n), size(n) {
dfs(0);
dfs2(0);
}
template<class Op = function<void(int, int)>>
void operate(int x, int y, const Op &op, const bool ignore_lca = false) {
while (head[x] != head[y]) {
if (depth[head[x]] > depth[head[y]]) swap(x, y);
op(in[head[y]], in[y]);
y = parent[head[y]];
}
if (depth[x] > depth[y]) swap(x, y);
if (in[x] + ignore_lca <= in[y]) op(in[x] + ignore_lca, in[y]);
}
};
class node {
array<array<int, 2>, 2> a;
public:
node(const int x = 0) {
for (const int i : {0, 1}) {
for (const int j : {0, 1}) {
a[i][j] = x;
}
}
}
array<int, 2> &operator[](const int i) {
return a[i];
}
};
int n = -1;
SegTree<node> st;
HeavyLight hld;
void initialize(const int N, vector<int> A, vector<int> B) {
n = N;
vector<vector<int>> g(n);
for (int i = 0; i < n - 1; i++) {
A[i]--, B[i]--;
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
auto unite = [](node l, node r) {
node ans(kInf);
for (const int s1 : {0, 1}) {
for (const int s2 : {0, 1}) {
for (const int e1 : {0, 1}) {
for (const int e2 : {0, 1}) {
ans[s1][e2] = min(ans[s1][e2], l[s1][e1] + (e1 != s2) + r[s2][e2]);
}
}
}
}
return ans;
};
st = SegTree<node>(n, node(), unite);
hld = HeavyLight(g);
}
int cat(const int x) {
node cur(kInf);
cur[0][0] = 0;
hld.operate(x - 1, x - 1, [&](const int l, const int r) {
st.update(l, cur);
});
node ans = st.query(0, n - 1);
return min({
ans[0][0], ans[0][1],
ans[1][0], ans[1][1]
});
}
int dog(const int x) {
node cur(kInf);
cur[1][1] = 0;
hld.operate(x - 1, x - 1, [&](const int l, const int r) {
st.update(l, cur);
});
node ans = st.query(0, n - 1);
return min({
ans[0][0], ans[0][1],
ans[1][0], ans[1][1]
});
}
int neighbor(const int x) {
node cur(0);
hld.operate(x - 1, x - 1, [&](const int l, const int r) {
st.update(l, cur);
});
node ans = st.query(0, n - 1);
return min({
ans[0][0], ans[0][1],
ans[1][0], ans[1][1]
});
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
