#include <bits/stdc++.h>
using namespace std;
template <class X, class Y>
bool cmin(X &a, const Y &b) {
return a > b ? a = b, 1 : 0;
}
const int INF = 1e9;
struct segTree {
using Tp = array <array <int, 2>, 2>;
vector <Tp> tr; int n, lo, hi; Tp res;
Tp base() {
Tp c; c[0][1] = c[1][0] = INF;
c[0][0] = c[1][1] = 0; return c;
}
Tp comb(const Tp &a, const Tp &b) {
if (a[0][0] < 0) return b; Tp c;
c[0][1] = min({a[0][0] +
b[0][1], a[0][0] + b[1][1]
+ 1, a[0][1] + b[1][1],
a[0][1] + b[0][1] + 1, INF});
c[1][0] = min({a[1][0] +
b[0][0], a[1][0] + b[1][0]
+ 1, a[1][1] + b[1][0],
a[1][1] + b[0][0] + 1, INF});
c[0][0] = min({a[0][0] +
b[0][0], a[0][0] + b[1][0]
+ 1, a[0][1] + b[1][0],
a[0][1] + b[0][0] + 1, INF});
c[1][1] = min({a[1][0] +
b[0][1], a[1][0] + b[1][1]
+ 1, a[1][1] + b[1][1],
a[1][1] + b[0][1] + 1, INF});
return c;
}
void build(int i, int l, int r) {
if (l == r) tr[i] = base();
else {
int m = (l + r) / 2;
build(i * 2, l, m);
build(i * 2 + 1, m + 1, r);
tr[i] = comb(tr[i * 2], tr[i * 2 + 1]);
}
}
void init(int n) {
tr.resize((this->n = n) * 4);
build(1, 1, n);
}
void update(int i, int l, int r, int t, int v) {
if (l == r) return void(tr[i][t][t] = v);
int m = (l + r) / 2;
if (m >= lo) update(i * 2, l, m, t, v);
else update(i * 2 + 1, m + 1, r, t, v);
tr[i] = comb(tr[i * 2], tr[i * 2 + 1]);
}
void update(int p, int t, int v) {
lo = p; update(1, 1, n, t, v);
}
void query(int i, int l, int r) {
if (l >= lo && r <= hi) {
res = comb(res, tr[i]); return;
}
int m = (l + r) / 2;
if (m >= lo) query(i * 2, l, m);
if (m < hi) query(i * 2 + 1, m + 1, r);
}
Tp query(int l, int r) {
lo = l; hi = r; res[0][0] = -1;
query(1, 1, n); return res;
}
};
const int N = 100005;
vector <int> adj[N];
int f[N][2], g[N][2];
int hv[N], head[N], par[N], col[N];
int tin[N], tout[N], timer, en[N];
segTree ST;
int DFSpre(int u) {
int sz = 1, big = 0, tmp;
for (int v : adj[u]) {
if (v == par[u]) continue;
par[v] = u;
sz += tmp = DFSpre(v);
if (tmp > big) {
tmp = big; hv[u] = v;
}
}
return sz;
}
void DFSsplit(int u) {
tin[u] = ++timer;
if (par[u] && u == hv[par[u]])
head[u] = head[par[u]];
else head[u] = u;
if (hv[u]) {
DFSsplit(hv[u]); en[u] = en[hv[u]];
}
else en[u] = u;
for (int v : adj[u])
if (v != par[u] && v != hv[u])
DFSsplit(v);
tout[u] = timer;
}
void update(int u, int t) {
if (t < 2) ST.update(tin[u], 1 - t, INF);
else ST.update(tin[u], 1 - col[u], g[u][1 - col[u]]);
col[u] = t;
while (u) {
u = head[u];
if (par[u]) {
g[par[u]][0] -= min(f[u][0], f[u][1] + 1);
g[par[u]][1] -= min(f[u][0] + 1, f[u][1]);
}
auto res = ST.query(tin[u], tin[en[u]]);
if (col[u] == 0 || col[u] == 2)
f[u][0] = min(res[0][0], res[0][1]);
else f[u][0] = INF;
if (col[u] == 1 || col[u] == 2)
f[u][1] = min(res[1][0], res[1][1]);
else f[u][1] = INF;
if (par[u]) {
g[par[u]][0] += min(f[u][0], f[u][1] + 1);
if (col[par[u]] == 0 || col[par[u]] == 2)
ST.update(tin[par[u]], 0, g[par[u]][0]);
g[par[u]][1] += min(f[u][0] + 1, f[u][1]);
if (col[par[u]] == 1 || col[par[u]] == 2)
ST.update(tin[par[u]], 1, g[par[u]][1]);
}
u = par[u];
}
}
void initialize(int n, vector <int> a, vector <int> b) {
fill(col + 1, col + n + 1, 2);
for (int i = 0; i < n - 1; i++) {
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
DFSpre(1); DFSsplit(1); ST.init(n);
}
int cat(int u) {
update(u, 0); return min(f[1][0], f[1][1]);
}
int dog(int u) {
update(u, 1); return min(f[1][0], f[1][1]);
}
int neighbor(int u) {
update(u, 2); return min(f[1][0], f[1][1]);
}
Compilation message
catdog.cpp: In member function 'segTree::Tp segTree::comb(const Tp&, const Tp&)':
catdog.cpp:23:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
23 | if (a[0][0] < 0) return b; Tp c;
| ^~
catdog.cpp:23:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
23 | if (a[0][0] < 0) return b; Tp c;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2668 KB |
Output is correct |
2 |
Correct |
2 ms |
2668 KB |
Output is correct |
3 |
Correct |
2 ms |
2668 KB |
Output is correct |
4 |
Correct |
2 ms |
2668 KB |
Output is correct |
5 |
Correct |
2 ms |
2668 KB |
Output is correct |
6 |
Correct |
2 ms |
2668 KB |
Output is correct |
7 |
Correct |
2 ms |
2668 KB |
Output is correct |
8 |
Correct |
2 ms |
2668 KB |
Output is correct |
9 |
Correct |
2 ms |
2668 KB |
Output is correct |
10 |
Correct |
2 ms |
2668 KB |
Output is correct |
11 |
Correct |
2 ms |
2668 KB |
Output is correct |
12 |
Correct |
2 ms |
2668 KB |
Output is correct |
13 |
Correct |
2 ms |
2668 KB |
Output is correct |
14 |
Correct |
2 ms |
2668 KB |
Output is correct |
15 |
Correct |
2 ms |
2668 KB |
Output is correct |
16 |
Correct |
3 ms |
2668 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2668 KB |
Output is correct |
2 |
Correct |
2 ms |
2668 KB |
Output is correct |
3 |
Correct |
2 ms |
2668 KB |
Output is correct |
4 |
Correct |
2 ms |
2668 KB |
Output is correct |
5 |
Correct |
2 ms |
2668 KB |
Output is correct |
6 |
Correct |
2 ms |
2668 KB |
Output is correct |
7 |
Correct |
2 ms |
2668 KB |
Output is correct |
8 |
Correct |
2 ms |
2668 KB |
Output is correct |
9 |
Correct |
2 ms |
2668 KB |
Output is correct |
10 |
Correct |
2 ms |
2668 KB |
Output is correct |
11 |
Correct |
2 ms |
2668 KB |
Output is correct |
12 |
Correct |
2 ms |
2668 KB |
Output is correct |
13 |
Correct |
2 ms |
2668 KB |
Output is correct |
14 |
Correct |
2 ms |
2668 KB |
Output is correct |
15 |
Correct |
2 ms |
2668 KB |
Output is correct |
16 |
Correct |
3 ms |
2668 KB |
Output is correct |
17 |
Correct |
10 ms |
2796 KB |
Output is correct |
18 |
Correct |
10 ms |
2796 KB |
Output is correct |
19 |
Correct |
8 ms |
2796 KB |
Output is correct |
20 |
Correct |
2 ms |
2796 KB |
Output is correct |
21 |
Correct |
4 ms |
2796 KB |
Output is correct |
22 |
Correct |
5 ms |
2796 KB |
Output is correct |
23 |
Correct |
12 ms |
2796 KB |
Output is correct |
24 |
Correct |
14 ms |
2796 KB |
Output is correct |
25 |
Correct |
7 ms |
2796 KB |
Output is correct |
26 |
Correct |
5 ms |
2796 KB |
Output is correct |
27 |
Correct |
3 ms |
2796 KB |
Output is correct |
28 |
Correct |
3 ms |
2924 KB |
Output is correct |
29 |
Correct |
5 ms |
2924 KB |
Output is correct |
30 |
Correct |
3 ms |
2796 KB |
Output is correct |
31 |
Correct |
3 ms |
2796 KB |
Output is correct |
32 |
Correct |
3 ms |
2796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2668 KB |
Output is correct |
2 |
Correct |
2 ms |
2668 KB |
Output is correct |
3 |
Correct |
2 ms |
2668 KB |
Output is correct |
4 |
Correct |
2 ms |
2668 KB |
Output is correct |
5 |
Correct |
2 ms |
2668 KB |
Output is correct |
6 |
Correct |
2 ms |
2668 KB |
Output is correct |
7 |
Correct |
2 ms |
2668 KB |
Output is correct |
8 |
Correct |
2 ms |
2668 KB |
Output is correct |
9 |
Correct |
2 ms |
2668 KB |
Output is correct |
10 |
Correct |
2 ms |
2668 KB |
Output is correct |
11 |
Correct |
2 ms |
2668 KB |
Output is correct |
12 |
Correct |
2 ms |
2668 KB |
Output is correct |
13 |
Correct |
2 ms |
2668 KB |
Output is correct |
14 |
Correct |
2 ms |
2668 KB |
Output is correct |
15 |
Correct |
2 ms |
2668 KB |
Output is correct |
16 |
Correct |
3 ms |
2668 KB |
Output is correct |
17 |
Correct |
10 ms |
2796 KB |
Output is correct |
18 |
Correct |
10 ms |
2796 KB |
Output is correct |
19 |
Correct |
8 ms |
2796 KB |
Output is correct |
20 |
Correct |
2 ms |
2796 KB |
Output is correct |
21 |
Correct |
4 ms |
2796 KB |
Output is correct |
22 |
Correct |
5 ms |
2796 KB |
Output is correct |
23 |
Correct |
12 ms |
2796 KB |
Output is correct |
24 |
Correct |
14 ms |
2796 KB |
Output is correct |
25 |
Correct |
7 ms |
2796 KB |
Output is correct |
26 |
Correct |
5 ms |
2796 KB |
Output is correct |
27 |
Correct |
3 ms |
2796 KB |
Output is correct |
28 |
Correct |
3 ms |
2924 KB |
Output is correct |
29 |
Correct |
5 ms |
2924 KB |
Output is correct |
30 |
Correct |
3 ms |
2796 KB |
Output is correct |
31 |
Correct |
3 ms |
2796 KB |
Output is correct |
32 |
Correct |
3 ms |
2796 KB |
Output is correct |
33 |
Execution timed out |
3071 ms |
11996 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |