#include <bits/stdc++.h>
#include "catdog.h"
using namespace std;
const int nmax = 1e5 + 5, qmax = 1e5 + 5, inf = 1e8 + 8;
#define red first
#define blue second
#define pii pair<int,int>
// -1 -- insipid, 0 -- rosu, 1 -- albastru
int n;
vector<int> g[nmax];
namespace HLD {
namespace AINT {
struct Mat {
int dp[2][2];
#warning poate pica memset
Mat() {dp[0][0] = dp[1][1] = 0, dp[0][1] = dp[1][0] = inf;}
Mat(int _00, int _11) {
dp[0][0] = _00;
dp[1][1] = _11;
dp[0][1] = inf;
dp[1][0] = inf;
}
Mat(int _00, int _01, int _10, int _11) {
dp[0][0] = _00;
dp[0][1] = _01;
dp[1][0] = _10;
dp[1][1] = _11;
}
Mat operator + (const Mat& x) const {
Mat rez;
for(int l = 0; l < 2; l++)
for(int r = 0; r < 2; r++) {
rez.dp[l][r] = inf;
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++)
rez.dp[l][r] = min(rez.dp[l][r], dp[l][i] + x.dp[j][r] + (i ^ j));
}
return rez;
}
};
Mat aint[nmax * 4];
void upd(int poz, int l, int r, int node = 1, int cl = 1, int cr = n) {
if(cl == cr) {
aint[node] = Mat(l, r);
return;
}
int mid = cl + cr >> 1;
if(poz <= mid)
upd(poz, l, r, 2 * node, cl, mid);
else
upd(poz, l, r, 2 * node + 1, mid + 1, cr);
aint[node] = aint[2 * node] + aint[2 * node + 1];
//cout << '\t' << cl << ' ' << cr <<'\n';
auto rez = aint[node];
//cout << "\t> " << rez.dp[0][0] << ' ' << rez.dp[0][1] << "\n\t> " << rez.dp[1][0] << ' ' << rez.dp[1][1] << '\n';
return;
}
Mat GetQuery(int l, int r, int node = 1, int cl = 1, int cr = n) {
if(r < cl || cr < l)
return Mat();
if(l <= cl && cr <= r)
return aint[node];
int ok = 0, mid = cl + cr >> 1;
Mat rez;
if(l <= mid)
rez = GetQuery(l, r, 2 * node ,cl, mid), ok = 1;
if(mid < r)
if(ok)
rez = rez + GetQuery(l, r, 2 * node + 1, mid + 1, cr);
else
rez = GetQuery(l, r, 2 * node + 1, mid + 1, cr);
return rez;
}
pii query(int l, int r) {
Mat rez = GetQuery(l, r);
//cout << l << ' ' << r << '\n';
//cout << "> " << rez.dp[0][0] << ' ' << rez.dp[0][1] << "\n> " << rez.dp[1][0] << ' ' << rez.dp[1][1] << '\n';
return {min(rez.dp[0][0], rez.dp[0][1]),
min(rez.dp[1][0], rez.dp[1][1])};
}
}
int p[nmax], preord[nmax], pin[nmax], lch[nmax], rch[nmax], atrch[nmax], inp = 1, inch = 0;
int area[nmax];
void initarea(int node, int f = 1) {
area[node] = 1;
atrch[node] = rch[node - 1] = 0;
lch[node - 1] = inf;
p[node] = f;
for(auto x : g[node]) {
if(x != f)
initarea(x, node), area[node] += area[x];
}
}
void initdfs(int node, int f = 1) {
atrch[node] = inch;
lch[inch] = min(inp, lch[inch]);
rch[inch] = max(inp, rch[inch]);
pin[node] = inp, preord[node] = inp++;
//cout << node << ' ' << pin[node] << ' ' << inch << '\t' << lch[inch] << ' ' << rch[inch]<< '\n';
if(node != f && g[node].size() == 1)
return;
vector<int> son;
for(auto x : g[node]) {
if(x == f)
continue;
son.push_back(x);
}
sort(son.begin(), son.end(), [&](auto x, auto y){return area[x] < area[y];});
initdfs(son.back(), node);
son.pop_back();
for(auto x : son) {
inch++;
initdfs(x, node);
}
}
int fch(int ch) {
return preord[lch[ch]];
}
int color[nmax];
pii sons[nmax], dp[nmax], total[nmax];
int gotop(int u) {
int ch = atrch[u];
dp[u] = sons[u];
if(color[u] == 0)
dp[u].blue = inf;
else if(color[u] == 1)
dp[u].red = inf;
//cout << u << ' ' << dp[u].red << ' ' << dp[u].blue << '\n';
AINT::upd(pin[u], dp[u].red, dp[u].blue);
pii rez = AINT::query(lch[ch], rch[ch]);
//cout << rez.red << ' ' << rez.blue << '\n';
if(ch == 0)
return min(rez.red, rez.blue);
u = fch(ch);
int f = p[u];
sons[f].red -= min(total[u].red, total[u].blue + 1), sons[f].blue -= min(total[u].red + 1, total[u].blue);
sons[f].red += min(rez.red, rez.blue + 1), sons[f].blue += min(rez.red + 1, rez.blue);
return gotop(f);
}
int setcolor(int u, int x) {
color[u] = x;
return gotop(u);
}
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n = N;
for(int i = 0; i < N - 1; i++)
g[A[i]].push_back(B[i]),
g[B[i]].push_back(A[i]);
HLD::initarea(1);
HLD::initdfs(1);
}
int cat(int v) {
return HLD::setcolor(v, 0);
}
int dog(int v) {
return HLD::setcolor(v, 1);
}
int neighbor(int v) {
return HLD::setcolor(v, -1);
}
Compilation message
catdog.cpp:15:8: warning: #warning poate pica memset [-Wcpp]
15 | #warning poate pica memset
| ^~~~~~~
catdog.cpp: In function 'void HLD::AINT::upd(int, int, int, int, int, int)':
catdog.cpp:47:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | int mid = cl + cr >> 1;
| ~~~^~~~
catdog.cpp:54:12: warning: variable 'rez' set but not used [-Wunused-but-set-variable]
54 | auto rez = aint[node];
| ^~~
catdog.cpp: In function 'HLD::AINT::Mat HLD::AINT::GetQuery(int, int, int, int, int)':
catdog.cpp:64:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
64 | int ok = 0, mid = cl + cr >> 1;
| ~~~^~~~
catdog.cpp:68:9: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
68 | if(mid < r)
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8916 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
8916 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8916 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
8916 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8916 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
8916 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
