Submission #848017

#TimeUsernameProblemLanguageResultExecution timeMemory
848017LeonaRagingCats or Dogs (JOI18_catdog)C++14
0 / 100
3 ms12892 KiB
#include "catdog.h" #include<bits/stdc++.h> using namespace std; #define pb push_back const int maxn = 1e5 + 4; const int INF = 1e9; int n, sz[maxn], R[maxn], B[maxn], col[maxn], par[maxn], id[maxn]; int chain[maxn], head[maxn], from[maxn], to[maxn], tin[maxn]; vector<int> adj[maxn]; struct Node { int a[2][2]; Node() { for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) a[i][j] = INF; } }; struct seg_tree { vector<Node> t; seg_tree() { t.resize(4 * maxn); } Node merge(Node L, Node R) { Node res; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int x = 0; x < 2; x++) for (int y = 0; y < 2; y++) res.a[i][j] = min(res.a[i][j], L.a[i][x] + R.a[y][j] + (x != y)); return res; } void update(int pos, int v = 1, int l = 1, int r = maxn - 1) { if (l == r) { t[v].a[0][0] = (col[id[l]] == 1 ? INF : R[id[l]]); t[v].a[1][1] = (col[id[l]] == 0 ? INF : B[id[l]]); t[v].a[0][1] = t[v].a[1][0] = INF; return; } int m = (l + r) / 2; if (pos <= m) update(pos, 2 * v, l, m); else update(pos, 2 * v + 1, m + 1, r); t[v] = merge(t[2 * v], t[2 * v + 1]); } Node get(int l, int r, int v = 1, int tl = 1, int tr = maxn - 1) { if (tl >= l && tr <= r) return t[v]; int m = (tl + tr) / 2; if (r <= m) return get(l, r, 2 * v, tl, m); else if (l > m) return get(l, r, 2 * v + 1, m + 1, tr); else return merge(get(l, r, 2 * v, tl, m), get(l, r, 2 * v + 1, m + 1, tr)); } } IT; void dfs(int u, int p) { sz[u] = 1; for (int v : adj[u]) if (v != p) { par[v] = u; dfs(v, u); sz[u] += sz[v]; } } void hld(int u) { tin[u] = ++tin[0]; id[tin[0]] = u; chain[u] = chain[0]; if (!head[chain[0]]) head[chain[0]] = u; int mx = 0; for (int v : adj[u]) if (v != par[u] && sz[v] > sz[mx]) mx = v; if (mx) hld(mx); for (int v : adj[u]) if (v != par[u] && v != mx) { chain[0]++; hld(v); } } void update(int v) { while (v) { int u = par[head[chain[v]]]; Node cur = IT.get(from[chain[v]], to[chain[v]]); if (col[u] != 1) R[u] -= min({cur.a[0][0], cur.a[0][1], cur.a[1][0] + 1, cur.a[1][1] + 1}); if (col[u] != 0) B[u] -= min({cur.a[0][0] + 1, cur.a[0][1] + 1, cur.a[1][0], cur.a[1][1]}); IT.update(tin[v]); cur = IT.get(from[chain[v]], to[chain[v]]); if (col[u] != 1) R[u] += min({cur.a[0][0], cur.a[0][1], cur.a[1][0] + 1, cur.a[1][1] + 1}); if (col[u] != 0) B[u] += min({cur.a[0][0] + 1, cur.a[0][1] + 1, cur.a[1][0], cur.a[1][1]}); v = u; } } int get() { Node cur = IT.get(from[0], to[0]); int res = INF; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) res = min(res, cur.a[i][j]); return res; } 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(1, 0); hld(1); for (int i = 0; i <= chain[0]; i++) from[i] = INF; for (int i = 1; i <= n; i++) { from[chain[i]] = min(from[chain[i]], tin[i]); to[chain[i]] = max(to[chain[i]], tin[i]); col[i] = -1; } for (int i = 1; i <= n; i++) IT.update(i); } int cat(int v) { col[v] = 0; update(v); return get(); } int dog(int v) { col[v] = 1; update(v); return get(); } int neighbor(int v) { col[v] = -1; update(v); return get(); } // int main() // { // ios::sync_with_stdio(0); // cin.tie(0); cout.tie(0); // if (fopen("Pets.INP", "r")) { // freopen("Pets.INP", "r", stdin); // freopen("Pets.OUT", "w", stdout); // } // cin >> n; // for (int i = 1, u, v; i < n; i++) { // cin >> u >> v; // adj[u].pb(v); // adj[v].pb(u); // } // dfs(1, 0); // hld(1); // for (int i = 0; i <= chain[0]; i++) // from[i] = INF; // for (int i = 1; i <= n; i++) { // from[chain[i]] = min(from[chain[i]], tin[i]); // to[chain[i]] = max(to[chain[i]], tin[i]); // col[i] = -1; // } // for (int i = 1; i <= n; i++) // IT.update(i); // int q; cin >> q; // while (q--) { // int t, u; cin >> t >> u; // if (t == 1) col[u] = 0; // if (t == 2) col[u] = 1; // if (t == 3) col[u] = -1; // update(u); // cout << get() << '\n'; // } // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...