Submission #1261112

#TimeUsernameProblemLanguageResultExecution timeMemory
1261112Bui_Quoc_CuongCats or Dogs (JOI18_catdog)C++20
100 / 100
132 ms24904 KiB
#include <bits/stdc++.h> using namespace std; template <class A, class B> bool maximize(A &a, const B b) { if (a < b) { a = b; return true; } return false; } template <class A, class B> bool minimize(A &a, const B b) { if (a > b) { a = b; return true; } return false; } #define pb push_back #define FOR(i, a, b) for(int i = a; i <= (int)b; i++) #define FORD(i, a, b) for(int i = a; i >= (int)b; i--) #define fi first #define se second #define ALL(A) A.begin(), A.end() typedef vector<int> vi; typedef pair<int, int> ii; typedef long long ll; const int N = 1e5 + 5; const int oo = 2e9 + 29032008; const ll INF = 1e18 + 29032008; int n, q; vi g[N]; int a[N]; int head[N], timedfs, heavy[N], sz[N], par[N], sz_head[N], pos[N]; void dfs_sz(int u) { sz[u] = 1; for (int &v : g[u]) if (v != par[u]) { par[v] = u; dfs_sz(v); sz[u]+= sz[v]; if (sz[v] > sz[heavy[u]]) heavy[u] = v; } } void hld(int u, int crt) { head[u] = crt; pos[u] = ++ sz_head[crt]; if (heavy[u]) hld(heavy[u], crt); for (int &v : g[u]) if (v != par[u] && v != heavy[u]) { hld(v, v); } } struct Node { int a[2][2]; Node() { a[0][0] = a[0][1] = a[1][0] = a[1][1] = N; } friend Node operator + (Node a, Node b) { Node ans; for (int st = 0; st <= 1; st++) { for (int ed = 0; ed <= 1; ed++) { ans.a[st][ed] = N; for (int x = 0; x <= 1; x++) { for (int y = 0; y <= 1; y++) { ans.a[st][ed] = min(ans.a[st][ed], a.a[st][x] + b.a[y][ed] + (x != y)); } } } } return ans; } }; struct SegmentTree { vector <Node> st; void init(int n) { st.resize(4 * n + 2); } void build(int id, int l, int r) { if (l == r) { st[id].a[0][0] = st[id].a[1][1] = 0; st[id].a[0][1] = st[id].a[1][0] = N; return; } int mid = l + r >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); st[id] = st[id << 1] + st[id << 1 | 1]; } void update(int id, int l, int r, int pos, int delta_cat, int delta_dog) { if (pos < l || pos > r) return; if (l == r) { st[id].a[0][0]+= delta_cat; st[id].a[1][1]+= delta_dog; return; } int mid = l + r >> 1; update(id << 1, l, mid, pos, delta_cat, delta_dog); update(id << 1 | 1, mid + 1, r, pos, delta_cat, delta_dog); st[id] = st[id << 1] + st[id << 1 | 1]; } Node get() { return st[1]; } } ST[N]; void update(int u, int cat, int dog) { while (u > 0) { Node cur = ST[head[u]].get(); int oldcat = min({cur.a[0][0], cur.a[0][1], cur.a[1][0] + 1, cur.a[1][1] + 1}); int olddog = min({cur.a[1][1], cur.a[1][0], cur.a[0][1] + 1, cur.a[0][0] + 1}); ST[head[u]].update(1, 1, sz_head[head[u]], pos[u], cat, dog); cur = ST[head[u]].get(); int newcat = min({cur.a[0][0], cur.a[0][1], cur.a[1][0] + 1, cur.a[1][1] + 1}); int newdog = min({cur.a[1][1], cur.a[1][0], cur.a[0][1] + 1, cur.a[0][0] + 1}); cat = newcat - oldcat; dog = newdog - olddog; /// cout << u << " " << cat << " " << dog << "\n"; u = par[head[u]]; } } int getAns() { Node res = ST[1].get(); return min({res.a[0][0], res.a[1][1], res.a[0][1], res.a[1][0]}); } int cat(int u) { a[u] = 1; update(u, 0, N); return getAns(); } int dog(int u) { a[u] = 2; update(u, N, 0); return getAns(); } int neighbor(int u) { if (a[u] == 1) { update(u, 0, - N); } else { update(u, - N, 0); } a[u] = 0; return getAns(); } void solve() { while (q--) { int type, u; cin >> type >> u; if (type == 1) cout << cat(u); if (type == 2) cout << dog(u); if (type == 3) cout << neighbor(u); cout << "\n"; } } void initialize(int _N, vector<int> A, vector<int> B){ n = _N; for(int i = 0; i < n - 1; ++i){ int u = A[i], v = B[i]; g[u].emplace_back(v); g[v].emplace_back(u); } dfs_sz(1); hld(1, 1); for (int i = 1; i <= n; i++) if (head[i] == i) { ST[i].init(sz_head[i]); ST[i].build(1, 1, sz_head[i]); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...