#include "catdog.h"
#include <iostream>
#include <algorithm>
#include <vector>
#pragma GCC optimize("Ofast,unroll-loops")
//
using namespace std;
const int nmax = 1e5 + 5;
const int inf = 1e6 + 5;
namespace Tree {
vector<int> g[nmax];
int area[nmax];
int pch[nmax], lastpoz[nmax], p[nmax];
int pin[nmax], pout[nmax], inp = 1;
int nodepoz(int node) { return pin[node];}
namespace Init {
void preinit(int node, int f) {
p[node] = f;
area[node] = 1;
for(auto x : g[node]) {
if(x == f) continue;
preinit(x, node);
area[node] += area[x];
}
return;
}
void init(int node, int f) {
lastpoz[pin[pch[node]]] = inp;
pin[node] = inp++;
int mx = -1;
for(auto x : g[node]) {
if(x == f) continue;
mx = mx == -1 || area[mx] < area[x]? x : mx;
}
if(mx == -1) {pout[node] = inp - 1; return; }
pch[mx] = pch[node];
init(mx, node);
for(auto x : g[node]) {
if(x == f || x == mx) continue;
pch[x] = x;
init(x, node);
}
}
}
struct Mat {
int mat[2][2];
Mat() { mat[0][0] = mat[1][1] = 0; mat[0][1] = mat[1][0] = inf; }
Mat(int a, int b) { mat[0][0] = a; mat[1][1] = b; mat[0][1] = mat[1][0] = inf; }
Mat operator +(const Mat& x) const {
if(mat[0][0] == 0 && mat[1][1] == 0 && mat[0][1] == inf && mat[1][0] == inf) return x;
if(x.mat[0][0] == 0 && x.mat[1][1] == 0 && x.mat[0][1] == inf && x.mat[1][0] == inf) return *this;
// if(x == ok) return *this;
Mat rez;
rez.mat[0][0] = rez.mat[1][1] = inf;
for(int L = 0; L < 2; L++) {
for(int M1 = 0; M1 < 2; M1++) {
for(int M2 = 0; M2 < 2; M2++) {
for(int R = 0; R < 2; R++) {
rez.mat[L][R] = min(rez.mat[L][R], mat[L][M1] + x.mat[M2][R] + (M1 ^ M2));
}
}
}
}
return rez;
}
};
#define Node Mat
namespace aint {
Node aint[nmax * 4];
int n;
void init(int _n) {
n = _n;
// aint.resize(n * 2 + 2);
}
void push(int node, int L) {;}
void upd(int p, Node x, int node, int cl, int cr) {
if(p < cl || cr < p) return;
if(cl == cr) { aint[node] = x; return; }
int mid = cl + cr >> 1, L = (mid - cl + 1) * 2;
push(node, (mid - cl + 1) * 2);
upd(p, x, node + 1, cl, mid);
upd(p, x, node + L, mid + 1, cr);
aint[node] = aint[node + 1] + aint[node + L];
}
Node query(int l, int r, int node, int cl, int cr) {
if(r < cl || cr < l) return Node();
if(l <= cl && cr <= r) return aint[node];
int mid = cl + cr >> 1, L = (mid - cl + 1) * 2;
push(node, (mid - cl + 1) * 2);
return query(l, r, node + 1, cl, mid) + query(l, r, node + L, mid + 1, cr);
}
void upd(int p, Node x) { upd(p, x, 1, 1, n); }
Node query(int l, int r) { return query(l, r, 1, 1, n); }
};
#undef Node
struct SimpleDir {
int red, blue;
SimpleDir(int a = 0, int b = 0): red(a), blue(b) {;}
void operator +=(const SimpleDir& x) { *this = SimpleDir(red + min(x.red, x.blue + 1), blue + min(x.blue, x.red + 1)); }
void operator -=(const SimpleDir& x) { *this = SimpleDir(red - min(x.red, x.blue + 1), blue - min(x.blue, x.red + 1)); }
};
SimpleDir overson[nmax], mine[nmax];
int color[nmax];
Mat red(int node) {
Mat curr(overson[node].red, inf);
return curr;
}
Mat blue(int node) {
Mat curr(inf, overson[node].blue);
return curr;
}
Mat gol(int node) {
Mat curr(overson[node].red, overson[node].blue);
return curr;
}
void init(int n) {
aint::init(n);
// init(0, 0);
}
int upd(int node) {
int P = pin[node], K = pin[pch[node]];
int father = pch[node];
if(color[P] == 0)
aint::upd(P, gol(P));
else if(color[P] == 1)
aint::upd(P, red(P));
else
aint::upd(P, blue(P));
if(father == 0) { auto R = aint::query(K, lastpoz[K]); return min({R.mat[0][0],R.mat[0][1],R.mat[1][0],R.mat[1][1]});}
overson[pin[p[father]]] -= mine[K];
auto R = aint::query(K, lastpoz[father]);
mine[K] = SimpleDir(min(R.mat[0][0], R.mat[0][1]), min(R.mat[1][0], R.mat[1][1]));
if(color[K] == 1) mine[K].blue = inf;
else if(color[K] == 2) mine[K].red = inf;
overson[pin[p[father]]] += mine[K];
return upd(p[node]);
}
}
void initialize(int n, std::vector<int> A, std::vector<int> B) {
for(int i = 0; i < n - 1; i++) {
Tree::g[--A[i]].emplace_back(--B[i]);
Tree::g[B[i]].emplace_back(A[i]);
}
Tree::Init::preinit(0, 0);
Tree::pch[0] = 0;
Tree::Init::init(0, 0);
Tree::init(n);
return;
}
int cat(int v) {
Tree::color[Tree::pin[--v]] = 1;
return Tree::upd(v);
}
int dog(int v) {
Tree::color[Tree::pin[--v]] = 2;
return Tree::upd(v);
}
int neighbor(int v) {
Tree::color[Tree::pin[--v]] = 0;
return Tree::upd(v);
}
Compilation message
catdog.cpp: In function 'void Tree::aint::upd(int, Tree::Mat, int, int, int)':
catdog.cpp:92:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
92 | int mid = cl + cr >> 1, L = (mid - cl + 1) * 2;
| ~~~^~~~
catdog.cpp: In function 'Tree::Mat Tree::aint::query(int, int, int, int, int)':
catdog.cpp:101:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
101 | int mid = cl + cr >> 1, L = (mid - cl + 1) * 2;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
13144 KB |
Output is correct |
| 2 |
Correct |
3 ms |
13148 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
13148 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
13144 KB |
Output is correct |
| 2 |
Correct |
3 ms |
13148 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
13148 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
13144 KB |
Output is correct |
| 2 |
Correct |
3 ms |
13148 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
13148 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
