#include "catdog.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 1<<17;
const int INF = 1e9+1;
#define var int p = 1, int l = 1, int r = n
#define mid ((l + r) >> 1)
#define lb p<<1, l, mid
#define rb p<<1|1, mid+1, r
struct node {
vector<int> v;
node() {
v = vector<int>(4, INF);
v[0] = v[3] = 0;
}
node(int a) { v = vector<int>(4, a); }
int ans() {
int ret = INF;
for(int i = 0; i < 4; i++) ret = min(ret, v[i]);
return ret;
}
friend node operator+(const node &a, const node &b) {
node ret(INF);
for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) {
int bit = (i & 2) + (j & 1);
bool dif = (i & 1) != (j >> 1 & 1);
ret.v[bit] = min(ret.v[bit], a.v[i] + b.v[j] + dif);
}
return ret;
}
} t[N<<1];
int n, col[N];
int par[N], rot[N], spi[N], pos[N], lev[N];
pii pv[N];
vector<int> g[N];
int dfs(int u, int p) {
par[u] = p;
int sz = 1; pii ret(0, -1);
for(int v : g[u]) if(v != p) {
int z = dfs(v, u);
sz += z, ret = max(ret, pii(z, v));
}
spi[u] = ret.y;
return sz;
}
void build(var) {
if(l == r) return;
build(lb), build(rb);
t[p] = t[p<<1] + t[p<<1|1];
}
void update(int x, pii k, var) {
if(l == r) {
t[p].v[0] += k.x, t[p].v[3] += k.y;
return;
}
if(x <= mid) update(x, k, lb);
else update(x, k, rb);
t[p] = t[p<<1] + t[p<<1|1];
}
node query(int x, int y, var) {
if(x <= l && r <= y) return t[p];
if(y <= mid) return query(x, y, lb);
if(x > mid) return query(x, y, rb);
return query(x, y, lb) + query(x, y, rb);
}
void hld() {
for(int i = 1, idx = 0; i <= n; i++) if(spi[par[i]] != i)
for(int j = i; j != -1; j = spi[j])
rot[j] = i, lev[i] = j, pos[j] = ++idx;
build();
}
void initialize(int _n, vector<int> A, vector<int> B) {
n = _n;
for(int i = 0; i < n-1; i++) {
g[A[i]].emplace_back(B[i]);
g[B[i]].emplace_back(A[i]);
}
dfs(1, 0), hld();
}
void update(int v, int a, int b) {
while(v) {
update(pos[v], pii(a, b));
node now = query(pos[rot[v]], pos[lev[rot[v]]]);
int x = min(now.v[0], now.v[1]), y = min(now.v[2], now.v[3]);
pii upd(min(x, y+1), min(x+1, y));
a = upd.x - pv[rot[v]].x, b = upd.y - pv[rot[v]].y;
pv[rot[v]] = upd;
v = par[rot[v]];
}
}
int cat(int v) {
col[v] = 1;
update(v, 0, INF);
return query(pos[1], pos[lev[1]]).ans();
}
int dog(int v) {
col[v] = 2;
update(v, INF, 0);
return query(pos[1], pos[lev[1]]).ans();
}
int neighbor(int v) {
if(col[v] == 1) update(v, 0, -INF);
if(col[v] == 2) update(v, -INF, 0);
col[v] = 0;
return query(pos[1], pos[lev[1]]).ans();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
17792 KB |
Output is correct |
2 |
Correct |
26 ms |
17912 KB |
Output is correct |
3 |
Correct |
29 ms |
17788 KB |
Output is correct |
4 |
Correct |
31 ms |
17792 KB |
Output is correct |
5 |
Correct |
36 ms |
17792 KB |
Output is correct |
6 |
Correct |
30 ms |
17792 KB |
Output is correct |
7 |
Correct |
26 ms |
17792 KB |
Output is correct |
8 |
Correct |
28 ms |
17792 KB |
Output is correct |
9 |
Correct |
29 ms |
17784 KB |
Output is correct |
10 |
Correct |
32 ms |
17792 KB |
Output is correct |
11 |
Correct |
31 ms |
17912 KB |
Output is correct |
12 |
Correct |
28 ms |
17792 KB |
Output is correct |
13 |
Correct |
33 ms |
17840 KB |
Output is correct |
14 |
Correct |
27 ms |
17920 KB |
Output is correct |
15 |
Correct |
26 ms |
17792 KB |
Output is correct |
16 |
Correct |
29 ms |
17792 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
17792 KB |
Output is correct |
2 |
Correct |
26 ms |
17912 KB |
Output is correct |
3 |
Correct |
29 ms |
17788 KB |
Output is correct |
4 |
Correct |
31 ms |
17792 KB |
Output is correct |
5 |
Correct |
36 ms |
17792 KB |
Output is correct |
6 |
Correct |
30 ms |
17792 KB |
Output is correct |
7 |
Correct |
26 ms |
17792 KB |
Output is correct |
8 |
Correct |
28 ms |
17792 KB |
Output is correct |
9 |
Correct |
29 ms |
17784 KB |
Output is correct |
10 |
Correct |
32 ms |
17792 KB |
Output is correct |
11 |
Correct |
31 ms |
17912 KB |
Output is correct |
12 |
Correct |
28 ms |
17792 KB |
Output is correct |
13 |
Correct |
33 ms |
17840 KB |
Output is correct |
14 |
Correct |
27 ms |
17920 KB |
Output is correct |
15 |
Correct |
26 ms |
17792 KB |
Output is correct |
16 |
Correct |
29 ms |
17792 KB |
Output is correct |
17 |
Correct |
38 ms |
17888 KB |
Output is correct |
18 |
Correct |
33 ms |
17892 KB |
Output is correct |
19 |
Correct |
30 ms |
17920 KB |
Output is correct |
20 |
Correct |
41 ms |
17912 KB |
Output is correct |
21 |
Correct |
27 ms |
17912 KB |
Output is correct |
22 |
Correct |
29 ms |
17920 KB |
Output is correct |
23 |
Correct |
29 ms |
17920 KB |
Output is correct |
24 |
Correct |
38 ms |
17912 KB |
Output is correct |
25 |
Correct |
31 ms |
17912 KB |
Output is correct |
26 |
Correct |
22 ms |
17788 KB |
Output is correct |
27 |
Correct |
28 ms |
17884 KB |
Output is correct |
28 |
Correct |
27 ms |
17912 KB |
Output is correct |
29 |
Correct |
40 ms |
17940 KB |
Output is correct |
30 |
Correct |
31 ms |
17792 KB |
Output is correct |
31 |
Correct |
28 ms |
17920 KB |
Output is correct |
32 |
Correct |
30 ms |
17792 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
17792 KB |
Output is correct |
2 |
Correct |
26 ms |
17912 KB |
Output is correct |
3 |
Correct |
29 ms |
17788 KB |
Output is correct |
4 |
Correct |
31 ms |
17792 KB |
Output is correct |
5 |
Correct |
36 ms |
17792 KB |
Output is correct |
6 |
Correct |
30 ms |
17792 KB |
Output is correct |
7 |
Correct |
26 ms |
17792 KB |
Output is correct |
8 |
Correct |
28 ms |
17792 KB |
Output is correct |
9 |
Correct |
29 ms |
17784 KB |
Output is correct |
10 |
Correct |
32 ms |
17792 KB |
Output is correct |
11 |
Correct |
31 ms |
17912 KB |
Output is correct |
12 |
Correct |
28 ms |
17792 KB |
Output is correct |
13 |
Correct |
33 ms |
17840 KB |
Output is correct |
14 |
Correct |
27 ms |
17920 KB |
Output is correct |
15 |
Correct |
26 ms |
17792 KB |
Output is correct |
16 |
Correct |
29 ms |
17792 KB |
Output is correct |
17 |
Correct |
38 ms |
17888 KB |
Output is correct |
18 |
Correct |
33 ms |
17892 KB |
Output is correct |
19 |
Correct |
30 ms |
17920 KB |
Output is correct |
20 |
Correct |
41 ms |
17912 KB |
Output is correct |
21 |
Correct |
27 ms |
17912 KB |
Output is correct |
22 |
Correct |
29 ms |
17920 KB |
Output is correct |
23 |
Correct |
29 ms |
17920 KB |
Output is correct |
24 |
Correct |
38 ms |
17912 KB |
Output is correct |
25 |
Correct |
31 ms |
17912 KB |
Output is correct |
26 |
Correct |
22 ms |
17788 KB |
Output is correct |
27 |
Correct |
28 ms |
17884 KB |
Output is correct |
28 |
Correct |
27 ms |
17912 KB |
Output is correct |
29 |
Correct |
40 ms |
17940 KB |
Output is correct |
30 |
Correct |
31 ms |
17792 KB |
Output is correct |
31 |
Correct |
28 ms |
17920 KB |
Output is correct |
32 |
Correct |
30 ms |
17792 KB |
Output is correct |
33 |
Correct |
1455 ms |
23828 KB |
Output is correct |
34 |
Correct |
367 ms |
23632 KB |
Output is correct |
35 |
Correct |
1180 ms |
22640 KB |
Output is correct |
36 |
Correct |
2200 ms |
27800 KB |
Output is correct |
37 |
Correct |
71 ms |
20728 KB |
Output is correct |
38 |
Correct |
2510 ms |
28732 KB |
Output is correct |
39 |
Correct |
2392 ms |
28644 KB |
Output is correct |
40 |
Correct |
2251 ms |
28620 KB |
Output is correct |
41 |
Correct |
2545 ms |
28748 KB |
Output is correct |
42 |
Correct |
2270 ms |
28780 KB |
Output is correct |
43 |
Correct |
2558 ms |
28640 KB |
Output is correct |
44 |
Correct |
2237 ms |
28652 KB |
Output is correct |
45 |
Correct |
2241 ms |
28648 KB |
Output is correct |
46 |
Correct |
2400 ms |
28648 KB |
Output is correct |
47 |
Correct |
2444 ms |
28552 KB |
Output is correct |
48 |
Correct |
583 ms |
25636 KB |
Output is correct |
49 |
Correct |
610 ms |
27416 KB |
Output is correct |
50 |
Correct |
228 ms |
20216 KB |
Output is correct |
51 |
Correct |
246 ms |
21596 KB |
Output is correct |
52 |
Correct |
89 ms |
19804 KB |
Output is correct |
53 |
Correct |
945 ms |
27032 KB |
Output is correct |
54 |
Correct |
757 ms |
22192 KB |
Output is correct |
55 |
Correct |
1858 ms |
25712 KB |
Output is correct |
56 |
Correct |
1072 ms |
23048 KB |
Output is correct |
57 |
Correct |
1524 ms |
26804 KB |
Output is correct |
58 |
Correct |
114 ms |
21612 KB |
Output is correct |
59 |
Correct |
219 ms |
21368 KB |
Output is correct |
60 |
Correct |
529 ms |
26616 KB |
Output is correct |
61 |
Correct |
508 ms |
26848 KB |
Output is correct |
62 |
Correct |
252 ms |
24848 KB |
Output is correct |
63 |
Correct |
186 ms |
25208 KB |
Output is correct |
64 |
Correct |
188 ms |
27100 KB |
Output is correct |
65 |
Correct |
203 ms |
31992 KB |
Output is correct |
66 |
Correct |
274 ms |
21580 KB |
Output is correct |
67 |
Correct |
240 ms |
27900 KB |
Output is correct |
68 |
Correct |
551 ms |
32220 KB |
Output is correct |
69 |
Correct |
232 ms |
19448 KB |
Output is correct |
70 |
Correct |
47 ms |
18040 KB |
Output is correct |
71 |
Correct |
315 ms |
25080 KB |
Output is correct |
72 |
Correct |
292 ms |
30584 KB |
Output is correct |
73 |
Correct |
1034 ms |
36220 KB |
Output is correct |
74 |
Correct |
833 ms |
31864 KB |
Output is correct |
75 |
Correct |
662 ms |
36120 KB |
Output is correct |
76 |
Correct |
483 ms |
34580 KB |
Output is correct |
77 |
Correct |
859 ms |
32248 KB |
Output is correct |