#include <bits/stdc++.h>
#include "catdog.h"
using namespace std;
int n;
constexpr int N = 100001;
vector<int> g[N];
int head[N], sz[N], parent[N], tin[N], T = 0, hld_sz[N], type[N];
int ans = 0;
array<int, 3> sum[N];
void dfs_init(int v) {
auto it = find(g[v].begin(), g[v].end(), parent[v]);
if (it != g[v].end()) {
g[v].erase(it);
}
sz[v] = 1;
for (int &to: g[v]) {
parent[to] = v;
dfs_init(to);
sz[v] += sz[to];
if (sz[to] > sz[g[v][0]]) {
swap(to, g[v][0]);
}
}
}
void dfs_hld(int v) {
if (head[v] == 0) {
head[v] = v;
}
hld_sz[head[v]] += 1;
tin[v] = T++;
for (int &to: g[v]) {
if (to == g[v][0]) {
head[to] = head[v];
}
dfs_hld(to);
}
}
struct Info {
int dp[3][3]{}, dq[3]{};
Info() = default;
Info(array<int, 3> d) {
memset(dp, 0x3f, sizeof(dp));
for (int i = 0; i < n; ++i) {
dq[i] = d[i];
}
}
Info(const int d[3][3], const int dk[3]) {
memcpy(dp, d, sizeof(dp));
memcpy(dq, dk, sizeof(dq));
}
};
Info operator+(Info &a, Info &b) {
int best[3];
memset(best, 0x3f, sizeof(best));
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
best[i] = min(best[i], a.dp[i][j]);
}
}
int dp[3][3], dq[3];
for (int i = 0; i < 3; ++i) {
dq[i] = min(0x3f3f3f3f, a.dq[i] + b.dq[i]);
}
memset(dp, 0x3f, sizeof(dp));
for (int x = 0; x < 3; ++x) {
for (int y = 0; y < 3; ++y) {
for (int z = 0; z < 3; ++z) {
dp[x][z] = min({dp[x][z], a.dp[x][y] + b.dp[y][z],
best[x] + b.dp[y][z] + (y != 2), a.dp[x][y] + b.dq[z] + (z != y),
a.dq[x] + b.dp[y][z] + (z != y)});
}
dp[x][y] = min({dp[x][y], a.dp[x][y] + b.dq[2], a.dq[2] + b.dp[x][y], a.dq[x] + b.dq[y] + 1});
}
}
return {dp, dq};
}
struct SegmentTree {
vector<Info> t;
int n{};
void init(int m) {
n = 1 << (__lg(m) + bool(m & (m - 1)));
t.assign(2 * n, {});
}
void modify(int i, Info x) {
for (t[i += n] = x; i >>= 1;) {
t[i] = t[i << 1] + t[i << 1 | 1];
}
}
array<int, 3> ans() {
array<int, 3> ans{};
for (int i = 0; i < 3; ++i) {
ans[i] = min({t[1].dp[i][0], t[1].dp[i][1], t[1].dp[i][2], t[1].dq[i]});
}
int mn = min({ans[0], ans[1], ans[2]});
for (int i = 0; i < 3; ++i) {
ans[i] = min(ans[i], mn + 1);
}
return ans;
}
int best() {
int ans = numeric_limits<int>::max();
for (int i = 0; i < 3; ++i) {
ans = min({ans, t[1].dp[i][0], t[1].dp[i][1], t[1].dp[i][2], t[1].dq[i]});
}
return ans;
}
};
SegmentTree t[N];
void update(int v) {
while (true) {
int p = head[v];
if (p != 0) {
auto kek = t[p].ans();
for (int i = 0; i < 3; ++i) {
sum[parent[p]][i] -= kek[i];
}
}
array<int, 3> now{};
if (type[v] == 2) {
now = sum[v];
} else {
now[0] = now[1] = now[2] = 0x3f3f3f3f;
now[type[v]] = sum[v][type[v]];
}
t[head[v]].modify(tin[v] - tin[head[v]], now);
if (p != 0) {
auto kek = t[p].ans();
for (int i = 0; i < 3; ++i) {
sum[parent[p]][i] += kek[i];
}
v = parent[p];
} else {
break;
}
}
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n = N;
for (int i = 0; i < n - 1; ++i) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
dfs_init(1);
dfs_hld(1);
for (int i = 1; i <= n; ++i) {
if (head[i] == i) {
t[i].init(hld_sz[i]);
}
}
}
int cat(int v) {
type[v] = 0;
update(v);
return t[1].best();
}
int dog(int v) {
type[v] = 1;
update(v);
return t[1].best();
}
int neighbor(int v) {
type[v] = 2;
update(v);
return t[1].best();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
11476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
11476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
11476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
