#include <bits/stdc++.h>
#include "catdog.h"
#define pb emplace_back
#define ll long long
#define fi first
#define se second
#define mp make_pair
//#define int int64_t
using namespace std;
const int N = (int)1e5 + 2;
const int inf = 2e5;
int n, u, v, q, sz[N], cur[N], par[N], t, tail[N];
int cnt, cntp, head[N], pos[N], id[N], big[N];
vector<int> adj[N];
int l[N << 2], h[N << 2];
struct TNode {
int g[2][2];
TNode() {g[0][0] = g[1][1] = 0, g[1][0] = g[0][1] = inf;}
TNode operator +(const TNode& r)const& {
TNode res;
res.g[0][0] = min({g[0][1] + r.g[1][0], g[0][1] + r.g[0][0] + 1, g[0][0] + r.g[0][0], g[0][0] + r.g[1][0] + 1, inf});
res.g[0][1] = min({g[0][1] + r.g[1][1], g[0][1] + r.g[0][1] + 1, g[0][0] + r.g[0][1], g[0][0] + r.g[1][1] + 1, inf});
res.g[1][0] = min({g[1][1] + r.g[1][0], g[1][1] + r.g[0][0] + 1, g[1][0] + r.g[0][0], g[1][0] + r.g[1][0] + 1, inf});
res.g[1][1] = min({g[1][1] + r.g[1][1], g[1][1] + r.g[0][1] + 1, g[1][0] + r.g[0][1], g[1][0] + r.g[1][1] + 1, inf});
return res;
}
} st[N << 2], val;
void build(int x, int low, int high) {
l[x] = low, h[x] = high;
if(low == high) return;
int mid = (low + high) >> 1;
build(x << 1, low, mid);
build(x << 1 | 1, mid + 1, high);
}
void upd(int x, int pos, int add0, int add1) {
if(l[x] > pos || h[x] < pos) return;
if(l[x] == pos && h[x] == pos) {
st[x].g[0][0] += add0;
st[x].g[1][1] += add1;
return;
}
upd(x << 1, pos, add0, add1);
upd(x << 1 | 1, pos, add0, add1);
st[x] = st[x << 1] + st[x << 1 | 1];
}
TNode get(int x, int low, int high) {
if(low > high) return TNode();
if(low > h[x] || l[x] > high) return TNode();
if(low <= l[x] && h[x] <= high) return st[x];
return get(x << 1, low, high) + get(x << 1 | 1, low, high);
}
void hld(int u) {
if(!head[cnt]) head[cnt] = u;
id[u] = cnt, pos[u] = ++cntp, tail[cnt] = u;
for(int v: adj[u])
if(!big[u] || sz[v] > sz[big[u]]) big[u] = v;
if(big[u]) hld(big[u]);
for(int v: adj[u])
if(big[u] != v) ++cnt, hld(v);
}
void initialize(int N, vector<int> A, vector<int> B) {
n = N;
for(int i = 0; i < A.size(); ++i) {
adj[A[i]].pb(B[i]), adj[B[i]].pb(A[i]);
}
function<void(int)> dfs = [&](int u) {
sz[u] = 1;
for(int& v: adj[u]) {
if(v == par[u]) swap(v, adj[u].back());
if(v == par[u]) continue;
par[v] = u;
dfs(v);
sz[u] += sz[v];
}
if(par[u]) adj[u].pop_back();
};
dfs(1), cnt = 1, hld(1);
build(1, 1, n);
fill(cur, cur + n + 1, -1);
}
int f0, f1, top, nf0, nf1;
pair<int, int> getf(int l, int r) {
val = get(1, pos[l], pos[r]);
return mp(min({val.g[0][0], val.g[0][1], val.g[1][0] + 1, val.g[1][1] + 1}),
min({val.g[1][0], val.g[1][1], val.g[0][0] + 1, val.g[0][1] + 1}));
}
void update(int v, int add0, int add1) {
while(1) {
top = head[id[v]];
tie(f0, f1) = getf(top, tail[id[v]]);
upd(1, pos[v], add0, add1);
tie(nf0, nf1) = getf(top, tail[id[v]]);
if(top == 1) return;
add0 = nf0 - f0, add1 = nf1 - f1, v = par[top];
}
}
int getans() {
tie(f0, f1) = getf(1, tail[1]);
return min(f0, f1);
}
int cat(int v) {
cur[v] = 0;
update(v, 0, inf);
return getans();
}
int dog(int v) {
cur[v] = 1;
update(v, inf, 0);
return getans();
}
int neighbor(int v) {
if(cur[v] == 1) update(v, -inf, 0);
else if(cur[v] == 0) update(v, 0, -inf);
cur[v] = -1;
return getans();
}
Compilation message
catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:72:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < A.size(); ++i) {
~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
8960 KB |
Output is correct |
2 |
Correct |
10 ms |
8960 KB |
Output is correct |
3 |
Correct |
10 ms |
8960 KB |
Output is correct |
4 |
Correct |
10 ms |
8960 KB |
Output is correct |
5 |
Correct |
11 ms |
8960 KB |
Output is correct |
6 |
Correct |
9 ms |
8960 KB |
Output is correct |
7 |
Correct |
9 ms |
8960 KB |
Output is correct |
8 |
Correct |
9 ms |
8960 KB |
Output is correct |
9 |
Correct |
10 ms |
8960 KB |
Output is correct |
10 |
Correct |
10 ms |
8960 KB |
Output is correct |
11 |
Correct |
11 ms |
8960 KB |
Output is correct |
12 |
Correct |
9 ms |
8960 KB |
Output is correct |
13 |
Correct |
9 ms |
8960 KB |
Output is correct |
14 |
Correct |
12 ms |
8960 KB |
Output is correct |
15 |
Correct |
10 ms |
8960 KB |
Output is correct |
16 |
Correct |
9 ms |
8960 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
8960 KB |
Output is correct |
2 |
Correct |
10 ms |
8960 KB |
Output is correct |
3 |
Correct |
10 ms |
8960 KB |
Output is correct |
4 |
Correct |
10 ms |
8960 KB |
Output is correct |
5 |
Correct |
11 ms |
8960 KB |
Output is correct |
6 |
Correct |
9 ms |
8960 KB |
Output is correct |
7 |
Correct |
9 ms |
8960 KB |
Output is correct |
8 |
Correct |
9 ms |
8960 KB |
Output is correct |
9 |
Correct |
10 ms |
8960 KB |
Output is correct |
10 |
Correct |
10 ms |
8960 KB |
Output is correct |
11 |
Correct |
11 ms |
8960 KB |
Output is correct |
12 |
Correct |
9 ms |
8960 KB |
Output is correct |
13 |
Correct |
9 ms |
8960 KB |
Output is correct |
14 |
Correct |
12 ms |
8960 KB |
Output is correct |
15 |
Correct |
10 ms |
8960 KB |
Output is correct |
16 |
Correct |
9 ms |
8960 KB |
Output is correct |
17 |
Correct |
14 ms |
9088 KB |
Output is correct |
18 |
Correct |
13 ms |
9088 KB |
Output is correct |
19 |
Correct |
13 ms |
9088 KB |
Output is correct |
20 |
Correct |
10 ms |
9076 KB |
Output is correct |
21 |
Correct |
11 ms |
9088 KB |
Output is correct |
22 |
Correct |
11 ms |
8960 KB |
Output is correct |
23 |
Correct |
13 ms |
9088 KB |
Output is correct |
24 |
Correct |
13 ms |
9088 KB |
Output is correct |
25 |
Correct |
12 ms |
8960 KB |
Output is correct |
26 |
Correct |
11 ms |
9088 KB |
Output is correct |
27 |
Correct |
10 ms |
8960 KB |
Output is correct |
28 |
Correct |
10 ms |
9088 KB |
Output is correct |
29 |
Correct |
12 ms |
9216 KB |
Output is correct |
30 |
Correct |
11 ms |
9088 KB |
Output is correct |
31 |
Correct |
10 ms |
9088 KB |
Output is correct |
32 |
Correct |
11 ms |
9088 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
8960 KB |
Output is correct |
2 |
Correct |
10 ms |
8960 KB |
Output is correct |
3 |
Correct |
10 ms |
8960 KB |
Output is correct |
4 |
Correct |
10 ms |
8960 KB |
Output is correct |
5 |
Correct |
11 ms |
8960 KB |
Output is correct |
6 |
Correct |
9 ms |
8960 KB |
Output is correct |
7 |
Correct |
9 ms |
8960 KB |
Output is correct |
8 |
Correct |
9 ms |
8960 KB |
Output is correct |
9 |
Correct |
10 ms |
8960 KB |
Output is correct |
10 |
Correct |
10 ms |
8960 KB |
Output is correct |
11 |
Correct |
11 ms |
8960 KB |
Output is correct |
12 |
Correct |
9 ms |
8960 KB |
Output is correct |
13 |
Correct |
9 ms |
8960 KB |
Output is correct |
14 |
Correct |
12 ms |
8960 KB |
Output is correct |
15 |
Correct |
10 ms |
8960 KB |
Output is correct |
16 |
Correct |
9 ms |
8960 KB |
Output is correct |
17 |
Correct |
14 ms |
9088 KB |
Output is correct |
18 |
Correct |
13 ms |
9088 KB |
Output is correct |
19 |
Correct |
13 ms |
9088 KB |
Output is correct |
20 |
Correct |
10 ms |
9076 KB |
Output is correct |
21 |
Correct |
11 ms |
9088 KB |
Output is correct |
22 |
Correct |
11 ms |
8960 KB |
Output is correct |
23 |
Correct |
13 ms |
9088 KB |
Output is correct |
24 |
Correct |
13 ms |
9088 KB |
Output is correct |
25 |
Correct |
12 ms |
8960 KB |
Output is correct |
26 |
Correct |
11 ms |
9088 KB |
Output is correct |
27 |
Correct |
10 ms |
8960 KB |
Output is correct |
28 |
Correct |
10 ms |
9088 KB |
Output is correct |
29 |
Correct |
12 ms |
9216 KB |
Output is correct |
30 |
Correct |
11 ms |
9088 KB |
Output is correct |
31 |
Correct |
10 ms |
9088 KB |
Output is correct |
32 |
Correct |
11 ms |
9088 KB |
Output is correct |
33 |
Correct |
775 ms |
15760 KB |
Output is correct |
34 |
Correct |
205 ms |
15872 KB |
Output is correct |
35 |
Correct |
734 ms |
14576 KB |
Output is correct |
36 |
Correct |
1161 ms |
20420 KB |
Output is correct |
37 |
Correct |
30 ms |
12032 KB |
Output is correct |
38 |
Correct |
1319 ms |
21324 KB |
Output is correct |
39 |
Correct |
1263 ms |
21352 KB |
Output is correct |
40 |
Correct |
1235 ms |
21348 KB |
Output is correct |
41 |
Correct |
1248 ms |
21308 KB |
Output is correct |
42 |
Correct |
1197 ms |
21352 KB |
Output is correct |
43 |
Correct |
1199 ms |
21352 KB |
Output is correct |
44 |
Correct |
1146 ms |
21352 KB |
Output is correct |
45 |
Correct |
1185 ms |
21348 KB |
Output is correct |
46 |
Correct |
1192 ms |
21348 KB |
Output is correct |
47 |
Correct |
1227 ms |
21352 KB |
Output is correct |
48 |
Correct |
325 ms |
18624 KB |
Output is correct |
49 |
Correct |
361 ms |
20464 KB |
Output is correct |
50 |
Correct |
142 ms |
11768 KB |
Output is correct |
51 |
Correct |
146 ms |
13712 KB |
Output is correct |
52 |
Correct |
64 ms |
11384 KB |
Output is correct |
53 |
Correct |
461 ms |
20088 KB |
Output is correct |
54 |
Correct |
396 ms |
14136 KB |
Output is correct |
55 |
Correct |
1008 ms |
18800 KB |
Output is correct |
56 |
Correct |
597 ms |
15008 KB |
Output is correct |
57 |
Correct |
811 ms |
19832 KB |
Output is correct |
58 |
Correct |
52 ms |
13812 KB |
Output is correct |
59 |
Correct |
142 ms |
12920 KB |
Output is correct |
60 |
Correct |
294 ms |
19448 KB |
Output is correct |
61 |
Correct |
321 ms |
19952 KB |
Output is correct |
62 |
Correct |
179 ms |
17904 KB |
Output is correct |
63 |
Correct |
86 ms |
17272 KB |
Output is correct |
64 |
Correct |
90 ms |
18936 KB |
Output is correct |
65 |
Correct |
104 ms |
24824 KB |
Output is correct |
66 |
Correct |
152 ms |
13304 KB |
Output is correct |
67 |
Correct |
130 ms |
20856 KB |
Output is correct |
68 |
Correct |
297 ms |
25208 KB |
Output is correct |
69 |
Correct |
71 ms |
10624 KB |
Output is correct |
70 |
Correct |
23 ms |
9216 KB |
Output is correct |
71 |
Correct |
115 ms |
16760 KB |
Output is correct |
72 |
Correct |
159 ms |
23292 KB |
Output is correct |
73 |
Correct |
458 ms |
28408 KB |
Output is correct |
74 |
Correct |
514 ms |
24952 KB |
Output is correct |
75 |
Correct |
297 ms |
28408 KB |
Output is correct |
76 |
Correct |
308 ms |
27128 KB |
Output is correct |
77 |
Correct |
511 ms |
25336 KB |
Output is correct |