#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e5 + 5, mod = 1e9 + 7, inf = 2e8;
int n, m;
vector<int> g[nmax], path[nmax];
int sz[nmax], heavy[nmax], depth[nmax], top[nmax], parent[nmax], pos[nmax], crtpos, bottom[nmax];
struct T {
int cc, cd, dc, dd;
};
T aint[nmax * 4];
T combine(T x, T y) {
T ans = {inf, inf, inf, inf};
ans.cc = min({x.cc + y.cc, x.cc + y.dc + 1, x.cd + y.dc, x.cd + y.cc + 1});
ans.cd = min({x.cc + y.cd, x.cc + y.dd + 1, x.cd + y.dd, x.cd + y.cd + 1});
ans.dd = min({x.dd + y.dd, x.dd + y.cd + 1, x.dc + y.cd, x.dc + y.dd + 1});
ans.dc = min({x.dd + y.dc, x.dd + y.cc + 1, x.dc + y.cc, x.dc + y.dc + 1});
return ans;
}
void build(int node, int left, int right) {
if (left == right) {
aint[node].cc = aint[node].dd = 0;
aint[node].cd = aint[node].dc = inf;
return;
}
int mid = (left + right) / 2;
build(node * 2, left, mid);
build(node * 2 + 1, mid + 1, right);
// aint[node] = combine(aint[node * 2], aint[node * 2 + 1]);
aint[node].cc = aint[node].dd = 0;
aint[node].cd = aint[node].dc = 0;
}
void update(int node, int left, int right, int x, pair<int, int> y) {
if (left == right) {
aint[node].cc = y.first;
aint[node].dd = y.second;
return;
}
int mid = (left + right) / 2;
if (x <= mid) update(node * 2, left, mid, x, y);
else update(node * 2 + 1, mid + 1, right, x, y);
aint[node] = combine(aint[node * 2], aint[node * 2 + 1]);
}
void update(int x, pair<int, int> y) {
update(1, 1, n, x, y);
}
T query(int node, int left, int right, int x, int y) {
if (x <= left && right <= y) {
return aint[node];
}
int mid = (left + right) / 2;
if (x <= mid && y > mid) {
return combine(query(node * 2, left, mid, x, y), query(node * 2 + 1, mid + 1, right, x, y));
}
if (x <= mid) {
return query(node * 2, left, mid, x, y);
}
if (y > mid) {
return query(node * 2 + 1, mid + 1, right, x, y);
}
}
T query(int x, int y) {
return query(1, 1, n, x, y);
}
void dfs1(int x, int par = 0) {
sz[x] = 1;
parent[x] = par;
depth[x] = depth[par] + 1;
int mx = 0;
for (auto y: g[x]) {
if (y == par) continue;
dfs1(y, x);
sz[x] += sz[y];
if (sz[y] > mx) {
heavy[x] = y;
mx = sz[y];
}
}
}
void decompose(int x, int crttop) {
path[crttop].push_back(x);
top[x] = crttop;
pos[x] = ++crtpos;
if (heavy[x]) {
decompose(heavy[x], crttop);
}
for (auto y: g[x]) {
if (y == parent[x]) continue;
if (heavy[x] != y) {
decompose(y, y);
}
}
}
pair<int, int> getval(int x) {
pair<int, int> ans; // first - cc ; second - dd
for (auto y: g[x]) {
if (y == parent[x] || y == heavy[x]) continue;
T crt = query(pos[top[y]], pos[bottom[y]]);
ans.first += min({crt.cc, crt.cd, crt.dc + 1, crt.dd + 1});
ans.second += min({crt.cc + 1, crt.cd + 1, crt.dc, crt.dd});
}
return ans;
}
void dfs(int x) {
for (auto y: g[x]) {
if (y == parent[x]) continue;
dfs(y);
}
pair<int, int> ans = getval(x);
update(pos[x], ans);
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n = N; m = A.size();
for (int i = 0; i < m; i++) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
dfs1(1);
decompose(1, 1);
build(1, 1, n);
for (int i = 1; i <= n; i++) {
for (auto x: path[i]) {
bottom[x] = path[i].back();
}
}
dfs(1);
}
int cat(int x) {
pair<int, int> crt = getval(x);
update(pos[x], {crt.first, inf});
x = parent[top[x]];
while (x) {
update(pos[x], getval(x));
x = parent[top[x]];
}
T ans = query(pos[top[1]], pos[bottom[1]]);
return min({ans.cc, ans.cd, ans.dc, ans.dd});
}
int dog(int x) {
pair<int, int> crt = getval(x);
update(pos[x], {inf, crt.second});
x = parent[top[x]];
while (x) {
update(pos[x], getval(x));
x = parent[top[x]];
}
T ans = query(pos[top[1]], pos[bottom[1]]);
return min({ans.cc, ans.cd, ans.dc, ans.dd});
}
int neighbor(int x) {
pair<int, int> crt = getval(x);
update(pos[x], crt);
x = parent[top[x]];
while (x) {
update(pos[x], getval(x));
x = parent[top[x]];
}
T ans = query(pos[top[1]], pos[bottom[1]]);
return min({ans.cc, ans.cd, ans.dc, ans.dd});
}
Compilation message
catdog.cpp: In function 'T query(int, int, int, int, int)':
catdog.cpp:71:1: warning: control reaches end of non-void function [-Wreturn-type]
71 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9828 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
9828 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9828 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
9828 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9828 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
9828 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
