Submission #58203

#TimeUsernameProblemLanguageResultExecution timeMemory
58203memikakizakiCats or Dogs (JOI18_catdog)C++14
100 / 100
897 ms19760 KiB
#include "catdog.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define epb emplace_back #define mp make_pair #define all(a) begin(a), end(a) #define csz(a) (int) a.size() #define fori(i, a, b) for(int i = (int) a; i <= (int) b; ++i) #define rofi(i, b, a) for(int i = (int) b; i >= (int) a; --i) #define foreach(tt, a) for(auto &tt: a) #define long long long const int INF = 1e9+1; const long MOD = 1e9+7, LINF = 1e16+1; const int N = 1 << 17; typedef array<array<int, 2>, 2> arr22; int n, state[N]; pair<int,int> lastval[N]; vector<int> g[N]; int par[N], sz[N], in[N], nxt[N], down[N]; void dfs_sz(int u) { sz[u] = 1; foreach(v, g[u]) if(v != par[u]) { par[v] = u; dfs_sz(v); sz[u] += sz[v]; if(g[u][0] == par[u] || sz[v] > sz[g[u][0]]) swap(v, g[u][0]); } } void dfs_hld(int u) { static int tick = 0; in[u] = tick++; down[nxt[u]] = u; foreach(v, g[u]) if(v != par[u]) { nxt[v] = (v == g[u][0] ? nxt[u] : v); dfs_hld(v); } } arr22 t[2*N]; arr22 merge(arr22 a, arr22 b) { arr22 ret; ret[0][0] = ret[0][1] = ret[1][0] = ret[1][1] = INF; fori(i, 0, 1) fori(j, 0, 1) fori(x, 0, 1) fori(y, 0, 1) { ret[i][j] = min(a[i][x] + b[y][j] + (x != y), ret[i][j]); } return ret; } void build(int i = 1, int l = 0, int r = N-1) { if(l == r) { t[i][0][1] = t[i][1][0] = INF; return; } int mid = l+r >> 1; build(i << 1, l, mid); build(i << 1 | 1, mid+1, r); t[i] = merge(t[i << 1], t[i << 1 | 1]); } void update(int targ, pair<int,int> val, int i = 1, int l = 0, int r = N-1) { if(l == r) { t[i][0][0] += val.first, t[i][1][1] += val.second; return; } int mid = l+r >> 1; if(targ <= mid) update(targ, val, i << 1, l, mid); else update(targ, val, i << 1 | 1, mid+1, r); t[i] = merge(t[i << 1], t[i << 1 | 1]); } arr22 query(int tl, int tr, int i = 1, int l = 0, int r = N-1) { if(l > tr || r < tl) { arr22 ret; fori(x, 0, 1) fori(y, 0, 1) ret[x][y] = 0; return ret; } if(tl <= l && r <= tr) return t[i]; int mid = l+r >> 1; arr22 lf = query(tl, tr, i << 1 , l, mid); arr22 rg = query(tl, tr, i << 1 | 1, mid+1, r); arr22 ret; if(tr <= mid) ret = lf; else if(tl > mid) ret = rg; else ret = merge(lf, rg); return ret; } void initialize(int _n, vector<int> U, vector<int> V) { n = _n; fori(i, 0, n-2) { g[U[i]].pb(V[i]); g[V[i]].pb(U[i]); } dfs_sz(1); nxt[1] = 1; dfs_hld(1); build(); } void propogate(int v, pair<int,int> val) { while(v) { update(in[v], val); arr22 curr = query(in[nxt[v]], in[down[nxt[v]]]); pair<int,int> mn = {min(curr[0][0], curr[0][1]), min(curr[1][0], curr[1][1])}; pair<int,int> mn2 = {min(mn.first, mn.second + 1), min(mn.first + 1, mn.second)}; val = mp(mn2.first - lastval[nxt[v]].first, mn2.second - lastval[nxt[v]].second); lastval[nxt[v]] = mn2; v = par[nxt[v]]; } } int answer() { int ans = INF; arr22 ret = query(in[1], in[down[1]]); fori(i, 0, 1) fori(j, 0, 1) ans = min(ret[i][j], ans); return ans; } int cat(int v) { state[v] = 1; propogate(v, mp(0, INF)); return answer(); } int dog(int v) { state[v] = 2; propogate(v, mp(INF, 0)); return answer(); } int neighbor(int v) { if(state[v] == 1) propogate(v, mp(0, -INF)); else propogate(v, mp(-INF, 0)); return answer(); }

Compilation message (stderr)

catdog.cpp: In function 'void build(int, int, int)':
catdog.cpp:57:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l+r >> 1;
            ~^~
catdog.cpp: In function 'void update(int, std::pair<int, int>, int, int, int)':
catdog.cpp:67:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l+r >> 1;
            ~^~
catdog.cpp: In function 'arr22 query(int, int, int, int, int)':
catdog.cpp:79:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l+r >> 1;
            ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...