//#include "catdog.h"
#include<vector>
#include<algorithm>
#pragma GCC optimize("O3")
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],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[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 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;
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 R = 0; R < 2; R++)
rez.mat[L][R] = min(rez.mat[L][R], mat[L][M1] + min(x.mat[M1][R], x.mat[M1 ^ 1][R] + 1));
return rez;
}
};
Mat ok;
namespace aint {
vector<Mat> aint;
int n;
void init(int _n) {
aint.resize(_n * 2 + 1);
}
void push(int node, int L) {;}
void upd(int p, Mat 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;
push(node, (mid - cl + 1) * 2);
upd(p, x, node + 1, cl, mid);
upd(p, x, node + (mid - cl + 1) * 2, mid + 1, cr);
aint[node] = aint[node + 1] + aint[node + (mid - cl + 1) * 2];
}
Mat query(int l, int r, int node, int cl, int cr) {
if(r < cl || cr < l) return Mat();
if(l <= cl && cr <= r) return aint[node];
int mid = cl + cr >> 1;
push(node, (mid - cl + 1) * 2);
return query(l, r, node + 1, cl, mid) + query(l, r, node + (mid - cl + 1) * 2, mid + 1, cr);
}
void upd(int p, Mat x) { upd(p, x, 1, 1, n); }
Mat query(int l, int r) { return query(l, r, 1, 1, n); }
};
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;
curr.mat[0][0] = overson[node].red;
curr.mat[1][1] = inf;
return curr;
}
Mat blue(int node) {
Mat curr;
curr.mat[1][1] = overson[node].blue;
curr.mat[0][0] = inf;
return curr;
}
Mat gol(int node) {
Mat curr;
curr.mat[0][0] = overson[node].red;
curr.mat[1][1] = overson[node].blue;
return curr;
}
void init(int n) {
aint::init(n);
}
int upd(int node) {
int father = pch[node];
aint::upd(nodepoz(node), color[node] == 0? gol(node) : color[node] == 1? red(node) : blue(node));
if(father == 0) { auto R = aint::query(pin[father], lastpoz[father]); return min({R.mat[0][0],R.mat[0][1],R.mat[1][0],R.mat[1][1]});}
overson[p[father]] -= mine[father];
auto R = aint::query(pin[father], lastpoz[father]);
mine[father] = SimpleDir(min(R.mat[0][0], R.mat[0][1]), min(R.mat[1][0], R.mat[1][1]));
if(color[father] == 1) mine[father].blue = inf;
if(color[father] == 2) mine[father].red = inf;
overson[p[father]] += mine[father];
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];
Tree::Init::init(0, 0);
Tree::init(n);
return;
}
int cat(int v) {
Tree::color[--v] = 1;
return Tree::upd(v);
}
int dog(int v) {
Tree::color[--v] = 2;
return Tree::upd(v);
}
int neighbor(int v) {
Tree::color[--v] = 0;
return Tree::upd(v);
}
Compilation message
catdog.cpp: In function 'void Tree::aint::upd(int, Tree::Mat, int, int, int)':
catdog.cpp:76:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
76 | int mid = cl + cr >> 1;
| ~~~^~~~
catdog.cpp: In function 'Tree::Mat Tree::aint::query(int, int, int, int, int)':
catdog.cpp:85:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
85 | int mid = cl + cr >> 1;
| ~~~^~~~
catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:143:16: warning: statement has no effect [-Wunused-value]
143 | Tree::pch[0];
| ~~~~~~~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
