제출 #197055

#제출 시각아이디문제언어결과실행 시간메모리
197055iefnah06Cats or Dogs (JOI18_catdog)C++11
0 / 100
9 ms6392 KiB
#include "catdog.h" #include<bits/stdc++.h> using namespace std; const int MAXN = 1.1e5; int N; vector<int> adj[MAXN]; int A[MAXN]; int sz[MAXN]; int par[MAXN]; void dfs_sz(int cur, int prv) { if (prv) { adj[cur].erase(find(adj[cur].begin(), adj[cur].end(), prv)); } sz[cur] = 1; par[cur] = prv; for (int nxt : adj[cur]) { dfs_sz(nxt, cur); sz[cur] += sz[nxt]; } nth_element(adj[cur].begin(), adj[cur].begin(), adj[cur].end(), [&](int i, int j) { return sz[i] > sz[j]; }); } int heavypar[MAXN]; int num[MAXN]; int pos[MAXN]; void dfs_hld(int cur, int top) { heavypar[cur] = top; pos[cur] = num[top]; num[top]++; bool isfirst = true; for (int nxt : adj[cur]) { dfs_hld(nxt, (isfirst ? top : nxt)); isfirst = false; } } struct mat { int a00, a01, a10, a11; friend mat operator * (const mat& A, const mat& B) { mat R; R.a00 = min(A.a00 + B.a00, A.a01 + B.a10); R.a01 = min(A.a00 + B.a01, A.a01 + B.a11); R.a10 = min(A.a10 + B.a00, A.a11 + B.a10); R.a11 = min(A.a10 + B.a01, A.a11 + B.a11); return R; } }; struct segtree { int s; vector<mat> cost; segtree() {} segtree(int n) { for (s = 1; s < n; s *= 2) {} cost = vector<mat>(2*s); for (int i = 0; i < s; i++) { cost[i+s].a01 = cost[i+s].a10 = 1; } } void update(int i, int& v0, int& v1) { i += s; cost[i].a00 += v0; cost[i].a01 += v0; cost[i].a10 += v1; cost[i].a11 += v1; for (i /= 2; i; i /= 2) { cost[i] = cost[2*i] * cost[2*i+1]; } } void eval(int& a0, int& a1) { a0 = min(cost[1].a00, cost[1].a01); a1 = min(cost[1].a10, cost[1].a11); } } seg[MAXN]; void initialize(int n, std::vector<int> a, std::vector<int> b) { N = n; for (int i = 0; i < N-1; i++) { adj[a[i]].push_back(b[i]); adj[b[i]].push_back(a[i]); } for (int i = 1; i <= N; i++) { A[i] = 0; } dfs_sz(1, 0); dfs_hld(1, 1); for (int i = 1; i <= N; i++) { assert((pos[i] == 0) == (heavypar[i] == i)); if (heavypar[i] == i) { seg[i] = segtree(num[i]); } } } void update(int cur, int v0, int v1) { while (cur) { int top = heavypar[cur]; int cur0, cur1, nxt0, nxt1; seg[top].eval(cur0, cur1); seg[top].update(pos[cur], v0, v1); seg[top].eval(nxt0, nxt1); v0 = min(nxt0, nxt1+1) - min(cur0, cur1+1); v1 = min(nxt0+1, nxt1) - min(cur0+1, cur1); cur = par[top]; } } int query(); int cat(int v) { A[v] = 1; update(v, 0, N); return query(); } int dog(int v) { A[v] = 2; update(v, N, 0); return query(); } int neighbor(int v) { if (A[v] == 1) { update(v, 0, -N); } else if (A[v] == 2) { update(v, -N, 0); } else assert(false); A[v] = 0; return query(); } int query() { int a0, a1; seg[1].eval(a0, a1); return min(a0, a1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...