Submission #884114

#TimeUsernameProblemLanguageResultExecution timeMemory
884114vjudge1Cats or Dogs (JOI18_catdog)C++17
38 / 100
3010 ms19016 KiB
#include "catdog.h" #include <bits/stdc++.h> #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[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; push(node, (mid - cl + 1) * 2); upd(p, x, node * 2, cl, mid); upd(p, x, node * 2 + 1, mid + 1, cr); aint[node] = aint[node * 2] + aint[node * 2 + 1]; } 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; push(node, (mid - cl + 1) * 2); return query(l, r, node * 2, cl, mid) + query(l, r, node * 2 + 1, 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[father]); 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]; 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 (stderr)

catdog.cpp: In function 'void Tree::aint::upd(int, Tree::Mat, int, int, int)':
catdog.cpp:90:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |             int mid = cl + cr >> 1;
      |                       ~~~^~~~
catdog.cpp: In function 'Tree::Mat Tree::aint::query(int, int, int, int, int)':
catdog.cpp:99:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |             int mid = cl + cr >> 1;
      |                       ~~~^~~~
catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:176:16: warning: statement has no effect [-Wunused-value]
  176 |     Tree::pch[0];
      |     ~~~~~~~~~~~^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...