#include <bits/stdc++.h>
using namespace std;
const int maxn = 101010;
vector<int>adj[maxn];
int pa[maxn], sz[maxn];
void dfs(int i, int p)
{
pa[i] = p;
sz[i] = 1;
pair<int, int>mx = {0, 0};
for (int t = 0; t < (int)adj[i].size(); t++)
{
int j = adj[i][t];
if (j == p)
continue;
dfs(j, i);
sz[i] += sz[j];
mx = max(mx, {sz[j], t});
}
swap(adj[i][0], adj[i][mx.second]);
}
int timer = 1;
int nr[maxn], head[maxn], tail[maxn];
void hld(int i, int p, int h)
{
nr[i] = timer++;
head[i] = h;
tail[h] = i;
for (int t = 0; t < (int)adj[i].size(); t++)
{
int j = adj[i][t];
if (j != p)
hld(j, i, t == 0 ? h : j);
}
}
struct line
{
int cc = 0, cd = maxn, dd = 0, dc = maxn;
line() {}
int mn(int c)
{
if (c)
return min({cd, cc, dc + 1, dd + 1});
else
return min({cd + 1, cc + 1, dc, dd});
}
};
line merge(line a, line b)
{
line c;
c.cc = min({a.cc + b.cc, a.cc + b.dc + 1, a.cd + b.cc + 1, a.cd + b.dc});
c.cd = min({a.cc + b.cd, a.cc + b.dd + 1, a.cd + b.cd + 1, a.cd + b.dd});
c.dd = min({a.dc + b.cd, a.dc + b.dd + 1, a.dd + b.cd + 1, a.dd + b.dd});
c.dc = min({a.dc + b.cc, a.dc + b.dc + 1, a.dd + b.cc + 1, a.dd + b.dc});
return c;
}
struct ST
{
line X;
int l, r;
ST *left, *right;
ST(int l, int r): l(l), r(r)
{
if (l < r)
{
left = new ST(l, (l + r) / 2);
right = new ST((l + r) / 2 + 1, r);
X = merge(left->X, right->X);
}
}
line get(int x, int y)
{
if (x <= l && r <= y)
return X;
if (r < x || y < l)
return line();
return merge(left->get(x, y), right->get(x, y));
}
void set(int x, int w, int c)
{
if (l == r)
{
if (c)
X.cc = w;
else
X.dd = w;
}
else
{
if (x <= (l + r) / 2)
left->set(x, w, c);
else
right->set(x, w, c);
X = merge(left->X, right->X);
}
}
} medis(0, 101010);
void initialize(int N, vector<int> A, vector<int> B)
{
for (int i = 0; i < N - 1; i++)
{
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
dfs(1, 0);
hld(1, 0, 1);
}
int C[maxn], D[maxn], V[maxn];
int fix(int v, int p)
{
V[v] = p;
while (true)
{
int w = head[v];
line X = medis.get(nr[w], nr[tail[w]]);
C[pa[w]] -= X.mn(1);
D[pa[w]] -= X.mn(0);
medis.set(nr[v], V[v] == 1 ? maxn : C[v], 1);
medis.set(nr[v], V[v] == -1 ? maxn : D[v], 0);
X = medis.get(nr[w], nr[tail[w]]);
C[pa[w]] += X.mn(1);
D[pa[w]] += X.mn(0);
if (v == 1)break;
if (v != w)
v = w;
else
v = pa[v];
}
return min(C[0], D[0]);
}
int cat(int v)
{
return fix(v, -1);
}
int dog(int v)
{
return fix(v, 1);
}
int neighbor(int v)
{
return fix(v, 0);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
12280 KB |
Output is correct |
2 |
Correct |
18 ms |
12152 KB |
Output is correct |
3 |
Correct |
18 ms |
12152 KB |
Output is correct |
4 |
Correct |
19 ms |
12152 KB |
Output is correct |
5 |
Correct |
20 ms |
12280 KB |
Output is correct |
6 |
Correct |
21 ms |
12152 KB |
Output is correct |
7 |
Correct |
21 ms |
12152 KB |
Output is correct |
8 |
Correct |
21 ms |
12280 KB |
Output is correct |
9 |
Correct |
19 ms |
12152 KB |
Output is correct |
10 |
Correct |
19 ms |
12196 KB |
Output is correct |
11 |
Correct |
19 ms |
12280 KB |
Output is correct |
12 |
Correct |
19 ms |
12280 KB |
Output is correct |
13 |
Correct |
19 ms |
12280 KB |
Output is correct |
14 |
Correct |
19 ms |
12280 KB |
Output is correct |
15 |
Correct |
19 ms |
12280 KB |
Output is correct |
16 |
Correct |
19 ms |
12156 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
12280 KB |
Output is correct |
2 |
Correct |
18 ms |
12152 KB |
Output is correct |
3 |
Correct |
18 ms |
12152 KB |
Output is correct |
4 |
Correct |
19 ms |
12152 KB |
Output is correct |
5 |
Correct |
20 ms |
12280 KB |
Output is correct |
6 |
Correct |
21 ms |
12152 KB |
Output is correct |
7 |
Correct |
21 ms |
12152 KB |
Output is correct |
8 |
Correct |
21 ms |
12280 KB |
Output is correct |
9 |
Correct |
19 ms |
12152 KB |
Output is correct |
10 |
Correct |
19 ms |
12196 KB |
Output is correct |
11 |
Correct |
19 ms |
12280 KB |
Output is correct |
12 |
Correct |
19 ms |
12280 KB |
Output is correct |
13 |
Correct |
19 ms |
12280 KB |
Output is correct |
14 |
Correct |
19 ms |
12280 KB |
Output is correct |
15 |
Correct |
19 ms |
12280 KB |
Output is correct |
16 |
Correct |
19 ms |
12156 KB |
Output is correct |
17 |
Correct |
24 ms |
12280 KB |
Output is correct |
18 |
Correct |
24 ms |
12280 KB |
Output is correct |
19 |
Correct |
22 ms |
12304 KB |
Output is correct |
20 |
Correct |
21 ms |
12280 KB |
Output is correct |
21 |
Correct |
21 ms |
12280 KB |
Output is correct |
22 |
Correct |
21 ms |
12252 KB |
Output is correct |
23 |
Correct |
25 ms |
12268 KB |
Output is correct |
24 |
Correct |
24 ms |
12280 KB |
Output is correct |
25 |
Correct |
23 ms |
12280 KB |
Output is correct |
26 |
Correct |
20 ms |
12280 KB |
Output is correct |
27 |
Correct |
20 ms |
12280 KB |
Output is correct |
28 |
Correct |
22 ms |
12328 KB |
Output is correct |
29 |
Correct |
22 ms |
12408 KB |
Output is correct |
30 |
Correct |
21 ms |
12236 KB |
Output is correct |
31 |
Correct |
20 ms |
12312 KB |
Output is correct |
32 |
Correct |
21 ms |
12280 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
12280 KB |
Output is correct |
2 |
Correct |
18 ms |
12152 KB |
Output is correct |
3 |
Correct |
18 ms |
12152 KB |
Output is correct |
4 |
Correct |
19 ms |
12152 KB |
Output is correct |
5 |
Correct |
20 ms |
12280 KB |
Output is correct |
6 |
Correct |
21 ms |
12152 KB |
Output is correct |
7 |
Correct |
21 ms |
12152 KB |
Output is correct |
8 |
Correct |
21 ms |
12280 KB |
Output is correct |
9 |
Correct |
19 ms |
12152 KB |
Output is correct |
10 |
Correct |
19 ms |
12196 KB |
Output is correct |
11 |
Correct |
19 ms |
12280 KB |
Output is correct |
12 |
Correct |
19 ms |
12280 KB |
Output is correct |
13 |
Correct |
19 ms |
12280 KB |
Output is correct |
14 |
Correct |
19 ms |
12280 KB |
Output is correct |
15 |
Correct |
19 ms |
12280 KB |
Output is correct |
16 |
Correct |
19 ms |
12156 KB |
Output is correct |
17 |
Correct |
24 ms |
12280 KB |
Output is correct |
18 |
Correct |
24 ms |
12280 KB |
Output is correct |
19 |
Correct |
22 ms |
12304 KB |
Output is correct |
20 |
Correct |
21 ms |
12280 KB |
Output is correct |
21 |
Correct |
21 ms |
12280 KB |
Output is correct |
22 |
Correct |
21 ms |
12252 KB |
Output is correct |
23 |
Correct |
25 ms |
12268 KB |
Output is correct |
24 |
Correct |
24 ms |
12280 KB |
Output is correct |
25 |
Correct |
23 ms |
12280 KB |
Output is correct |
26 |
Correct |
20 ms |
12280 KB |
Output is correct |
27 |
Correct |
20 ms |
12280 KB |
Output is correct |
28 |
Correct |
22 ms |
12328 KB |
Output is correct |
29 |
Correct |
22 ms |
12408 KB |
Output is correct |
30 |
Correct |
21 ms |
12236 KB |
Output is correct |
31 |
Correct |
20 ms |
12312 KB |
Output is correct |
32 |
Correct |
21 ms |
12280 KB |
Output is correct |
33 |
Correct |
1029 ms |
17956 KB |
Output is correct |
34 |
Correct |
274 ms |
17912 KB |
Output is correct |
35 |
Correct |
955 ms |
16840 KB |
Output is correct |
36 |
Correct |
1488 ms |
21264 KB |
Output is correct |
37 |
Correct |
43 ms |
14968 KB |
Output is correct |
38 |
Correct |
1624 ms |
21964 KB |
Output is correct |
39 |
Correct |
1623 ms |
22072 KB |
Output is correct |
40 |
Correct |
1666 ms |
21844 KB |
Output is correct |
41 |
Correct |
1567 ms |
21992 KB |
Output is correct |
42 |
Correct |
1474 ms |
21788 KB |
Output is correct |
43 |
Correct |
1574 ms |
21988 KB |
Output is correct |
44 |
Correct |
1443 ms |
21952 KB |
Output is correct |
45 |
Correct |
1456 ms |
22160 KB |
Output is correct |
46 |
Correct |
1524 ms |
22096 KB |
Output is correct |
47 |
Correct |
1596 ms |
22216 KB |
Output is correct |
48 |
Correct |
377 ms |
19220 KB |
Output is correct |
49 |
Correct |
416 ms |
20512 KB |
Output is correct |
50 |
Correct |
193 ms |
14456 KB |
Output is correct |
51 |
Correct |
179 ms |
15580 KB |
Output is correct |
52 |
Correct |
83 ms |
14072 KB |
Output is correct |
53 |
Correct |
600 ms |
20788 KB |
Output is correct |
54 |
Correct |
498 ms |
16332 KB |
Output is correct |
55 |
Correct |
1292 ms |
19336 KB |
Output is correct |
56 |
Correct |
862 ms |
16792 KB |
Output is correct |
57 |
Correct |
1046 ms |
20280 KB |
Output is correct |
58 |
Correct |
73 ms |
15604 KB |
Output is correct |
59 |
Correct |
191 ms |
15352 KB |
Output is correct |
60 |
Correct |
332 ms |
19320 KB |
Output is correct |
61 |
Correct |
367 ms |
19552 KB |
Output is correct |
62 |
Correct |
213 ms |
17664 KB |
Output is correct |
63 |
Correct |
120 ms |
19064 KB |
Output is correct |
64 |
Correct |
124 ms |
20728 KB |
Output is correct |
65 |
Correct |
141 ms |
25484 KB |
Output is correct |
66 |
Correct |
237 ms |
15608 KB |
Output is correct |
67 |
Correct |
186 ms |
21492 KB |
Output is correct |
68 |
Correct |
363 ms |
25340 KB |
Output is correct |
69 |
Correct |
135 ms |
13688 KB |
Output is correct |
70 |
Correct |
49 ms |
12536 KB |
Output is correct |
71 |
Correct |
191 ms |
18696 KB |
Output is correct |
72 |
Correct |
247 ms |
23928 KB |
Output is correct |
73 |
Correct |
516 ms |
28580 KB |
Output is correct |
74 |
Correct |
562 ms |
24860 KB |
Output is correct |
75 |
Correct |
422 ms |
29176 KB |
Output is correct |
76 |
Correct |
432 ms |
27512 KB |
Output is correct |
77 |
Correct |
557 ms |
25336 KB |
Output is correct |