#include <bits/stdc++.h>
#include "catdog.h"
using namespace std;
const int N = 100100;
const int inf = 1e9;
struct Arr {
array<array<int, 2>, 2> a;
Arr() { a[0][0] = a[0][1] = a[1][0] = a[1][1] = inf; };
array<int, 2>& operator [](int id) { return a[id]; }
};
Arr mrg(Arr x,Arr y) {
Arr z;
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) {
z[i][l] = min(z[i][l], x[i][j] + (j ^ k) + y[k][l]);
}
}
}
}
return z;
}
#define md ((l + r) >> 1)
struct SegTree {
vector<Arr> t;
void resize(int n) {
t.resize((n + 1) << 2);
}
void build(int v,int l,int r) {
if (l == r) {
t[v][0][0] = t[v][1][1] = 0;
return;
}
build(v << 1, l, md);
build(v << 1 | 1, md + 1, r);
t[v] = mrg(t[v << 1], t[v << 1 | 1]);
}
void add(int v,int l,int r,int p,int v0,int v1) {
if (p < l || p > r) return;
if (l == r) {
t[v][0][0] += v0;
t[v][1][1] += v1;
return;
}
add(v << 1, l, md, p, v0, v1);
add(v << 1 | 1, md + 1, r, p, v0, v1);
t[v] = mrg(t[v << 1], t[v << 1 | 1]);
}
} t[N];
int a[N];
vector<int> g[N];
int child[N];
int up[N], par[N];
int tin[N], tt;
int ll[N], rr[N];
void dfs(int u) {
child[u] = 1;
for (int v : g[u]) {
if (v != par[u]) {
par[v] = u;
dfs(v);
child[u] += child[v];
}
}
}
void hld(int u,int root) {
up[u] = root;
tin[u] = ++tt;
int nxt = 0;
for (int v : g[u]) {
if (v != par[u]) {
if (child[v] > child[nxt]) {
nxt = v;
}
}
}
if (nxt) {
hld(nxt, root);
}
for (int v : g[u]) {
if (v != par[u] && v != nxt) {
hld(v, v);
}
}
}
void initialize(int n, vector<int> a,vector<int> b) {
for (int i = 0; i < n - 1; ++i) {
g[a[i]].push_back(b[i]);
g[b[i]].push_back(a[i]);
}
dfs(1);
hld(1, 1);
for (int i = 1; i <= n; ++i) ll[i] = n, rr[i] = 1;
for (int i = 1; i <= n; ++i) {
ll[up[i]] = min(ll[up[i]], tin[i]);
rr[up[i]] = max(rr[up[i]], tin[i]);
}
for (int i = 1; i <= n; ++i) {
if (up[i] == i) {
t[i].resize(rr[i] - ll[i] + 1);
t[i].build(1, ll[i], rr[i]);
}
}
}
void add(int u,int v0,int v1) {
while (up[u] != up[1]) {
int v = up[u];
int nw[2], nx[2];
nw[0] = nw[1] = inf;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
for (int k = 0; k < 2; ++k) {
nw[i] = min(nw[i], (i ^ j) + t[v].t[1][j][k]);
}
}
}
t[v].add(1, ll[v], rr[v], tin[u], v0, v1);
nx[0] = nx[1] = inf;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
for (int k = 0; k < 2; ++k) {
nx[i] = min(nx[i], (i ^ j) + t[v].t[1][j][k]);
}
}
}
u = par[v], v0 = nx[0] - nw[0], v1 = nx[1] - nw[1];
}
t[1].add(1, ll[1], rr[1], tin[u], v0, v1);
}
int go() {
int ans = inf;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
ans = min(ans, t[1].t[1][i][j]);
}
}
return ans;
}
int cat(int u) {
a[u] = 0; add(u, 0, inf); return go();
}
int dog(int u) {
a[u] = 1; add(u, inf, 0); return go();
}
int neighbor(int u) {
if (a[u]) add(u, -inf, 0);
else add(u, 0, -inf);
return go();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5120 KB |
Output is correct |
2 |
Correct |
8 ms |
5120 KB |
Output is correct |
3 |
Correct |
8 ms |
5120 KB |
Output is correct |
4 |
Correct |
7 ms |
4992 KB |
Output is correct |
5 |
Correct |
8 ms |
5120 KB |
Output is correct |
6 |
Correct |
6 ms |
4992 KB |
Output is correct |
7 |
Correct |
6 ms |
4992 KB |
Output is correct |
8 |
Correct |
7 ms |
4992 KB |
Output is correct |
9 |
Correct |
6 ms |
5120 KB |
Output is correct |
10 |
Correct |
5 ms |
5120 KB |
Output is correct |
11 |
Correct |
7 ms |
5120 KB |
Output is correct |
12 |
Correct |
7 ms |
4992 KB |
Output is correct |
13 |
Correct |
7 ms |
4992 KB |
Output is correct |
14 |
Correct |
6 ms |
5120 KB |
Output is correct |
15 |
Correct |
8 ms |
5120 KB |
Output is correct |
16 |
Correct |
7 ms |
4992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5120 KB |
Output is correct |
2 |
Correct |
8 ms |
5120 KB |
Output is correct |
3 |
Correct |
8 ms |
5120 KB |
Output is correct |
4 |
Correct |
7 ms |
4992 KB |
Output is correct |
5 |
Correct |
8 ms |
5120 KB |
Output is correct |
6 |
Correct |
6 ms |
4992 KB |
Output is correct |
7 |
Correct |
6 ms |
4992 KB |
Output is correct |
8 |
Correct |
7 ms |
4992 KB |
Output is correct |
9 |
Correct |
6 ms |
5120 KB |
Output is correct |
10 |
Correct |
5 ms |
5120 KB |
Output is correct |
11 |
Correct |
7 ms |
5120 KB |
Output is correct |
12 |
Correct |
7 ms |
4992 KB |
Output is correct |
13 |
Correct |
7 ms |
4992 KB |
Output is correct |
14 |
Correct |
6 ms |
5120 KB |
Output is correct |
15 |
Correct |
8 ms |
5120 KB |
Output is correct |
16 |
Correct |
7 ms |
4992 KB |
Output is correct |
17 |
Correct |
9 ms |
5248 KB |
Output is correct |
18 |
Correct |
8 ms |
5248 KB |
Output is correct |
19 |
Correct |
7 ms |
5120 KB |
Output is correct |
20 |
Correct |
6 ms |
5120 KB |
Output is correct |
21 |
Correct |
8 ms |
5120 KB |
Output is correct |
22 |
Correct |
7 ms |
5120 KB |
Output is correct |
23 |
Correct |
8 ms |
5248 KB |
Output is correct |
24 |
Correct |
8 ms |
5248 KB |
Output is correct |
25 |
Correct |
9 ms |
5120 KB |
Output is correct |
26 |
Correct |
7 ms |
5120 KB |
Output is correct |
27 |
Correct |
8 ms |
5120 KB |
Output is correct |
28 |
Correct |
9 ms |
5120 KB |
Output is correct |
29 |
Correct |
7 ms |
5248 KB |
Output is correct |
30 |
Correct |
7 ms |
5120 KB |
Output is correct |
31 |
Correct |
8 ms |
5248 KB |
Output is correct |
32 |
Correct |
7 ms |
5120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5120 KB |
Output is correct |
2 |
Correct |
8 ms |
5120 KB |
Output is correct |
3 |
Correct |
8 ms |
5120 KB |
Output is correct |
4 |
Correct |
7 ms |
4992 KB |
Output is correct |
5 |
Correct |
8 ms |
5120 KB |
Output is correct |
6 |
Correct |
6 ms |
4992 KB |
Output is correct |
7 |
Correct |
6 ms |
4992 KB |
Output is correct |
8 |
Correct |
7 ms |
4992 KB |
Output is correct |
9 |
Correct |
6 ms |
5120 KB |
Output is correct |
10 |
Correct |
5 ms |
5120 KB |
Output is correct |
11 |
Correct |
7 ms |
5120 KB |
Output is correct |
12 |
Correct |
7 ms |
4992 KB |
Output is correct |
13 |
Correct |
7 ms |
4992 KB |
Output is correct |
14 |
Correct |
6 ms |
5120 KB |
Output is correct |
15 |
Correct |
8 ms |
5120 KB |
Output is correct |
16 |
Correct |
7 ms |
4992 KB |
Output is correct |
17 |
Correct |
9 ms |
5248 KB |
Output is correct |
18 |
Correct |
8 ms |
5248 KB |
Output is correct |
19 |
Correct |
7 ms |
5120 KB |
Output is correct |
20 |
Correct |
6 ms |
5120 KB |
Output is correct |
21 |
Correct |
8 ms |
5120 KB |
Output is correct |
22 |
Correct |
7 ms |
5120 KB |
Output is correct |
23 |
Correct |
8 ms |
5248 KB |
Output is correct |
24 |
Correct |
8 ms |
5248 KB |
Output is correct |
25 |
Correct |
9 ms |
5120 KB |
Output is correct |
26 |
Correct |
7 ms |
5120 KB |
Output is correct |
27 |
Correct |
8 ms |
5120 KB |
Output is correct |
28 |
Correct |
9 ms |
5120 KB |
Output is correct |
29 |
Correct |
7 ms |
5248 KB |
Output is correct |
30 |
Correct |
7 ms |
5120 KB |
Output is correct |
31 |
Correct |
8 ms |
5248 KB |
Output is correct |
32 |
Correct |
7 ms |
5120 KB |
Output is correct |
33 |
Correct |
216 ms |
15592 KB |
Output is correct |
34 |
Correct |
158 ms |
16760 KB |
Output is correct |
35 |
Correct |
211 ms |
12784 KB |
Output is correct |
36 |
Correct |
385 ms |
22588 KB |
Output is correct |
37 |
Correct |
57 ms |
10488 KB |
Output is correct |
38 |
Correct |
469 ms |
24200 KB |
Output is correct |
39 |
Correct |
513 ms |
24168 KB |
Output is correct |
40 |
Correct |
509 ms |
24212 KB |
Output is correct |
41 |
Correct |
432 ms |
24168 KB |
Output is correct |
42 |
Correct |
391 ms |
24164 KB |
Output is correct |
43 |
Correct |
388 ms |
24168 KB |
Output is correct |
44 |
Correct |
341 ms |
24168 KB |
Output is correct |
45 |
Correct |
343 ms |
24220 KB |
Output is correct |
46 |
Correct |
370 ms |
24164 KB |
Output is correct |
47 |
Correct |
344 ms |
24296 KB |
Output is correct |
48 |
Correct |
110 ms |
22592 KB |
Output is correct |
49 |
Correct |
165 ms |
26784 KB |
Output is correct |
50 |
Correct |
38 ms |
9848 KB |
Output is correct |
51 |
Correct |
47 ms |
13648 KB |
Output is correct |
52 |
Correct |
27 ms |
9472 KB |
Output is correct |
53 |
Correct |
205 ms |
23032 KB |
Output is correct |
54 |
Correct |
83 ms |
13104 KB |
Output is correct |
55 |
Correct |
267 ms |
18816 KB |
Output is correct |
56 |
Correct |
155 ms |
14240 KB |
Output is correct |
57 |
Correct |
254 ms |
21904 KB |
Output is correct |
58 |
Correct |
53 ms |
14580 KB |
Output is correct |
59 |
Correct |
52 ms |
12952 KB |
Output is correct |
60 |
Correct |
112 ms |
24404 KB |
Output is correct |
61 |
Correct |
117 ms |
25128 KB |
Output is correct |
62 |
Correct |
94 ms |
21360 KB |
Output is correct |
63 |
Correct |
74 ms |
14840 KB |
Output is correct |
64 |
Correct |
85 ms |
16120 KB |
Output is correct |
65 |
Correct |
154 ms |
22900 KB |
Output is correct |
66 |
Correct |
62 ms |
9848 KB |
Output is correct |
67 |
Correct |
108 ms |
17628 KB |
Output is correct |
68 |
Correct |
195 ms |
23160 KB |
Output is correct |
69 |
Correct |
32 ms |
6776 KB |
Output is correct |
70 |
Correct |
14 ms |
5372 KB |
Output is correct |
71 |
Correct |
83 ms |
13176 KB |
Output is correct |
72 |
Correct |
135 ms |
19812 KB |
Output is correct |
73 |
Correct |
265 ms |
24952 KB |
Output is correct |
74 |
Correct |
271 ms |
22904 KB |
Output is correct |
75 |
Correct |
229 ms |
24952 KB |
Output is correct |
76 |
Correct |
222 ms |
24184 KB |
Output is correct |
77 |
Correct |
249 ms |
23196 KB |
Output is correct |