제출 #122598

#제출 시각아이디문제언어결과실행 시간메모리
122598WhipppedCreamCats or Dogs (JOI18_catdog)C++17
0 / 100
4 ms2816 KiB
#include "catdog.h" #include <bits/stdc++.h> #pragma GCC optimize ("O3") #pragma GCC target ("sse4") using namespace std; #define X first #define Y second #define pb push_back typedef pair<int, int> ii; typedef long long ll; const int maxn = 1e5+5; int n; vector<int> adj[maxn]; int par[22][maxn]; int dep[maxn]; int cnt[maxn]; int prf[maxn]; int pos[maxn]; int head[maxn]; int stat[maxn]; //1 cat 2 Dog int run = 0; struct segtree { ll st[4*maxn]; ll lz[4*maxn]; void push(int p, int L, int R) { if(!lz) return; st[p] += lz[p]; if(L != R) { lz[2*p] += lz[p]; lz[2*p+1] += lz[p]; } lz[p] = 0; } void pull(int p) { st[p] = st[2*p] + st[2*p+1]; } void update(int i, int j, int dx, int p = 1, int L = 1, int R = n) { push(p, L, R); if(i> R || j< L) return; if(i<= L && R<= j) { lz[p] += dx; push(p, L, R); return; } int M = (L+R)/2; update(i, j, dx, 2*p, L, M); update(i, j, dx, 2*p+1, M+1, R); pull(p); } int ask(int i, int j, int p = 1, int L = 1, int R = n) { if(i> R || j< L) return 0; push(p, L, R); if(i<= L && R<= j) return st[p]; int M = (L+R)/2; int x = ask(i, j, 2*p, L, M); int y = ask(i, j, 2*p+1, M+1, R); return x+y; } }; segtree Cat, Dog, sum; void changeme(segtree &st, int u, int v, int dx) { if(dep[u]< dep[v]) return; while(head[u] != head[v]) { st.update(pos[head[u]], pos[u], dx); u = par[0][head[u]]; } st.update(pos[v], pos[u], dx); } int gimme(segtree &st, int u, int v) { //v higher than u, v an ancestor of u if(v == 0) v = 1; int res = 0; while(head[u] != head[v]) { res += st.ask(pos[head[u]], pos[u]); u = par[0][head[u]]; } res += st.ask(pos[v], pos[u]); return res; } void dfs(int u = 1, int p = 0) { dep[u] = dep[p]+1; par[0][u] = p; for(int i = 1; i<= 20; i++) par[i][u] = par[i-1][par[i-1][u]]; cnt[u] = 1; ii big = {0, -1}; for(int v : adj[u]) { if(v == p) continue; dfs(v, u); big = max(big, {cnt[v], v}); cnt[u] += cnt[v]; } prf[u] = big.Y; } void hld() { for(int i = 1; i<= n; i++) { if(prf[par[0][i]] == i) continue; for(int j = i; j != -1; j = prf[j]) { head[j] = i; pos[j] = ++run; } } } void initialize(int N, vector<int> A, vector<int> B) { n = N; for(int i = 0; i< n-1; i++) { adj[A[i]].pb(B[i]); adj[B[i]].pb(A[i]); } dfs(); hld(); // printf("ok\n"); } int cat(int u) { int c = gimme(Cat, u, u); int d = gimme(Dog, u, u); int cc = min(c, d+1); int dd = min(d, c+1); int cx = c; int dx = c+1; int cur = u; for(int i = 20; i>= 0; i--) { if(gimme(sum, u, par[i][cur]) == 0) { cur = par[i][cur]; } } // printf("cur = %d\n", cur); cur = par[0][cur]; bool iszero = (cur == 0); if(cur == 0) cur = 1; changeme(Cat, par[0][u], cur, cx-cc); changeme(Dog, par[0][u], cur, dx-dd); if(!iszero) { int st = stat[cur]; if(st == 1) { dd = cc+1; dx = cx+1; } else { cc = dd+1; cx = dx+1; } cur = par[0][cur]; if(cur) { changeme(Cat, cur, 1, cx-cc); changeme(Dog, cur, 1, dx-dd); } } stat[u] = 1; // for(int i = 1; i<= n; i++) printf("%d ", gimme(Cat, i, i)); // printf("\n"); // for(int i = 1; i<= n; i++) printf("%d ", gimme(Dog, i, i)); // printf("\n"); if(stat[u] == 1) return gimme(Cat, 1, 1); if(stat[u] == 2) return gimme(Dog, 1, 1); return min(gimme(Cat, 1, 1), gimme(Dog, 1, 1)); } int dog(int u) { int c = gimme(Cat, u, u); int d = gimme(Dog, u, u); int cc = min(c, d+1); int dd = min(d, c+1); int cx = d+1; int dx = d; int cur = u; for(int i = 20; i>= 0; i--) { if(gimme(sum, u, par[i][cur]) == 0) { cur = par[i][cur]; } } cur = par[0][cur]; bool iszero = (cur == 0); if(cur == 0) cur = 1; changeme(Cat, par[0][u], cur, cx-cc); changeme(Dog, par[0][u], cur, dx-dd); if(!iszero) { int st = stat[cur]; if(st == 1) { dd = cc+1; dx = cx+1; } else { cc = dd+1; cx = dx+1; } cur = par[0][cur]; if(cur) { changeme(Cat, cur, 1, cx-cc); changeme(Dog, cur, 1, dx-dd); } } stat[u] = 2; // for(int i = 1; i<= n; i++) printf("%d ", gimme(Cat, i, i)); // printf("\n"); // for(int i = 1; i<= n; i++) printf("%d ", gimme(Dog, i, i)); // printf("\n"); if(stat[u] == 1) return gimme(Cat, 1, 1); if(stat[u] == 2) return gimme(Dog, 1, 1); return min(gimme(Cat, 1, 1), gimme(Dog, 1, 1)); } int neighbor(int u) { int c = gimme(Cat, u, u); int d = gimme(Dog, u, u); int cc, dd; if(stat[u] == 1) { cc = c; dd = c+1; } else { cc = d+1; dd = d; } int cx = min(c, d+1); int dx = min(c+1, d); int cur = u; for(int i = 20; i>= 0; i--) { if(gimme(sum, u, par[i][cur]) == 0) { cur = par[i][cur]; } } cur = par[0][cur]; bool iszero = (cur == 0); if(cur == 0) cur = 1; changeme(Cat, par[0][u], cur, cx-cc); changeme(Dog, par[0][u], cur, dx-dd); if(!iszero) { int st = stat[cur]; if(st == 1) { dd = cc+1; dx = cx+1; } else { cc = dd+1; cx = dx+1; } cur = par[0][cur]; if(cur) { changeme(Cat, cur, 1, cx-cc); changeme(Dog, cur, 1, dx-dd); } } stat[u] = 0; // for(int i = 1; i<= n; i++) printf("%d ", gimme(Cat, i, i)); // printf("\n"); // for(int i = 1; i<= n; i++) printf("%d ", gimme(Dog, i, i)); // printf("\n"); if(stat[u] == 1) return gimme(Cat, 1, 1); if(stat[u] == 2) return gimme(Dog, 1, 1); return min(gimme(Cat, 1, 1), gimme(Dog, 1, 1)); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...