#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
template<typename Node>
struct AINT {
vector<Node> aint;
int n;
Node ID;
void init(int _n, Node id) {
ID = id;
n = _n;
aint.resize(n * 2 + 5, Node());
}
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;
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];
// cerr << cl << ' ' << cr << " :: \t" << aint[node].mat[0][0] << ' ' << aint[node].mat[1][1] << '\n'
}
Node query(int l, int r, int node, int cl, int cr) {
if(r < cl || cr < l) return ID;
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, Node x) { upd(p, x, 1, 1, n); }
Node query(int l, int r) { return query(l, r, 1, 1, n); }
void push(int node, int L) {;}
};
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[pch[node]] = inp;
pin[node] = inp++;
int mx = -1;
for(auto x : g[node]) {
if(x == f) continue;
mx = 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() { for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) mat[i][j] = inf; }
Mat operator +(const Mat& x) const {
Mat rez;
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;
}
};
AINT<Mat> aint;
struct SimpleDir {
int red, blue;
SimpleDir(int a = 0, int b = 0): red(a), blue(b) {;}
SimpleDir operator +=(SimpleDir& x) { return *this = SimpleDir(red + min(x.red, x.blue + 1), blue + min(x.blue, x.red + 1)); }
SimpleDir operator -=(SimpleDir& x) { return *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) { //
// cerr << "Red: " << node << ' ' << overson[node].red << '\n';
Mat curr;
curr.mat[0][0] = overson[node].red;
return curr;
}
Mat blue(int node) { //
// cerr << "Blue: " << node << ' ' << overson[node].blue << '\n';
Mat curr;
curr.mat[1][1] = overson[node].blue;
return curr;
}
Mat gol(int node) {
// cerr << "Empty: " << node << ' ' << overson[node].red << ' ' << overson[node].blue << '\n';
Mat curr;
curr.mat[0][0] = overson[node].red;
curr.mat[1][1] = overson[node].blue;
return curr;
}
void init(int node, int f) {
aint.upd(nodepoz(node), gol(node));
for(auto x : g[node])
if(x != f)
init(x, node);
return;
}
void init(int n) {
Mat ok;
ok.mat[0][0] = 0;
ok.mat[0][1] = 0;
ok.mat[1][0] = 0;
ok.mat[1][1] = 0;
aint.init(n, ok);
init(0, 0);
// cerr << "clown\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));
// cerr << pin[father] << ' ' << lastpoz[father] << '\n';
//
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] == 0) mine[father].red = inf;
// cerr << father << " gained " << mine[father].red << ' ' << mine[father].blue << '\n';
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 initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:194:16: warning: statement has no effect [-Wunused-value]
194 | Tree::pch[0];
| ~~~~~~~~~~~^
catdog.cpp: In instantiation of 'void AINT<Node>::upd(int, Node, int, int, int) [with Node = Tree::Mat]':
catdog.cpp:37:34: required from 'void AINT<Node>::upd(int, Node) [with Node = Tree::Mat]'
catdog.cpp:147:42: required from here
catdog.cpp:22:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
22 | int mid = cl + cr >> 1;
| ~~~^~~~
catdog.cpp: In instantiation of 'Node AINT<Node>::query(int, int, int, int, int) [with Node = Tree::Mat]':
catdog.cpp:38:44: required from 'Node AINT<Node>::query(int, int) [with Node = Tree::Mat]'
catdog.cpp:171:75: required from here
catdog.cpp:32:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
32 | int mid = cl + cr >> 1;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6748 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6748 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6748 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
