| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 884059 | vjudge1 | Cats or Dogs (JOI18_catdog) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "catdog.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
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 = 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() { 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 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]));
}
}
}
}
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) {
Mat curr;
curr.mat[0][0] = overson[node].red;
return curr;
}
Mat blue(int node) {
Mat curr;
curr.mat[1][1] = overson[node].blue;
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 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[1][1] = 0;
aint.init(n, ok);
init(0, 0);
}
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);
}