#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e7;
const int MAXN = 1e5 + 5;
class Node {
public:
int par, ch[2], state;
int sum[2]; // sum of dp of light children
int dp[2][2]; // merged values on chain (dp[i][j] = start from color i, ending at color j)
Node() {
par = ch[0] = ch[1] = 0;
state = 2;
sum[0] = sum[1] = 0;
dp[0][0] = 0; dp[0][1] = INF;
dp[1][0] = INF; dp[1][1] = 0;
}
void ChangeState(int t) {
state = t;
}
int Answer() {
return min({dp[0][0], dp[0][1], dp[1][0], dp[1][1]});
}
};
int root;
Node tree[MAXN];
int sub[MAXN];
int heavy[MAXN];
vector<int> adj[MAXN];
bool IsChainRoot(int u) {
return tree[tree[u].par].ch[0] != u && tree[tree[u].par].ch[1] != u;
}
void Reupdate(int u) { // array<int, 2>{1, 0}});
tree[u].dp[0][0] = tree[u].sum[0]; tree[u].dp[0][1] = INF;
tree[u].dp[1][0] = INF; tree[u].dp[1][1] = tree[u].sum[1];
if (tree[u].state == 0) {
tree[u].dp[0][0] = INF;
} else if (tree[u].state == 1) {
tree[u].dp[1][1] = INF;
}
static int res[2][2];
if (tree[u].ch[1]) {
res[0][0] = res[0][1] = res[1][0] = res[1][1] = INF;
int oth = tree[u].ch[1];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
for (int l = 0; l < 2; l++) {
res[i][j] = min(res[i][j], (k != l) + tree[u].dp[i][k] + tree[oth].dp[l][j]);
}
}
}
}
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
tree[u].dp[i][j] = res[i][j];
}
}
}
if (tree[u].ch[0]) {
res[0][0] = res[0][1] = res[1][0] = res[1][1] = INF;
int oth = tree[u].ch[0];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
for (int l = 0; l < 2; l++) {
res[i][j] = min(res[i][j], (k != l) + tree[oth].dp[i][k] + tree[u].dp[l][j]);
}
}
}
}
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
tree[u].dp[i][j] = res[i][j];
}
}
}
}
void UpdateSum(int p, int u, int sgn) {
tree[p].sum[0] += sgn * min({tree[u].dp[0][0], tree[u].dp[0][1],
tree[u].dp[1][0] + 1, tree[u].dp[1][1] + 1});
tree[p].sum[1] += sgn * min({tree[u].dp[1][0], tree[u].dp[1][1],
tree[u].dp[0][0] + 1, tree[u].dp[0][1] + 1});
}
int Update(int u, int type) {
tree[u].ChangeState(type);
for (; u; u = tree[u].par) {
if (tree[u].par && IsChainRoot(u)) {
UpdateSum(tree[u].par, u, -1);
Reupdate(u);
UpdateSum(tree[u].par, u, +1);
} else {
Reupdate(u);
}
}
return tree[root].Answer();
}
void DfsInit(int u, int p) {
if (p) {
adj[u].erase(find(begin(adj[u]), end(adj[u]), p));
}
sub[u] = 1;
for (auto &v : adj[u]) {
DfsInit(v, u);
sub[u] += sub[v];
if (!heavy[u] || sub[heavy[u]] < sub[v]) {
heavy[u] = v;
}
}
}
int Build(int l, int r, const vector<int> &chain) {
if (l > r) return 0;
int all = 0, cur = 0, mid;
for (int i = l; i <= r; i++) all += sub[chain[i]];
for (mid = l; mid <= r; mid++) {
cur += sub[chain[mid]];
if (cur * 2 > all) {
break;
}
}
int id = chain[mid];
tree[id].ch[0] = Build(l, mid - 1, chain);
tree[id].ch[1] = Build(mid + 1, r, chain);
if (tree[id].ch[0]) tree[tree[id].ch[0]].par = id;
if (tree[id].ch[1]) tree[tree[id].ch[1]].par = id;
Reupdate(id);
return id;
}
int Construct(int u) {
for (int i = u; i; i = heavy[i]) {
for (auto v : adj[i]) {
if (v != heavy[i]) {
int r = Construct(v);
tree[r].par = i;
UpdateSum(i, r, +1);
}
}
}
static vector<int> chain; chain.clear();
for (int i = u; i; i = heavy[i]) {
chain.emplace_back(i);
}
for (int i = 0; i + 1 < (int) chain.size(); i++) {
sub[chain[i]] -= sub[chain[i + 1]];
}
return Build(0, int(chain.size()) - 1, chain);
}
void initialize(int N, vector<int> A, vector<int> B) {
for (int i = 0; i + 1 < N; i++) {
adj[A[i]].emplace_back(B[i]);
adj[B[i]].emplace_back(A[i]);
}
DfsInit(1, 0);
root = Construct(1);
}
int cat(int v) {
return Update(v, 0);
}
int dog(int v) {
return Update(v, 1);
}
int neighbor(int v) {
return Update(v, 2);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
6632 KB |
Output is correct |
2 |
Correct |
5 ms |
6656 KB |
Output is correct |
3 |
Correct |
4 ms |
6528 KB |
Output is correct |
4 |
Correct |
4 ms |
6528 KB |
Output is correct |
5 |
Correct |
4 ms |
6528 KB |
Output is correct |
6 |
Correct |
4 ms |
6528 KB |
Output is correct |
7 |
Correct |
4 ms |
6528 KB |
Output is correct |
8 |
Correct |
4 ms |
6528 KB |
Output is correct |
9 |
Correct |
4 ms |
6656 KB |
Output is correct |
10 |
Correct |
4 ms |
6528 KB |
Output is correct |
11 |
Correct |
4 ms |
6528 KB |
Output is correct |
12 |
Correct |
4 ms |
6656 KB |
Output is correct |
13 |
Correct |
4 ms |
6528 KB |
Output is correct |
14 |
Correct |
4 ms |
6528 KB |
Output is correct |
15 |
Correct |
4 ms |
6528 KB |
Output is correct |
16 |
Correct |
5 ms |
6528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
6632 KB |
Output is correct |
2 |
Correct |
5 ms |
6656 KB |
Output is correct |
3 |
Correct |
4 ms |
6528 KB |
Output is correct |
4 |
Correct |
4 ms |
6528 KB |
Output is correct |
5 |
Correct |
4 ms |
6528 KB |
Output is correct |
6 |
Correct |
4 ms |
6528 KB |
Output is correct |
7 |
Correct |
4 ms |
6528 KB |
Output is correct |
8 |
Correct |
4 ms |
6528 KB |
Output is correct |
9 |
Correct |
4 ms |
6656 KB |
Output is correct |
10 |
Correct |
4 ms |
6528 KB |
Output is correct |
11 |
Correct |
4 ms |
6528 KB |
Output is correct |
12 |
Correct |
4 ms |
6656 KB |
Output is correct |
13 |
Correct |
4 ms |
6528 KB |
Output is correct |
14 |
Correct |
4 ms |
6528 KB |
Output is correct |
15 |
Correct |
4 ms |
6528 KB |
Output is correct |
16 |
Correct |
5 ms |
6528 KB |
Output is correct |
17 |
Correct |
5 ms |
6656 KB |
Output is correct |
18 |
Correct |
5 ms |
6656 KB |
Output is correct |
19 |
Correct |
5 ms |
6656 KB |
Output is correct |
20 |
Correct |
4 ms |
6656 KB |
Output is correct |
21 |
Correct |
5 ms |
6656 KB |
Output is correct |
22 |
Correct |
5 ms |
6656 KB |
Output is correct |
23 |
Correct |
6 ms |
6656 KB |
Output is correct |
24 |
Correct |
6 ms |
6656 KB |
Output is correct |
25 |
Correct |
5 ms |
6656 KB |
Output is correct |
26 |
Correct |
5 ms |
6656 KB |
Output is correct |
27 |
Correct |
5 ms |
6656 KB |
Output is correct |
28 |
Correct |
5 ms |
6656 KB |
Output is correct |
29 |
Correct |
5 ms |
6656 KB |
Output is correct |
30 |
Correct |
4 ms |
6656 KB |
Output is correct |
31 |
Correct |
4 ms |
6656 KB |
Output is correct |
32 |
Correct |
4 ms |
6656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
6632 KB |
Output is correct |
2 |
Correct |
5 ms |
6656 KB |
Output is correct |
3 |
Correct |
4 ms |
6528 KB |
Output is correct |
4 |
Correct |
4 ms |
6528 KB |
Output is correct |
5 |
Correct |
4 ms |
6528 KB |
Output is correct |
6 |
Correct |
4 ms |
6528 KB |
Output is correct |
7 |
Correct |
4 ms |
6528 KB |
Output is correct |
8 |
Correct |
4 ms |
6528 KB |
Output is correct |
9 |
Correct |
4 ms |
6656 KB |
Output is correct |
10 |
Correct |
4 ms |
6528 KB |
Output is correct |
11 |
Correct |
4 ms |
6528 KB |
Output is correct |
12 |
Correct |
4 ms |
6656 KB |
Output is correct |
13 |
Correct |
4 ms |
6528 KB |
Output is correct |
14 |
Correct |
4 ms |
6528 KB |
Output is correct |
15 |
Correct |
4 ms |
6528 KB |
Output is correct |
16 |
Correct |
5 ms |
6528 KB |
Output is correct |
17 |
Correct |
5 ms |
6656 KB |
Output is correct |
18 |
Correct |
5 ms |
6656 KB |
Output is correct |
19 |
Correct |
5 ms |
6656 KB |
Output is correct |
20 |
Correct |
4 ms |
6656 KB |
Output is correct |
21 |
Correct |
5 ms |
6656 KB |
Output is correct |
22 |
Correct |
5 ms |
6656 KB |
Output is correct |
23 |
Correct |
6 ms |
6656 KB |
Output is correct |
24 |
Correct |
6 ms |
6656 KB |
Output is correct |
25 |
Correct |
5 ms |
6656 KB |
Output is correct |
26 |
Correct |
5 ms |
6656 KB |
Output is correct |
27 |
Correct |
5 ms |
6656 KB |
Output is correct |
28 |
Correct |
5 ms |
6656 KB |
Output is correct |
29 |
Correct |
5 ms |
6656 KB |
Output is correct |
30 |
Correct |
4 ms |
6656 KB |
Output is correct |
31 |
Correct |
4 ms |
6656 KB |
Output is correct |
32 |
Correct |
4 ms |
6656 KB |
Output is correct |
33 |
Correct |
123 ms |
10216 KB |
Output is correct |
34 |
Correct |
72 ms |
10360 KB |
Output is correct |
35 |
Correct |
131 ms |
9584 KB |
Output is correct |
36 |
Correct |
207 ms |
12480 KB |
Output is correct |
37 |
Correct |
23 ms |
8320 KB |
Output is correct |
38 |
Correct |
236 ms |
13156 KB |
Output is correct |
39 |
Correct |
232 ms |
13056 KB |
Output is correct |
40 |
Correct |
228 ms |
13160 KB |
Output is correct |
41 |
Correct |
234 ms |
13032 KB |
Output is correct |
42 |
Correct |
226 ms |
13156 KB |
Output is correct |
43 |
Correct |
255 ms |
13244 KB |
Output is correct |
44 |
Correct |
239 ms |
13072 KB |
Output is correct |
45 |
Correct |
275 ms |
13156 KB |
Output is correct |
46 |
Correct |
243 ms |
13032 KB |
Output is correct |
47 |
Correct |
244 ms |
13032 KB |
Output is correct |
48 |
Correct |
81 ms |
11072 KB |
Output is correct |
49 |
Correct |
102 ms |
12192 KB |
Output is correct |
50 |
Correct |
29 ms |
8128 KB |
Output is correct |
51 |
Correct |
37 ms |
8756 KB |
Output is correct |
52 |
Correct |
19 ms |
7808 KB |
Output is correct |
53 |
Correct |
144 ms |
12408 KB |
Output is correct |
54 |
Correct |
73 ms |
9208 KB |
Output is correct |
55 |
Correct |
174 ms |
11376 KB |
Output is correct |
56 |
Correct |
107 ms |
9808 KB |
Output is correct |
57 |
Correct |
167 ms |
12208 KB |
Output is correct |
58 |
Correct |
29 ms |
8948 KB |
Output is correct |
59 |
Correct |
37 ms |
8696 KB |
Output is correct |
60 |
Correct |
89 ms |
11632 KB |
Output is correct |
61 |
Correct |
91 ms |
12016 KB |
Output is correct |
62 |
Correct |
67 ms |
10736 KB |
Output is correct |
63 |
Correct |
68 ms |
11512 KB |
Output is correct |
64 |
Correct |
77 ms |
12664 KB |
Output is correct |
65 |
Correct |
99 ms |
16120 KB |
Output is correct |
66 |
Correct |
87 ms |
9336 KB |
Output is correct |
67 |
Correct |
82 ms |
13176 KB |
Output is correct |
68 |
Correct |
151 ms |
15992 KB |
Output is correct |
69 |
Correct |
39 ms |
7672 KB |
Output is correct |
70 |
Correct |
11 ms |
6784 KB |
Output is correct |
71 |
Correct |
76 ms |
11256 KB |
Output is correct |
72 |
Correct |
110 ms |
14968 KB |
Output is correct |
73 |
Correct |
175 ms |
18048 KB |
Output is correct |
74 |
Correct |
182 ms |
15752 KB |
Output is correct |
75 |
Correct |
178 ms |
18168 KB |
Output is correct |
76 |
Correct |
174 ms |
17272 KB |
Output is correct |
77 |
Correct |
190 ms |
16120 KB |
Output is correct |