Submission #99303

#TimeUsernameProblemLanguageResultExecution timeMemory
99303youngyojunCats or Dogs (JOI18_catdog)C++11
0 / 100
5 ms2816 KiB
#include "catdog.h" #include <bits/stdc++.h> #define eb emplace_back #define INF (0x3f3f3f3f) using namespace std; const int MAXN = 100055; static int _int[MAXN<<5], *_intp=_int; inline int* newint(const unsigned int SZ) { _intp += SZ; return _intp - SZ; } struct HLD { int *DCC, *DCD, *DDC, *DDD; int *CC, *CD; int n, MX, pc, pd; void init(int _n) { n = _n; for(MX = 1; MX < n; MX <<= 1); CC = newint(n); CD = newint(n); DCC = newint(MX<<1); DCD = newint(MX<<1); DDC = newint(MX<<1); DDD = newint(MX<<1); fill(DCD+MX, DCD+(MX<<1), INF); fill(DDC+MX, DDC+(MX<<1), INF); } void upd(int i) { DCC[i+MX] = CC[i]; DDD[i+MX] = CD[i]; for(i = (i+MX)>>1; i; i >>= 1) { int l = i<<1, r = l|1; DCC[i] = min({INF, DCC[l]+DCC[r], DCD[l]+DDC[r] , DCC[l]+DDC[r]+1, DCD[l]+DCC[r]+1}); DDD[i] = min({INF, DDD[l]+DDD[r], DDC[l]+DCD[r] , DDD[l]+DCD[r]+1, DDC[l]+DDD[r]+1}); DCD[i] = min({INF, DCC[l]+DCD[r], DCD[l]+DDD[r] , DCC[l]+DDD[r]+1, DCD[l]+DCD[r]+1}); DDC[i] = min({INF, DDD[l]+DDC[r], DDC[l]+DCC[r] , DDD[l]+DCC[r]+1, DDC[l]+DDC[r]+1}); } } int get() { return min({DCC[1], DCD[1], DDC[1], DDD[1]}); } } hld[MAXN]; vector<int> G[MAXN]; int SC[MAXN], SD[MAXN]; int HI[MAXN], HJ[MAXN], HC[MAXN], HR[MAXN], Hn; int prt[MAXN], dep[MAXN], cnt[MAXN]; bitset<MAXN> chk, isc; int N, Q; void g(int v) { auto &V = hld[HI[v]]; int j = HJ[v]; V.CC[j] = SC[v]; V.CD[j] = SD[v]; if(chk[v]) (isc[v] ? V.CD[j] : V.CC[j]) = INF; } void f(int v) { for(int p, j; v; v = p) { g(v); auto &V = hld[HI[v]]; j = HJ[v]; p = prt[HR[HI[v]]]; V.upd(j); SC[p] -= min(V.pc, V.pd+1); SD[p] -= min(V.pd, V.pc+1); V.pc = min(V.DCC[1], V.DCD[1]); V.pd = min(V.DDC[1], V.DDD[1]); SC[p] += min(V.pc, V.pd+1); SD[p] += min(V.pd, V.pc+1); } } void hfs(int i) { HC[HI[i]]++; int hi = -1, hc = 0; for(int v : G[i]) if(v != prt[i] && hc < cnt[v]) { hi = v; hc = cnt[v]; } if(!hc) return; HI[hi] = HI[i]; HJ[hi] = HJ[i]+1; for(int v : G[i]) if(v != prt[i]) { if(v != hi) { HI[v] = ++Hn; HR[Hn] = v; } hfs(v); } } void dfs(int i) { cnt[i] = 1; for(int v : G[i]) if(!dep[v]) { dep[v] = dep[i] + 1; prt[v] = i; dfs(v); cnt[i] += cnt[v]; } } void initialize(int N, std::vector<int> _A, std::vector<int> _B) { ::N = N; for(int i = 1, a, b; i < N; i++) { a = _A[i-1]; b = _B[i-1]; G[a].eb(b); G[b].eb(a); } dep[1] = 1; dfs(1); HI[1] = HR[1] = Hn = 1; hfs(1); for(int i = 1; i <= Hn; i++) hld[i].init(HC[i]); } int cat(int v) { chk[v] = isc[v] = true; f(v); return hld[1].get(); } int dog(int v) { chk[v] = true; isc[v] = false; f(v); return hld[1].get(); } int neighbor(int v) { chk[v] = isc[v] = false; f(v); return hld[1].get(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...