#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int INF = 1e9;
int n;
int a[N];
int par[N], nchild[N];
int T, head[N], pos[N], L[N], R[N];
vector<int> G[N];
struct Node {
int f[2][2];
Node() {
f[0][0] = f[1][1] = f[0][1] = f[1][0] = INF;
}
Node operator + (Node x) {
Node ret;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
for (int k = 0; k < 2; ++k) {
for (int l = 0; l < 2; ++l) {
ret.f[i][l] = min(ret.f[i][l], f[i][j] + x.f[k][l] + (j ^ k));
}
}
}
}
return ret;
}
};
struct SegmentTree {
vector<Node> T;
#define mid ((l + r) >> 1)
void build(int i, int l, int r) {
if (l == r) {
T[i].f[0][0] = T[i].f[1][1] = 0; return;
}
build(i << 1, l, mid);
build(i << 1 | 1, mid + 1, r);
T[i] = T[i << 1] + T[i << 1 | 1];
}
void upd(int i, int l, int r, int p, int v0, int v1) {
if (l == r) {
T[i].f[0][0] = min(INF, T[i].f[0][0] + v0);
T[i].f[1][1] = min(INF, T[i].f[1][1] + v1);
return;
}
if (mid >= p) upd(i << 1, l, mid, p, v0, v1);
else upd(i << 1 | 1, mid + 1, r, p, v0, v1);
T[i] = T[i << 1] + T[i << 1 | 1];
}
#undef mid
} IT[N];
void dfs(int u) {
nchild[u] = 1;
for (auto v : G[u]) {
if (v == par[u]) continue;
par[v] = u, dfs(v), nchild[u] += nchild[v];
}
}
void dfsHld(int u) {
if (head[u] == -1) head[u] = u;
pos[u] = ++T;
int nx = -1;
for (auto v : G[u]) {
if (v == par[u]) continue;
if (nx == -1 || nchild[nx] < nchild[v]) nx = v;
}
if (nx != -1) { head[nx] = head[u], dfsHld(nx); }
for (auto v : G[u]) {
if (v == par[u] || v == nx) continue; dfsHld(v);
}
}
void initialize(int _n, vector<int> A, vector<int> B) {
n = _n;
for (int i = 0; i < (n - 1); ++i) {
--A[i], --B[i];
G[A[i]].push_back(B[i]), G[B[i]].push_back(A[i]);
}
memset(head, -1, sizeof head);
dfs(0), dfsHld(0);
for (int i = 0; i < n; ++i) L[i] = n, R[i] = 1;
for (int i = 0; i < n; ++i) {
L[head[i]] = min(L[head[i]], pos[i]);
R[head[i]] = max(R[head[i]], pos[i]);
}
for (int i = 0; i < n; ++i) {
if (head[i] != i) continue;
int tmp = R[i] - L[i] + 1;
IT[i].T.assign(tmp * 4 + 5, Node());
IT[i].build(1, L[i], R[i]);
}
}
void upd(int u, int v0, int v1) {
while (head[u] != head[0]) {
int i = head[u];
int x0 = min(IT[i].T[1].f[0][1], IT[i].T[1].f[0][0]);
int x1 = min(IT[i].T[1].f[1][1], IT[i].T[1].f[1][0]);
IT[i].upd(1, L[i], R[i], pos[u], v0, v1);
int y0 = min(IT[i].T[1].f[0][1], IT[i].T[1].f[0][0]);
int y1 = min(IT[i].T[1].f[1][1], IT[i].T[1].f[1][0]);
u = par[i], v0 = y0 - x0, v1 = y1 - x1;
}
IT[0].upd(1, L[0], R[0], pos[u], v0, v1);
}
int get() {
int ret = INF;
for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) {
ret = min(ret, IT[0].T[1].f[i][j]);
}
return ret;
}
int cat(int v) {
--v, a[v] = 1, upd(v, 0, INF); return get();
}
int dog(int v) {
--v, a[v] = 2, upd(v, INF, 0); return get();
}
int neighbor(int v) {
--v; if (a[v] == 1) upd(v, 0, -INF); else upd(v, -INF, 0); return get();
}
Compilation message
catdog.cpp: In function 'void dfsHld(int)':
catdog.cpp:84:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if (v == par[u] || v == nx) continue; dfsHld(v);
^~
catdog.cpp:84:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if (v == par[u] || v == nx) continue; dfsHld(v);
^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5368 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
5476 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5368 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
5476 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5368 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
5476 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
