/// Sursa #2 cu renumerotarea HLD a nodurilor
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#include "catdog.h"
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
const ll NMAX = 250002;
const int INF = 1e9;
const ll nrbits = 20;
const ll MOD = 998244353;
vector <int> v[NMAX];
int stamp;
int n;
int timp[NMAX];
int sz[NMAX];
int maxi[NMAX];
int cpt[NMAX];
int last[NMAX];
int pa[NMAX];
int dp[NMAX][2]; /// suma vecinilor daca node e 0(cat)/1(dog)
int notAllowed[NMAX][2];
int adv[NMAX];
struct Node {
int dp[2][2];
} aint[NMAX * 4];
void DFS(int node, int p) {
sz[node] = 1;
maxi[node] = -1;
for(auto x : v[node]) {
if(x == p) continue;
DFS(x, node);
sz[node] += sz[x];
if(maxi[node] == -1 || sz[maxi[node]] < sz[x])
maxi[node] = x;
}
}
void hld(int node, int p, int capat) {
timp[node] = ++stamp;
adv[node] = stamp;
pa[stamp] = timp[p];
cpt[stamp] = timp[capat];
last[timp[capat]] = stamp;
if(maxi[node] != -1) {
hld(maxi[node], node, capat);
}
for(auto x : v[node]) {
if(x == p || maxi[node] == x)
continue;
hld(x, node, x);
}
}
Node combine(Node a, Node b) {
Node sol;
for(int i = 0; i < 2; i++) {
for(int j = 0; j < 2; j++) {
sol.dp[i][j] = INF;
for(int t = 0; t < 2; t++) {
sol.dp[i][j] = min(sol.dp[i][j], a.dp[i][t] + min(b.dp[t][j], b.dp[(t ^ 1)][j] + 1));
}
}
}
return sol;
}
void update(int node, int st, int dr, int a) {
if(st == dr) {
aint[node].dp[0][0] = dp[a][0] + notAllowed[a][0] * INF;
aint[node].dp[1][1] = dp[a][1] + notAllowed[a][1] * INF;
aint[node].dp[0][1] = aint[node].dp[1][0] = INF;
return;
}
int mid = (st + dr) / 2;
if(a <= mid)
update(node * 2, st, mid, a);
else
update(node * 2 + 1, mid + 1, dr, a);
aint[node] = combine(aint[node * 2], aint[node * 2 + 1]); /// numar mai mic => preordine primul => capatul lantului
}
Node query(int node, int st, int dr, int a, int b) {
if(a <= st && dr <= b)
return aint[node];
int mid = (st + dr) / 2;
if(b <= mid) {
return query(node * 2, st, mid, a, b);
}
if(a > mid) {
return query(node * 2 + 1, mid + 1, dr, a, b);
}
return combine(query(node * 2, st, mid, a, b), query(node * 2 + 1, mid + 1, dr, a, b));
}
pii realValue(int node) {
Node x = query(1, 1, n, node, last[cpt[node]]);
return {min(x.dp[0][1], x.dp[0][0]), min(x.dp[1][0], x.dp[1][1])};
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n = N;
for(int i = 0; i < A.size(); i++) {
v[A[i]].push_back(B[i]);
v[B[i]].push_back(A[i]);
}
DFS(1, 0);
hld(1, 0, 1);
for(int i = 1; i <= n; i++) {
/// aici nu avem ce adauga
update(1, 1, n, i); /// = {0, 0}
}
}
void adauga(int node, int sgn) {
vector <pii> perechi;
while(pa[cpt[node]] != 0) {
int unde = pa[cpt[node]];
int cine = cpt[node];
perechi.push_back({unde, cine});
node = unde;
}
if(sgn == -1) reverse(perechi.begin(), perechi.end());
for(auto x : perechi) {
int unde = x.first;
int cine = x.second;
pii am = realValue(cine);
dp[unde][0] += sgn * min(am.first, am.second + 1);
dp[unde][1] += sgn * min(am.first + 1, am.second);
update(1, 1, n, unde);
}
}
int cat(int v) {
v = adv[v];
adauga(v, -1);
notAllowed[v][1] = 1;
update(1, 1, n, v);
adauga(v, 1);
pii sol = realValue(1);
return min(sol.first, sol.second);
}
int dog(int v) {
v = adv[v];
adauga(v, -1);
notAllowed[v][0] = 1;
update(1, 1, n, v);
adauga(v, 1);
pii sol = realValue(1);
return min(sol.first, sol.second);
}
int neighbor(int v) {
v = adv[v];
adauga(v, -1);
notAllowed[v][0] = notAllowed[v][1] = 0;
update(1, 1, n, v);
adauga(v, 1);
pii sol = realValue(1);
return min(sol.first, sol.second);
}
Compilation message
catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:113:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(int i = 0; i < A.size(); i++) {
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
15972 KB |
Output is correct |
2 |
Correct |
3 ms |
15960 KB |
Output is correct |
3 |
Correct |
3 ms |
15960 KB |
Output is correct |
4 |
Correct |
3 ms |
15960 KB |
Output is correct |
5 |
Correct |
3 ms |
16120 KB |
Output is correct |
6 |
Correct |
3 ms |
16216 KB |
Output is correct |
7 |
Correct |
3 ms |
15964 KB |
Output is correct |
8 |
Correct |
4 ms |
16120 KB |
Output is correct |
9 |
Correct |
3 ms |
15964 KB |
Output is correct |
10 |
Correct |
4 ms |
16156 KB |
Output is correct |
11 |
Correct |
3 ms |
16140 KB |
Output is correct |
12 |
Correct |
3 ms |
15960 KB |
Output is correct |
13 |
Correct |
3 ms |
15964 KB |
Output is correct |
14 |
Correct |
3 ms |
15964 KB |
Output is correct |
15 |
Correct |
3 ms |
15960 KB |
Output is correct |
16 |
Correct |
3 ms |
15964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
15972 KB |
Output is correct |
2 |
Correct |
3 ms |
15960 KB |
Output is correct |
3 |
Correct |
3 ms |
15960 KB |
Output is correct |
4 |
Correct |
3 ms |
15960 KB |
Output is correct |
5 |
Correct |
3 ms |
16120 KB |
Output is correct |
6 |
Correct |
3 ms |
16216 KB |
Output is correct |
7 |
Correct |
3 ms |
15964 KB |
Output is correct |
8 |
Correct |
4 ms |
16120 KB |
Output is correct |
9 |
Correct |
3 ms |
15964 KB |
Output is correct |
10 |
Correct |
4 ms |
16156 KB |
Output is correct |
11 |
Correct |
3 ms |
16140 KB |
Output is correct |
12 |
Correct |
3 ms |
15960 KB |
Output is correct |
13 |
Correct |
3 ms |
15964 KB |
Output is correct |
14 |
Correct |
3 ms |
15964 KB |
Output is correct |
15 |
Correct |
3 ms |
15960 KB |
Output is correct |
16 |
Correct |
3 ms |
15964 KB |
Output is correct |
17 |
Correct |
4 ms |
16220 KB |
Output is correct |
18 |
Correct |
5 ms |
16220 KB |
Output is correct |
19 |
Correct |
4 ms |
16220 KB |
Output is correct |
20 |
Correct |
3 ms |
15960 KB |
Output is correct |
21 |
Correct |
4 ms |
15960 KB |
Output is correct |
22 |
Correct |
4 ms |
15964 KB |
Output is correct |
23 |
Correct |
6 ms |
16216 KB |
Output is correct |
24 |
Correct |
5 ms |
16220 KB |
Output is correct |
25 |
Correct |
4 ms |
15964 KB |
Output is correct |
26 |
Correct |
4 ms |
15964 KB |
Output is correct |
27 |
Correct |
4 ms |
15960 KB |
Output is correct |
28 |
Correct |
4 ms |
16220 KB |
Output is correct |
29 |
Correct |
4 ms |
16220 KB |
Output is correct |
30 |
Correct |
3 ms |
15960 KB |
Output is correct |
31 |
Correct |
4 ms |
16220 KB |
Output is correct |
32 |
Correct |
4 ms |
15964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
15972 KB |
Output is correct |
2 |
Correct |
3 ms |
15960 KB |
Output is correct |
3 |
Correct |
3 ms |
15960 KB |
Output is correct |
4 |
Correct |
3 ms |
15960 KB |
Output is correct |
5 |
Correct |
3 ms |
16120 KB |
Output is correct |
6 |
Correct |
3 ms |
16216 KB |
Output is correct |
7 |
Correct |
3 ms |
15964 KB |
Output is correct |
8 |
Correct |
4 ms |
16120 KB |
Output is correct |
9 |
Correct |
3 ms |
15964 KB |
Output is correct |
10 |
Correct |
4 ms |
16156 KB |
Output is correct |
11 |
Correct |
3 ms |
16140 KB |
Output is correct |
12 |
Correct |
3 ms |
15960 KB |
Output is correct |
13 |
Correct |
3 ms |
15964 KB |
Output is correct |
14 |
Correct |
3 ms |
15964 KB |
Output is correct |
15 |
Correct |
3 ms |
15960 KB |
Output is correct |
16 |
Correct |
3 ms |
15964 KB |
Output is correct |
17 |
Correct |
4 ms |
16220 KB |
Output is correct |
18 |
Correct |
5 ms |
16220 KB |
Output is correct |
19 |
Correct |
4 ms |
16220 KB |
Output is correct |
20 |
Correct |
3 ms |
15960 KB |
Output is correct |
21 |
Correct |
4 ms |
15960 KB |
Output is correct |
22 |
Correct |
4 ms |
15964 KB |
Output is correct |
23 |
Correct |
6 ms |
16216 KB |
Output is correct |
24 |
Correct |
5 ms |
16220 KB |
Output is correct |
25 |
Correct |
4 ms |
15964 KB |
Output is correct |
26 |
Correct |
4 ms |
15964 KB |
Output is correct |
27 |
Correct |
4 ms |
15960 KB |
Output is correct |
28 |
Correct |
4 ms |
16220 KB |
Output is correct |
29 |
Correct |
4 ms |
16220 KB |
Output is correct |
30 |
Correct |
3 ms |
15960 KB |
Output is correct |
31 |
Correct |
4 ms |
16220 KB |
Output is correct |
32 |
Correct |
4 ms |
15964 KB |
Output is correct |
33 |
Correct |
263 ms |
22780 KB |
Output is correct |
34 |
Correct |
91 ms |
22352 KB |
Output is correct |
35 |
Correct |
243 ms |
21996 KB |
Output is correct |
36 |
Correct |
413 ms |
27368 KB |
Output is correct |
37 |
Correct |
20 ms |
20380 KB |
Output is correct |
38 |
Correct |
439 ms |
28384 KB |
Output is correct |
39 |
Correct |
427 ms |
28228 KB |
Output is correct |
40 |
Correct |
446 ms |
28224 KB |
Output is correct |
41 |
Correct |
436 ms |
28192 KB |
Output is correct |
42 |
Correct |
382 ms |
28128 KB |
Output is correct |
43 |
Correct |
430 ms |
28192 KB |
Output is correct |
44 |
Correct |
397 ms |
28140 KB |
Output is correct |
45 |
Correct |
402 ms |
28156 KB |
Output is correct |
46 |
Correct |
398 ms |
28224 KB |
Output is correct |
47 |
Correct |
409 ms |
28220 KB |
Output is correct |
48 |
Correct |
127 ms |
26016 KB |
Output is correct |
49 |
Correct |
149 ms |
27152 KB |
Output is correct |
50 |
Correct |
50 ms |
20132 KB |
Output is correct |
51 |
Correct |
58 ms |
21176 KB |
Output is correct |
52 |
Correct |
25 ms |
19804 KB |
Output is correct |
53 |
Correct |
188 ms |
26608 KB |
Output is correct |
54 |
Correct |
134 ms |
21344 KB |
Output is correct |
55 |
Correct |
361 ms |
26180 KB |
Output is correct |
56 |
Correct |
224 ms |
22276 KB |
Output is correct |
57 |
Correct |
314 ms |
26464 KB |
Output is correct |
58 |
Correct |
29 ms |
20948 KB |
Output is correct |
59 |
Correct |
50 ms |
21072 KB |
Output is correct |
60 |
Correct |
142 ms |
26452 KB |
Output is correct |
61 |
Correct |
130 ms |
26712 KB |
Output is correct |
62 |
Correct |
78 ms |
25228 KB |
Output is correct |
63 |
Correct |
46 ms |
24180 KB |
Output is correct |
64 |
Correct |
48 ms |
25680 KB |
Output is correct |
65 |
Correct |
72 ms |
31356 KB |
Output is correct |
66 |
Correct |
54 ms |
21468 KB |
Output is correct |
67 |
Correct |
63 ms |
28240 KB |
Output is correct |
68 |
Correct |
130 ms |
31568 KB |
Output is correct |
69 |
Correct |
24 ms |
19796 KB |
Output is correct |
70 |
Correct |
7 ms |
16220 KB |
Output is correct |
71 |
Correct |
49 ms |
23968 KB |
Output is correct |
72 |
Correct |
74 ms |
30260 KB |
Output is correct |
73 |
Correct |
207 ms |
34752 KB |
Output is correct |
74 |
Correct |
245 ms |
31324 KB |
Output is correct |
75 |
Correct |
136 ms |
34664 KB |
Output is correct |
76 |
Correct |
124 ms |
33616 KB |
Output is correct |
77 |
Correct |
239 ms |
31488 KB |
Output is correct |