#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n, par[100001];
int heavy[100001] = {0}, sz[100001] = {0}, depth[100001] = {0}, head[100001];
vector<int> adj[100001];
struct Node {
int l, r;
int cats = 0, dogs = 0;
int mndiff = 0, mxdiff = 0;
int lazyC = 0, lazyD = 0;
int type = 0;
int idx = 0;
Node *lc, *rc;
Node(int l, int r) : l(l), r(r) {
if (l < r) {
int m = (l + r) >> 1;
lc = new Node{l, m};
rc = new Node{m + 1, r};
}
}
void clean() {
if (lazyC or lazyD) {
mndiff += lazyC - lazyD;
mxdiff += lazyC - lazyD;
if (l < r) {
lc->lazyC += lazyC;
rc->lazyC += lazyC;
lc->lazyD += lazyD;
rc->lazyD += lazyD;
} else {
cats += lazyC, dogs += lazyD;
}
lazyC = lazyD = 0;
}
}
void label(int i, int j) {
if (l == r) {
idx = j;
return;
}
int m = (l + r) >> 1;
if (i <= m) lc->label(i, j);
else rc->label(i, j);
}
pair<int, int> query(int i) {
clean();
if (l == r) {
if (type == 1 or not type and cats < dogs) {
return {cats, cats + 1};
} else if (type == 2 or not type and cats > dogs) {
return {dogs + 1, dogs};
} else {
return {cats, dogs};
}
}
int m = (l + r) >> 1;
if (i <= m) return lc->query(i);
else return rc->query(i);
}
void inc(int ul, int ur, int c, int d) {
clean();
if (ul > r or ur < l) return;
if (l >= ul and r <= ur) {
lazyC += c;
lazyD += d;
clean();
return;
}
lc->inc(ul, ur, c, d);
rc->inc(ul, ur, c, d);
mndiff = min(lc->mndiff, rc->mndiff);
mxdiff = max(lc->mxdiff, rc->mxdiff);
}
void update(int i, int t) {
if (i < l or i > r) return;
if (l == r) {
type = t;
return;
}
lc->update(i, t);
rc->update(i, t);
type = max(lc->type, rc->type);
}
pair<int, int> le(int i, int x) {
clean();
if (i < l) return {0, 0};
if (mndiff > x) return {0, 0};
if (l == r) return {idx, mndiff};
auto q = rc->le(i, x);
return q.first ? q : lc->le(i, x);
}
pair<int, int> ge(int i, int x) {
clean();
if (i < l) return {0, 0};
if (mxdiff < x) return {0, 0};
if (l == r) return {idx, mxdiff};
auto q = rc->ge(i, x);
return q.first ? q : lc->ge(i, x);
}
pair<int, int> occupied(int i) {
if (i < l or not type) return {0, 0};
if (l == r) return {idx, type};
auto q = rc->occupied(i);
return q.first ? q : lc->occupied(i);
}
} *st[100001] = {nullptr};
void build(int i) {
for (int j: adj[i]) {
if (j != par[i]) {
par[j] = i;
depth[j] = depth[i] + 1;
build(j);
sz[i] += sz[j];
if (sz[j] > sz[heavy[i]]) {
heavy[i] = j;
}
}
}
if (sz[heavy[i]] <= sz[i]++ / 2) heavy[i] = 0;
}
void hld(int i, int h) {
if (heavy[i]) {
hld(heavy[i], h);
st[i] = st[heavy[i]];
} else {
st[i] = new Node{depth[h], depth[i]};
}
head[i] = par[h];
for (int j: adj[i]) {
if (j != par[i] and j != heavy[i]) {
hld(j, j);
}
}
}
void inc(int i, int c, int d = INF) {
if (not i) return;
if (c == d or d == INF) {
st[i]->inc(0, depth[i], c, c);
inc(head[i], c, c);
return;
}
int diff1 = c - d;
if (diff1 == -2) {
auto [i0, v0] = st[i]->le(depth[i], 0);
auto [i1, v1] = st[i]->ge(depth[i], 2);
auto [io, t] = st[i]->occupied(depth[i]);
if (io and depth[io] >= max(depth[i0], depth[i1])) {
st[i]->inc(depth[io], depth[i], c, d);
inc(par[io], t == 1 ? c : d);
} else if (depth[i0] > depth[i1]) {
st[i]->inc(depth[i0], depth[i], c, d);
inc(par[i0], c, v0 == 0 ? c + 1 : c);
} else if (depth[i1] > depth[i0]) {
st[i]->inc(depth[i1], depth[i], c, d);
inc(par[i1], v1 == 2 ? d - 1 : d, d);
} else {
st[i]->inc(0, depth[i], c, d);
inc(head[i], c, d);
}
} else if (diff1 == -1) {
int i0 = st[i]->le(depth[i], -1).first;
int i1 = st[i]->ge(depth[i], 2).first;
auto [io, t] = st[i]->occupied(depth[i]);
if (io and depth[io] >= max(depth[i0], depth[i1])) {
st[i]->inc(depth[io], depth[i], c, d);
inc(par[io], t == 1 ? c : d);
} else if (depth[i0] > depth[i1]) {
st[i]->inc(depth[i0], depth[i], c, d);
inc(par[i0], c);
} else if (depth[i1] > depth[i0]) {
st[i]->inc(depth[i1], depth[i], c, d);
inc(par[i1], d);
} else {
st[i]->inc(0, depth[i], c, d);
inc(head[i], c, d);
}
} else if (diff1 == 1) {
int i0 = st[i]->le(depth[i], -2).first;
int i1 = st[i]->ge(depth[i], 1).first;
auto [io, t] = st[i]->occupied(depth[i]);
if (io and depth[io] >= max(depth[i0], depth[i1])) {
st[i]->inc(depth[io], depth[i], c, d);
inc(par[io], t == 1 ? c : d);
} else if (depth[i0] > depth[i1]) {
st[i]->inc(depth[i0], depth[i], c, d);
inc(par[i0], c);
} else if (depth[i1] > depth[i0]) {
st[i]->inc(depth[i1], depth[i], c, d);
inc(par[i1], d);
} else {
st[i]->inc(0, depth[i], c, d);
inc(head[i], c, d);
}
} else if (diff1 == 2) {
auto [i0, v0] = st[i]->le(depth[i], -2);
auto [i1, v1] = st[i]->ge(depth[i], 0);
auto [io, t] = st[i]->occupied(depth[i]);
if (io and depth[io] >= max(depth[i0], depth[i1])) {
st[i]->inc(depth[io], depth[i], c, d);
inc(par[io], t == 1 ? c : d);
} else if (depth[i0] > depth[i1]) {
st[i]->inc(depth[i0], depth[i], c, d);
inc(par[i0], c, v0 == -2 ? c - 1 : c);
} else if (depth[i1] > depth[i0]) {
st[i]->inc(depth[i1], depth[i], c, d);
inc(par[i1], v1 == 0 ? d + 1 : d, d);
} else {
st[i]->inc(0, depth[i], c, d);
inc(head[i], c, d);
}
}
}
int update(int i, int t) {
auto [c0, d0] = st[i]->query(depth[i]);
st[i]->update(depth[i], t);
if (par[i]) {
auto [c1, d1] = st[i]->query(depth[i]);
int dc = c1 - c0, dd = d1 - d0;
inc(par[i], dc, dd);
}
auto [c, d] = st[1]->query(depth[1]);
return min(c, d);
}
void initialize(int N, vector<int> A, vector<int> B) {
n = N;
for (int i = 0; i < n - 1; ++i) {
adj[A[i]].emplace_back(B[i]);
adj[B[i]].emplace_back(A[i]);
}
par[1] = 0;
build(1);
hld(1, 1);
for (int i = 1; i <= n; ++i) {
st[i]->label(depth[i], i);
}
depth[0] = -INF;
}
int cat(int v) {
return update(v, 1);
}
int dog(int v) {
return update(v, 2);
}
int neighbor(int v) {
return update(v, 0);
}
Compilation message
catdog.cpp: In member function 'std::pair<int, int> Node::query(int)':
catdog.cpp:56:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
56 | if (type == 1 or not type and cats < dogs) {
| ~~~~~~~~~^~~~~~~~~~~~~~~
catdog.cpp:58:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
58 | } else if (type == 2 or not type and cats > dogs) {
| ~~~~~~~~~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4556 KB |
Output is correct |
2 |
Correct |
3 ms |
4444 KB |
Output is correct |
3 |
Correct |
2 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4532 KB |
Output is correct |
5 |
Correct |
1 ms |
4552 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
2 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4696 KB |
Output is correct |
9 |
Correct |
2 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4448 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
2 ms |
4696 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
2 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4556 KB |
Output is correct |
2 |
Correct |
3 ms |
4444 KB |
Output is correct |
3 |
Correct |
2 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4532 KB |
Output is correct |
5 |
Correct |
1 ms |
4552 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
2 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4696 KB |
Output is correct |
9 |
Correct |
2 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4448 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
2 ms |
4696 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
2 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
2 ms |
4700 KB |
Output is correct |
18 |
Correct |
2 ms |
4704 KB |
Output is correct |
19 |
Correct |
2 ms |
4444 KB |
Output is correct |
20 |
Correct |
1 ms |
4552 KB |
Output is correct |
21 |
Correct |
1 ms |
4444 KB |
Output is correct |
22 |
Correct |
3 ms |
4556 KB |
Output is correct |
23 |
Correct |
2 ms |
4704 KB |
Output is correct |
24 |
Correct |
3 ms |
4564 KB |
Output is correct |
25 |
Correct |
2 ms |
4440 KB |
Output is correct |
26 |
Correct |
1 ms |
4448 KB |
Output is correct |
27 |
Correct |
1 ms |
4444 KB |
Output is correct |
28 |
Correct |
2 ms |
4700 KB |
Output is correct |
29 |
Correct |
2 ms |
4696 KB |
Output is correct |
30 |
Correct |
2 ms |
4444 KB |
Output is correct |
31 |
Correct |
1 ms |
4556 KB |
Output is correct |
32 |
Correct |
1 ms |
4444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4556 KB |
Output is correct |
2 |
Correct |
3 ms |
4444 KB |
Output is correct |
3 |
Correct |
2 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4532 KB |
Output is correct |
5 |
Correct |
1 ms |
4552 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
2 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4696 KB |
Output is correct |
9 |
Correct |
2 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4448 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
2 ms |
4696 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
2 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
2 ms |
4700 KB |
Output is correct |
18 |
Correct |
2 ms |
4704 KB |
Output is correct |
19 |
Correct |
2 ms |
4444 KB |
Output is correct |
20 |
Correct |
1 ms |
4552 KB |
Output is correct |
21 |
Correct |
1 ms |
4444 KB |
Output is correct |
22 |
Correct |
3 ms |
4556 KB |
Output is correct |
23 |
Correct |
2 ms |
4704 KB |
Output is correct |
24 |
Correct |
3 ms |
4564 KB |
Output is correct |
25 |
Correct |
2 ms |
4440 KB |
Output is correct |
26 |
Correct |
1 ms |
4448 KB |
Output is correct |
27 |
Correct |
1 ms |
4444 KB |
Output is correct |
28 |
Correct |
2 ms |
4700 KB |
Output is correct |
29 |
Correct |
2 ms |
4696 KB |
Output is correct |
30 |
Correct |
2 ms |
4444 KB |
Output is correct |
31 |
Correct |
1 ms |
4556 KB |
Output is correct |
32 |
Correct |
1 ms |
4444 KB |
Output is correct |
33 |
Correct |
91 ms |
14160 KB |
Output is correct |
34 |
Correct |
47 ms |
15292 KB |
Output is correct |
35 |
Correct |
94 ms |
11772 KB |
Output is correct |
36 |
Correct |
147 ms |
20884 KB |
Output is correct |
37 |
Correct |
15 ms |
9424 KB |
Output is correct |
38 |
Correct |
150 ms |
22568 KB |
Output is correct |
39 |
Correct |
163 ms |
22604 KB |
Output is correct |
40 |
Correct |
175 ms |
22668 KB |
Output is correct |
41 |
Correct |
170 ms |
22600 KB |
Output is correct |
42 |
Correct |
175 ms |
22704 KB |
Output is correct |
43 |
Correct |
159 ms |
22712 KB |
Output is correct |
44 |
Correct |
158 ms |
22604 KB |
Output is correct |
45 |
Correct |
157 ms |
22736 KB |
Output is correct |
46 |
Correct |
175 ms |
22684 KB |
Output is correct |
47 |
Correct |
150 ms |
22708 KB |
Output is correct |
48 |
Correct |
44 ms |
15252 KB |
Output is correct |
49 |
Correct |
51 ms |
17744 KB |
Output is correct |
50 |
Correct |
15 ms |
7612 KB |
Output is correct |
51 |
Correct |
27 ms |
9688 KB |
Output is correct |
52 |
Correct |
13 ms |
7264 KB |
Output is correct |
53 |
Correct |
84 ms |
21336 KB |
Output is correct |
54 |
Correct |
63 ms |
11860 KB |
Output is correct |
55 |
Correct |
130 ms |
17484 KB |
Output is correct |
56 |
Correct |
80 ms |
13044 KB |
Output is correct |
57 |
Correct |
122 ms |
20336 KB |
Output is correct |
58 |
Correct |
15 ms |
10200 KB |
Output is correct |
59 |
Correct |
21 ms |
9496 KB |
Output is correct |
60 |
Correct |
48 ms |
16588 KB |
Output is correct |
61 |
Correct |
47 ms |
17096 KB |
Output is correct |
62 |
Correct |
34 ms |
14524 KB |
Output is correct |
63 |
Correct |
43 ms |
18260 KB |
Output is correct |
64 |
Correct |
57 ms |
20828 KB |
Output is correct |
65 |
Correct |
71 ms |
30540 KB |
Output is correct |
66 |
Correct |
54 ms |
10840 KB |
Output is correct |
67 |
Correct |
65 ms |
22736 KB |
Output is correct |
68 |
Correct |
123 ms |
30780 KB |
Output is correct |
69 |
Correct |
31 ms |
6748 KB |
Output is correct |
70 |
Correct |
8 ms |
4700 KB |
Output is correct |
71 |
Correct |
68 ms |
16396 KB |
Output is correct |
72 |
Correct |
96 ms |
25940 KB |
Output is correct |
73 |
Correct |
140 ms |
34496 KB |
Output is correct |
74 |
Correct |
150 ms |
30324 KB |
Output is correct |
75 |
Correct |
158 ms |
34772 KB |
Output is correct |
76 |
Correct |
145 ms |
33056 KB |
Output is correct |
77 |
Correct |
148 ms |
30800 KB |
Output is correct |