/*input
3
1 2 1
2 3 1
3 1 2
*/
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
vector<ll>adj[101010];
ll pa[101010], sz[101010];
void dfs(ll i, ll p)
{
if (p != 0)
adj[i].erase(find(adj[i].begin(), adj[i].end(), p));
pa[i] = p;
sz[i] = 1;
pair<ll, ll>mx = { -1, -1};
for (ll t = 0; t < (ll)adj[i].size(); t++)
{
ll j = adj[i][t];
dfs(j, i);
sz[i] += sz[j];
mx = max(mx, {sz[j], t});
}
if (mx.second != -1)
swap(adj[i][0], adj[i][mx.second]);
}
ll timer = 1;
ll nr[101010], head[101010], tail[101010];
void hld(ll i, ll h)
{
nr[i] = timer++;
head[i] = h;
tail[h] = i;
for (ll t = 0; t < (ll)adj[i].size(); t++)
{
ll j = adj[i][t];
hld(j, t == 0 ? h : j);
}
}
struct line
{
ll cc = 0, cd = 0, dd = 0, dc = 0;
line() {}
line(string s) {cc = -1; cd = -1; dd = -1; dc = -1;}
};
line merge(line a, line b)
{
if (a.cc < 0)
return b;
if (b.cc < 0)
return a;
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;
ll l, r;
ST *left, *right;
ST(ll l, ll 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);
}
else
{
X.cc = 0;
X.cd = 101010;
X.dc = 101010;
X.dd = 0;
}
}
line get(ll x, ll y)
{
if (x <= l && r <= y)
return X;
if (r < x || y < l)
return line("blogai");
return merge(left->get(x, y), right->get(x, y));
}
void setC(ll x, ll w)
{
if (l == r)
{
X.cc = w;
}
else
{
if (x <= (l + r) / 2)
left->setC(x, w);
else
right->setC(x, w);
X = merge(left->X, right->X);
}
}
void setD(ll x, ll w)
{
if (l == r)
{
X.dd = w;
}
else
{
if (x <= (l + r) / 2)
left->setD(x, w);
else
right->setD(x, w);
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, 1);
}
ll C[101010], D[101010], V[101010];
void fix(ll v)
{
ll w = head[v];
line X = medis.get(nr[w], nr[tail[w]]);
C[pa[w]] -= min({X.cd, X.cc, X.dc + 1, X.dd + 1});
D[pa[w]] -= min({X.cd + 1, X.cc + 1, X.dc, X.dd});
if (V[v] == -1)
{
medis.setC(nr[v], C[v]);
medis.setD(nr[v], 101010);
} else if (V[v] == 1)
{
medis.setC(nr[v], 101010);
medis.setD(nr[v], D[v]);
} else
{
medis.setC(nr[v], C[v]);
medis.setD(nr[v], D[v]);
}
X = medis.get(nr[w], nr[tail[w]]);
C[pa[w]] += min({X.cd, X.cc, X.dc + 1, X.dd + 1});
D[pa[w]] += min({X.cd + 1, X.cc + 1, X.dc, X.dd});
if (v != w)
return fix(w);
else if (v != 1)
return fix(pa[v]);
}
int cat(int v)
{
V[v] = -1;
fix(v);
return min(C[0], D[0]);
}
int dog(int v)
{
V[v] = 1;
fix(v);
return min(C[0], D[0]);
}
int neighbor(int v)
{
V[v] = 0;
fix(v);
return min(C[0], D[0]);
}/*
int main()
{
initialize(3, {1, 1}, {2, 3});
cout << cat(1) << endl;
cout << C[0] << " " << D[0] << endl;
cout << dog(2) << endl;
cout << dog(3) << endl;
}*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
18680 KB |
Output is correct |
2 |
Correct |
24 ms |
18552 KB |
Output is correct |
3 |
Correct |
27 ms |
18552 KB |
Output is correct |
4 |
Correct |
28 ms |
18556 KB |
Output is correct |
5 |
Correct |
24 ms |
18552 KB |
Output is correct |
6 |
Correct |
27 ms |
18552 KB |
Output is correct |
7 |
Correct |
24 ms |
18552 KB |
Output is correct |
8 |
Correct |
25 ms |
18556 KB |
Output is correct |
9 |
Correct |
24 ms |
18680 KB |
Output is correct |
10 |
Correct |
24 ms |
18680 KB |
Output is correct |
11 |
Correct |
24 ms |
18552 KB |
Output is correct |
12 |
Correct |
28 ms |
18560 KB |
Output is correct |
13 |
Correct |
25 ms |
18580 KB |
Output is correct |
14 |
Correct |
24 ms |
18552 KB |
Output is correct |
15 |
Correct |
24 ms |
18596 KB |
Output is correct |
16 |
Correct |
24 ms |
18484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
18680 KB |
Output is correct |
2 |
Correct |
24 ms |
18552 KB |
Output is correct |
3 |
Correct |
27 ms |
18552 KB |
Output is correct |
4 |
Correct |
28 ms |
18556 KB |
Output is correct |
5 |
Correct |
24 ms |
18552 KB |
Output is correct |
6 |
Correct |
27 ms |
18552 KB |
Output is correct |
7 |
Correct |
24 ms |
18552 KB |
Output is correct |
8 |
Correct |
25 ms |
18556 KB |
Output is correct |
9 |
Correct |
24 ms |
18680 KB |
Output is correct |
10 |
Correct |
24 ms |
18680 KB |
Output is correct |
11 |
Correct |
24 ms |
18552 KB |
Output is correct |
12 |
Correct |
28 ms |
18560 KB |
Output is correct |
13 |
Correct |
25 ms |
18580 KB |
Output is correct |
14 |
Correct |
24 ms |
18552 KB |
Output is correct |
15 |
Correct |
24 ms |
18596 KB |
Output is correct |
16 |
Correct |
24 ms |
18484 KB |
Output is correct |
17 |
Correct |
30 ms |
18720 KB |
Output is correct |
18 |
Correct |
30 ms |
18680 KB |
Output is correct |
19 |
Correct |
27 ms |
18680 KB |
Output is correct |
20 |
Correct |
24 ms |
18552 KB |
Output is correct |
21 |
Correct |
26 ms |
18552 KB |
Output is correct |
22 |
Correct |
27 ms |
18552 KB |
Output is correct |
23 |
Correct |
32 ms |
18680 KB |
Output is correct |
24 |
Correct |
31 ms |
18680 KB |
Output is correct |
25 |
Correct |
30 ms |
18680 KB |
Output is correct |
26 |
Correct |
26 ms |
18552 KB |
Output is correct |
27 |
Correct |
25 ms |
18552 KB |
Output is correct |
28 |
Correct |
28 ms |
18680 KB |
Output is correct |
29 |
Correct |
28 ms |
18680 KB |
Output is correct |
30 |
Correct |
27 ms |
18680 KB |
Output is correct |
31 |
Correct |
25 ms |
18680 KB |
Output is correct |
32 |
Correct |
27 ms |
18552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
18680 KB |
Output is correct |
2 |
Correct |
24 ms |
18552 KB |
Output is correct |
3 |
Correct |
27 ms |
18552 KB |
Output is correct |
4 |
Correct |
28 ms |
18556 KB |
Output is correct |
5 |
Correct |
24 ms |
18552 KB |
Output is correct |
6 |
Correct |
27 ms |
18552 KB |
Output is correct |
7 |
Correct |
24 ms |
18552 KB |
Output is correct |
8 |
Correct |
25 ms |
18556 KB |
Output is correct |
9 |
Correct |
24 ms |
18680 KB |
Output is correct |
10 |
Correct |
24 ms |
18680 KB |
Output is correct |
11 |
Correct |
24 ms |
18552 KB |
Output is correct |
12 |
Correct |
28 ms |
18560 KB |
Output is correct |
13 |
Correct |
25 ms |
18580 KB |
Output is correct |
14 |
Correct |
24 ms |
18552 KB |
Output is correct |
15 |
Correct |
24 ms |
18596 KB |
Output is correct |
16 |
Correct |
24 ms |
18484 KB |
Output is correct |
17 |
Correct |
30 ms |
18720 KB |
Output is correct |
18 |
Correct |
30 ms |
18680 KB |
Output is correct |
19 |
Correct |
27 ms |
18680 KB |
Output is correct |
20 |
Correct |
24 ms |
18552 KB |
Output is correct |
21 |
Correct |
26 ms |
18552 KB |
Output is correct |
22 |
Correct |
27 ms |
18552 KB |
Output is correct |
23 |
Correct |
32 ms |
18680 KB |
Output is correct |
24 |
Correct |
31 ms |
18680 KB |
Output is correct |
25 |
Correct |
30 ms |
18680 KB |
Output is correct |
26 |
Correct |
26 ms |
18552 KB |
Output is correct |
27 |
Correct |
25 ms |
18552 KB |
Output is correct |
28 |
Correct |
28 ms |
18680 KB |
Output is correct |
29 |
Correct |
28 ms |
18680 KB |
Output is correct |
30 |
Correct |
27 ms |
18680 KB |
Output is correct |
31 |
Correct |
25 ms |
18680 KB |
Output is correct |
32 |
Correct |
27 ms |
18552 KB |
Output is correct |
33 |
Correct |
1330 ms |
26236 KB |
Output is correct |
34 |
Correct |
358 ms |
26632 KB |
Output is correct |
35 |
Correct |
1239 ms |
24492 KB |
Output is correct |
36 |
Correct |
2025 ms |
31548 KB |
Output is correct |
37 |
Correct |
48 ms |
22392 KB |
Output is correct |
38 |
Correct |
2068 ms |
32784 KB |
Output is correct |
39 |
Correct |
2103 ms |
32788 KB |
Output is correct |
40 |
Correct |
2127 ms |
32856 KB |
Output is correct |
41 |
Correct |
2245 ms |
32792 KB |
Output is correct |
42 |
Correct |
2081 ms |
32796 KB |
Output is correct |
43 |
Correct |
1959 ms |
32780 KB |
Output is correct |
44 |
Correct |
1890 ms |
32812 KB |
Output is correct |
45 |
Correct |
1997 ms |
32812 KB |
Output is correct |
46 |
Correct |
1898 ms |
32792 KB |
Output is correct |
47 |
Correct |
1956 ms |
32800 KB |
Output is correct |
48 |
Correct |
427 ms |
27780 KB |
Output is correct |
49 |
Correct |
464 ms |
29972 KB |
Output is correct |
50 |
Correct |
212 ms |
21212 KB |
Output is correct |
51 |
Correct |
211 ms |
23200 KB |
Output is correct |
52 |
Correct |
92 ms |
20852 KB |
Output is correct |
53 |
Correct |
776 ms |
31216 KB |
Output is correct |
54 |
Correct |
639 ms |
24368 KB |
Output is correct |
55 |
Correct |
1692 ms |
28796 KB |
Output is correct |
56 |
Correct |
1059 ms |
25248 KB |
Output is correct |
57 |
Correct |
1299 ms |
30604 KB |
Output is correct |
58 |
Correct |
77 ms |
23120 KB |
Output is correct |
59 |
Correct |
194 ms |
22772 KB |
Output is correct |
60 |
Correct |
390 ms |
28788 KB |
Output is correct |
61 |
Correct |
429 ms |
29376 KB |
Output is correct |
62 |
Correct |
284 ms |
26768 KB |
Output is correct |
63 |
Correct |
141 ms |
26664 KB |
Output is correct |
64 |
Correct |
151 ms |
28768 KB |
Output is correct |
65 |
Correct |
157 ms |
34168 KB |
Output is correct |
66 |
Correct |
301 ms |
22648 KB |
Output is correct |
67 |
Correct |
223 ms |
29688 KB |
Output is correct |
68 |
Correct |
457 ms |
34516 KB |
Output is correct |
69 |
Correct |
168 ms |
20216 KB |
Output is correct |
70 |
Correct |
60 ms |
18808 KB |
Output is correct |
71 |
Correct |
247 ms |
26272 KB |
Output is correct |
72 |
Correct |
305 ms |
32504 KB |
Output is correct |
73 |
Correct |
643 ms |
38392 KB |
Output is correct |
74 |
Correct |
708 ms |
34052 KB |
Output is correct |
75 |
Correct |
560 ms |
38236 KB |
Output is correct |
76 |
Correct |
553 ms |
36728 KB |
Output is correct |
77 |
Correct |
707 ms |
34468 KB |
Output is correct |