#include "catdog.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int maxn = 1e5 + 4;
const int INF = 1e9;
int n, sz[maxn], R[maxn], B[maxn], col[maxn], par[maxn], id[maxn];
int chain[maxn], head[maxn], from[maxn], to[maxn], tin[maxn];
vector<int> adj[maxn];
struct Node {
int a[2][2];
Node() {
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
a[i][j] = INF;
}
};
struct seg_tree {
vector<Node> t;
seg_tree() {
t.resize(4 * maxn);
}
Node merge(Node L, Node R) {
Node res;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int x = 0; x < 2; x++)
for (int y = 0; y < 2; y++)
res.a[i][j] = min(res.a[i][j], L.a[i][x] + R.a[y][j] + (x != y));
return res;
}
void update(int pos, int v = 1, int l = 1, int r = maxn - 1) {
if (l == r) {
t[v].a[0][0] = (col[id[l]] == 1 ? INF : R[id[l]]);
t[v].a[1][1] = (col[id[l]] == 0 ? INF : B[id[l]]);
t[v].a[0][1] = t[v].a[1][0] = INF;
return;
}
int m = (l + r) / 2;
if (pos <= m) update(pos, 2 * v, l, m);
else update(pos, 2 * v + 1, m + 1, r);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
Node get(int l, int r, int v = 1, int tl = 1, int tr = maxn - 1) {
if (tl >= l && tr <= r) return t[v];
int m = (tl + tr) / 2;
if (r <= m) return get(l, r, 2 * v, tl, m);
else if (l > m) return get(l, r, 2 * v + 1, m + 1, tr);
else return merge(get(l, r, 2 * v, tl, m), get(l, r, 2 * v + 1, m + 1, tr));
}
} IT;
void dfs(int u, int p) {
sz[u] = 1;
for (int v : adj[u]) if (v != p) {
par[v] = u;
dfs(v, u);
sz[u] += sz[v];
}
}
void hld(int u) {
tin[u] = ++tin[0];
id[tin[0]] = u;
chain[u] = chain[0];
if (!head[chain[0]]) head[chain[0]] = u;
int mx = 0;
for (int v : adj[u])
if (v != par[u] && sz[v] > sz[mx])
mx = v;
if (mx) hld(mx);
for (int v : adj[u])
if (v != par[u] && v != mx) {
chain[0]++;
hld(v);
}
}
void update(int v) {
while (v) {
int u = par[head[chain[v]]];
Node cur = IT.get(from[chain[v]], to[chain[v]]);
R[u] -= min({cur.a[0][0], cur.a[0][1], cur.a[1][0] + 1, cur.a[1][1] + 1});
B[u] -= min({cur.a[0][0] + 1, cur.a[0][1] + 1, cur.a[1][0], cur.a[1][1]});
IT.update(tin[v]);
cur = IT.get(from[chain[v]], to[chain[v]]);
R[u] += min({cur.a[0][0], cur.a[0][1], cur.a[1][0] + 1, cur.a[1][1] + 1});
B[u] += min({cur.a[0][0] + 1, cur.a[0][1] + 1, cur.a[1][0], cur.a[1][1]});
v = u;
}
}
int get() {
Node cur = IT.get(from[0], to[0]);
int res = INF;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
res = min(res, cur.a[i][j]);
return res;
}
void initialize(int N, vector<int> A, vector<int> B) {
n = N;
for (int i = 0; i < n - 1; i++) {
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
}
dfs(1, 0);
hld(1);
for (int i = 0; i <= chain[0]; i++)
from[i] = INF;
for (int i = 1; i <= n; i++) {
from[chain[i]] = min(from[chain[i]], tin[i]);
to[chain[i]] = max(to[chain[i]], tin[i]);
col[i] = -1;
}
for (int i = 1; i <= n; i++)
IT.update(i);
}
int cat(int v) {
col[v] = 0;
update(v);
return get();
}
int dog(int v) {
col[v] = 1;
update(v);
return get();
}
int neighbor(int v) {
col[v] = -1;
update(v);
return get();
}
// int main()
// {
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// if (fopen("Pets.INP", "r")) {
// freopen("Pets.INP", "r", stdin);
// freopen("Pets.OUT", "w", stdout);
// }
// cin >> n;
// for (int i = 1, u, v; i < n; i++) {
// cin >> u >> v;
// adj[u].pb(v);
// adj[v].pb(u);
// }
// dfs(1, 0);
// hld(1);
// for (int i = 0; i <= chain[0]; i++)
// from[i] = INF;
// for (int i = 1; i <= n; i++) {
// from[chain[i]] = min(from[chain[i]], tin[i]);
// to[chain[i]] = max(to[chain[i]], tin[i]);
// col[i] = -1;
// }
// for (int i = 1; i <= n; i++)
// IT.update(i);
// int q; cin >> q;
// while (q--) {
// int t, u; cin >> t >> u;
// if (t == 1) col[u] = 0;
// if (t == 2) col[u] = 1;
// if (t == 3) col[u] = -1;
// update(u);
// cout << get() << '\n';
// }
// }
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12888 KB |
Output is correct |
2 |
Correct |
3 ms |
12888 KB |
Output is correct |
3 |
Correct |
4 ms |
13144 KB |
Output is correct |
4 |
Correct |
3 ms |
12888 KB |
Output is correct |
5 |
Correct |
3 ms |
12888 KB |
Output is correct |
6 |
Correct |
3 ms |
12888 KB |
Output is correct |
7 |
Correct |
3 ms |
12888 KB |
Output is correct |
8 |
Correct |
3 ms |
12892 KB |
Output is correct |
9 |
Correct |
3 ms |
12888 KB |
Output is correct |
10 |
Correct |
3 ms |
12888 KB |
Output is correct |
11 |
Correct |
3 ms |
13040 KB |
Output is correct |
12 |
Correct |
3 ms |
12888 KB |
Output is correct |
13 |
Correct |
3 ms |
12888 KB |
Output is correct |
14 |
Correct |
3 ms |
13040 KB |
Output is correct |
15 |
Correct |
3 ms |
12892 KB |
Output is correct |
16 |
Correct |
3 ms |
12888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12888 KB |
Output is correct |
2 |
Correct |
3 ms |
12888 KB |
Output is correct |
3 |
Correct |
4 ms |
13144 KB |
Output is correct |
4 |
Correct |
3 ms |
12888 KB |
Output is correct |
5 |
Correct |
3 ms |
12888 KB |
Output is correct |
6 |
Correct |
3 ms |
12888 KB |
Output is correct |
7 |
Correct |
3 ms |
12888 KB |
Output is correct |
8 |
Correct |
3 ms |
12892 KB |
Output is correct |
9 |
Correct |
3 ms |
12888 KB |
Output is correct |
10 |
Correct |
3 ms |
12888 KB |
Output is correct |
11 |
Correct |
3 ms |
13040 KB |
Output is correct |
12 |
Correct |
3 ms |
12888 KB |
Output is correct |
13 |
Correct |
3 ms |
12888 KB |
Output is correct |
14 |
Correct |
3 ms |
13040 KB |
Output is correct |
15 |
Correct |
3 ms |
12892 KB |
Output is correct |
16 |
Correct |
3 ms |
12888 KB |
Output is correct |
17 |
Correct |
5 ms |
12888 KB |
Output is correct |
18 |
Correct |
5 ms |
12888 KB |
Output is correct |
19 |
Correct |
4 ms |
12888 KB |
Output is correct |
20 |
Correct |
3 ms |
12888 KB |
Output is correct |
21 |
Correct |
4 ms |
12888 KB |
Output is correct |
22 |
Correct |
4 ms |
12892 KB |
Output is correct |
23 |
Correct |
6 ms |
12892 KB |
Output is correct |
24 |
Correct |
5 ms |
12888 KB |
Output is correct |
25 |
Correct |
5 ms |
12888 KB |
Output is correct |
26 |
Correct |
5 ms |
12888 KB |
Output is correct |
27 |
Correct |
3 ms |
12888 KB |
Output is correct |
28 |
Correct |
4 ms |
12888 KB |
Output is correct |
29 |
Correct |
5 ms |
13144 KB |
Output is correct |
30 |
Correct |
4 ms |
12892 KB |
Output is correct |
31 |
Correct |
4 ms |
12888 KB |
Output is correct |
32 |
Correct |
4 ms |
12892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12888 KB |
Output is correct |
2 |
Correct |
3 ms |
12888 KB |
Output is correct |
3 |
Correct |
4 ms |
13144 KB |
Output is correct |
4 |
Correct |
3 ms |
12888 KB |
Output is correct |
5 |
Correct |
3 ms |
12888 KB |
Output is correct |
6 |
Correct |
3 ms |
12888 KB |
Output is correct |
7 |
Correct |
3 ms |
12888 KB |
Output is correct |
8 |
Correct |
3 ms |
12892 KB |
Output is correct |
9 |
Correct |
3 ms |
12888 KB |
Output is correct |
10 |
Correct |
3 ms |
12888 KB |
Output is correct |
11 |
Correct |
3 ms |
13040 KB |
Output is correct |
12 |
Correct |
3 ms |
12888 KB |
Output is correct |
13 |
Correct |
3 ms |
12888 KB |
Output is correct |
14 |
Correct |
3 ms |
13040 KB |
Output is correct |
15 |
Correct |
3 ms |
12892 KB |
Output is correct |
16 |
Correct |
3 ms |
12888 KB |
Output is correct |
17 |
Correct |
5 ms |
12888 KB |
Output is correct |
18 |
Correct |
5 ms |
12888 KB |
Output is correct |
19 |
Correct |
4 ms |
12888 KB |
Output is correct |
20 |
Correct |
3 ms |
12888 KB |
Output is correct |
21 |
Correct |
4 ms |
12888 KB |
Output is correct |
22 |
Correct |
4 ms |
12892 KB |
Output is correct |
23 |
Correct |
6 ms |
12892 KB |
Output is correct |
24 |
Correct |
5 ms |
12888 KB |
Output is correct |
25 |
Correct |
5 ms |
12888 KB |
Output is correct |
26 |
Correct |
5 ms |
12888 KB |
Output is correct |
27 |
Correct |
3 ms |
12888 KB |
Output is correct |
28 |
Correct |
4 ms |
12888 KB |
Output is correct |
29 |
Correct |
5 ms |
13144 KB |
Output is correct |
30 |
Correct |
4 ms |
12892 KB |
Output is correct |
31 |
Correct |
4 ms |
12888 KB |
Output is correct |
32 |
Correct |
4 ms |
12892 KB |
Output is correct |
33 |
Correct |
295 ms |
17340 KB |
Output is correct |
34 |
Correct |
106 ms |
17232 KB |
Output is correct |
35 |
Correct |
263 ms |
16708 KB |
Output is correct |
36 |
Correct |
406 ms |
20116 KB |
Output is correct |
37 |
Correct |
25 ms |
14680 KB |
Output is correct |
38 |
Correct |
442 ms |
20800 KB |
Output is correct |
39 |
Correct |
484 ms |
20928 KB |
Output is correct |
40 |
Correct |
474 ms |
21052 KB |
Output is correct |
41 |
Correct |
447 ms |
20816 KB |
Output is correct |
42 |
Correct |
436 ms |
20944 KB |
Output is correct |
43 |
Correct |
427 ms |
20816 KB |
Output is correct |
44 |
Correct |
440 ms |
20940 KB |
Output is correct |
45 |
Correct |
448 ms |
20828 KB |
Output is correct |
46 |
Correct |
446 ms |
20852 KB |
Output is correct |
47 |
Correct |
443 ms |
20816 KB |
Output is correct |
48 |
Correct |
149 ms |
18632 KB |
Output is correct |
49 |
Correct |
160 ms |
20004 KB |
Output is correct |
50 |
Correct |
61 ms |
14640 KB |
Output is correct |
51 |
Correct |
68 ms |
15564 KB |
Output is correct |
52 |
Correct |
32 ms |
14168 KB |
Output is correct |
53 |
Correct |
199 ms |
19548 KB |
Output is correct |
54 |
Correct |
155 ms |
16136 KB |
Output is correct |
55 |
Correct |
365 ms |
18928 KB |
Output is correct |
56 |
Correct |
252 ms |
16884 KB |
Output is correct |
57 |
Correct |
326 ms |
19536 KB |
Output is correct |
58 |
Correct |
41 ms |
16084 KB |
Output is correct |
59 |
Correct |
67 ms |
15448 KB |
Output is correct |
60 |
Correct |
143 ms |
19376 KB |
Output is correct |
61 |
Correct |
174 ms |
19876 KB |
Output is correct |
62 |
Correct |
97 ms |
18124 KB |
Output is correct |
63 |
Correct |
62 ms |
19024 KB |
Output is correct |
64 |
Correct |
68 ms |
20560 KB |
Output is correct |
65 |
Correct |
89 ms |
24668 KB |
Output is correct |
66 |
Correct |
97 ms |
16120 KB |
Output is correct |
67 |
Correct |
105 ms |
21328 KB |
Output is correct |
68 |
Correct |
182 ms |
25220 KB |
Output is correct |
69 |
Correct |
38 ms |
14416 KB |
Output is correct |
70 |
Correct |
12 ms |
13144 KB |
Output is correct |
71 |
Correct |
77 ms |
18768 KB |
Output is correct |
72 |
Correct |
109 ms |
23632 KB |
Output is correct |
73 |
Correct |
285 ms |
28240 KB |
Output is correct |
74 |
Correct |
289 ms |
24812 KB |
Output is correct |
75 |
Correct |
207 ms |
28280 KB |
Output is correct |
76 |
Correct |
191 ms |
27116 KB |
Output is correct |
77 |
Correct |
295 ms |
25052 KB |
Output is correct |