Submission #884063

#TimeUsernameProblemLanguageResultExecution timeMemory
884063vjudge1Cats or Dogs (JOI18_catdog)C++14
38 / 100
3013 ms15960 KiB
#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, ID); } 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] + 1)); } } } 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); }

Compilation message (stderr)

catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:180:16: warning: statement has no effect [-Wunused-value]
  180 |     Tree::pch[0];
      |     ~~~~~~~~~~~^
catdog.cpp: In instantiation of 'void AINT<Node>::upd(int, Node, int, int, int) [with Node = Tree::Mat]':
catdog.cpp:38:34:   required from 'void AINT<Node>::upd(int, Node) [with Node = Tree::Mat]'
catdog.cpp:140:42:   required from here
catdog.cpp:23:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |         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:39:44:   required from 'Node AINT<Node>::query(int, int) [with Node = Tree::Mat]'
catdog.cpp:159:75:   required from here
catdog.cpp:33:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         int mid = cl + cr >> 1;
      |                   ~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...