#include"catdog.h"
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb emplace_back
#define LC(i) (i << 1)
#define RC(i) ((i << 1) | 1)
#define IOS ios::sync_with_stdio(false); cin.tie(nullptr)
using ll = long long;
using vi = vector <int>;
const ll INF = 100000000000007;
const int V = 200005;
/* Helper */
void chmin(ll& a, ll b) {
if (b < a) a = b;
}
/* Graph */
int n;
vi g[V];
/* Segment Tree */
struct SegTree {
struct Node {
ll c[2][2]; // cat/dog cat/dog
void init() {
c[0][0] = c[1][1] = 0;
c[0][1] = c[1][0] = INF;
}
void update(int x, int y) {
c[0][0] += x;
c[1][1] += y;
}
};
int n;
vector <Node> node;
void init(int n) {
this->n = n;
node.resize(n << 3);
build(1, 0, n - 1);
}
void pull(int i) {
for (int a = 0; a < 2; ++a)
for (int b = 0; b < 2; ++b)
node[i].c[a][b] = INF;
for (int a = 0; a < 2; ++a)
for (int b = 0; b < 2; ++b)
for (int c = 0; c < 2; ++c)
for (int d = 0; d < 2; ++d)
chmin(node[i].c[a][b], node[LC(i)].c[a][c] + (c ^ d) + node[RC(i)].c[d][b]);
}
void build(int i, int l, int r) {
if (l == r) {
node[i].init();
return;
}
int m = (l + r) >> 1;
build(LC(i), l, m);
build(RC(i), m + 1, r);
pull(i);
}
int ui, x, y;
void update(int i, int l, int r) {
if (ui < l || r < ui) return;
if (l == r) {
node[i].update(x, y);
return;
}
int m = (l + r) >> 1;
update(LC(i), l, m);
update(RC(i), m + 1, r);
pull(i);
}
void update(int i, int x, int y, ll &a, ll &b) {
ui = i;
this->x = x;
this->y = y;
update(1, 0, n - 1);
query(a, b);
}
void query(ll &x, ll &y) {
ll c = min(node[1].c[0][0], node[1].c[0][1]);
ll d = min(node[1].c[1][0], node[1].c[1][1]);
x = min(c, d + 1);
y = min(c + 1, d);
}
};
vector <SegTree> tree;
/* HLD */
int dep[V], sz[V], hs[V], p[V];
int pdfs(int x, int px) {
sz[x] = 1;
p[x] = px;
int h = 0;
for (int y : g[x])
if (y != px) {
dep[y] = dep[x] + 1;
sz[x] += pdfs(y, x);
if (sz[y] > h)
h = sz[y], hs[x] = y;
}
return sz[x];
}
int g_tp[V], g_sz[V];
int g_cnt, v_num[V];
int pos[V];
void hdfs(int x, int px, int num) {
pos[x] = g_sz[num]++;
v_num[x] = num;
if (hs[x] != -1)
hdfs(hs[x], x, num);
for (int y : g[x])
if (y != px && y != hs[x])
hdfs(y, x, ++g_cnt), g_tp[g_cnt] = y;
}
void initialize(int N, vi A, vi B) {
n = N;
for (int i = 0; i < n; ++i)
g[i].clear();
for (int i = n - 2; i >= 0; --i)
g[--A[i]].pb(--B[i]), g[B[i]].pb(A[i]);
for (int i = 0; i < n; ++i)
hs[i] = -1;
pdfs(0, -1);
g_cnt = 0;
for (int i = 0; i < n; ++i) g_sz[i] = 0;
hdfs(0, 0, 0);
++g_cnt;
tree.resize(g_cnt);
for (int i = 0; i < g_cnt; ++i)
tree[i].init(g_sz[i]);
}
int update(int i, int x, int y) {
while (i != -1) {
int id;
ll old_x, old_y, new_x, new_y;
id = v_num[i];
tree[id].query(old_x, old_y);
tree[id].update(pos[i], x, y, new_x, new_y);
x = new_x - old_x;
y = new_y - old_y;
i = p[g_tp[id]];
}
ll a, b;
tree[0].query(a, b);
return min(a, b);
}
int st[V];
int cat(int v) {
--v;
st[v] = 1;
return update(v, 0, V);
}
int dog(int v) {
--v;
st[v] = 2;
return update(v, V, 0);
}
int neighbor(int v) {
--v;
int ans;
if (st[v] == 1)
ans = update(v, 0, -V);
else
ans = update(v, -V, 0);
st[v] = 0;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
