Submission #800289

#TimeUsernameProblemLanguageResultExecution timeMemory
800289MilosMilutinovicCats or Dogs (JOI18_catdog)C++14
100 / 100
433 ms25784 KiB
#include "catdog.h" #include <bits/stdc++.h> using namespace std; const int MAX = (int) 1e5; int n, sz[MAX], pr[MAX], hd[MAX]; int from[MAX], to[MAX], col[MAX]; int ver[MAX], id[MAX], rt[MAX]; int dp_a[MAX], dp_b[MAX], cnt; vector<int> g[MAX]; struct node { int a[2][2]; node() {} node(int v) { for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { a[i][j] = v; } } } }; node st[8 * MAX]; void dfs_hld(int v, int p) { sz[v] = 1; hd[v] = -1; pr[v] = p; for (int u : g[v]) { if (u == p) { continue; } dfs_hld(u, v); sz[v] += sz[u]; if (hd[v] == -1 || sz[u] > sz[hd[v]]) { hd[v] = u; } } } void dfs(int v, int p) { if (hd[v] != -1) { rt[hd[v]] = rt[v]; id[hd[v]] = cnt++; dfs(hd[v], v); } for (int u : g[v]) { if (u == p || u == hd[v]) { continue; } id[u] = cnt++; rt[u] = u; dfs(u, v); } } const int inf = (int) 1e9; node f(node l, node r) { node res(inf); for (int xl = 0; xl < 2; xl++) { for (int yl = 0; yl < 2; yl++) { for (int xr = 0; xr < 2; xr++) { for (int yr = 0; yr < 2; yr++) { res.a[xl][yr] = min(res.a[xl][yr], l.a[xl][yl] + r.a[xr][yr] + (yl != xr ? 1 : 0)); } } } } return res; }; void pull(int v) { st[v] = f(st[v * 2], st[v * 2 + 1]); } void Build(int v, int l, int r) { if (l == r) { st[v].a[0][0] = dp_a[ver[l]]; st[v].a[0][1] = inf; st[v].a[1][0] = inf; st[v].a[1][1] = dp_b[ver[l]]; return; } int mid = l + r >> 1; Build(v * 2, l, mid); Build(v * 2 + 1, mid + 1, r); pull(v); } void Modify(int v, int l, int r, int i) { if (l == r) { st[v].a[0][0] = (col[ver[l]] != 1 ? dp_a[ver[l]] : inf); st[v].a[0][1] = inf; st[v].a[1][0] = inf; st[v].a[1][1] = (col[ver[l]] != 0 ? dp_b[ver[l]] : inf); return; } int mid = l + r >> 1; if (i <= mid) { Modify(v * 2, l, mid, i); } else { Modify(v * 2 + 1, mid + 1, r, i); } pull(v); } node Query(int v, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) { return st[v]; } int mid = l + r >> 1; if (qr <= mid) { return Query(v * 2, l, mid, ql, qr); } else if (ql > mid) { return Query(v * 2 + 1, mid + 1, r, ql, qr); } else { return f(Query(v * 2, l, mid, ql, qr), Query(v * 2 + 1, mid + 1, r, ql, qr)); } } void Update(int v) { while (true) { if (rt[v] != 0) { int x = pr[rt[v]]; int y = rt[v]; node nd = Query(1, 0, n - 1, from[y], to[y]); { dp_a[x] -= min({nd.a[0][0], nd.a[0][1], nd.a[1][0] + 1, nd.a[1][1] + 1}); dp_b[x] -= min({nd.a[1][0], nd.a[1][1], nd.a[0][0] + 1, nd.a[0][1] + 1}); } } Modify(1, 0, n - 1, id[v]); if (rt[v] != 0) { int x = pr[rt[v]]; int y = rt[v]; node nd = Query(1, 0, n - 1, from[y], to[y]); { dp_a[x] += min({nd.a[0][0], nd.a[0][1], nd.a[1][0] + 1, nd.a[1][1] + 1}); dp_b[x] += min({nd.a[1][0], nd.a[1][1], nd.a[0][0] + 1, nd.a[0][1] + 1}); } v = x; } else { return; } } } void initialize(int n, vector<int> x, vector<int> y) { ::n = n; for (int i = 0; i < n - 1; i++) { --x[i]; --y[i]; g[x[i]].push_back(y[i]); g[y[i]].push_back(x[i]); } for (int i = 0; i < n; i++) { col[i] = -1; } dfs_hld(0, -1); id[0] = cnt++; dfs(0, -1); for (int i = 0; i < n; i++) { ver[id[i]] = i; } Build(1, 0, n - 1); for (int i = 0; i < n; i++) { from[i] = n; to[i] = 0; } for (int i = 0; i < n; i++) { from[rt[i]] = min(from[rt[i]], id[i]); to[rt[i]] = max(to[rt[i]], id[i]); } vector<int> order(n); iota(order.begin(), order.end(), 0); sort(order.begin(), order.end(), [&](int i, int j) { return id[i] > id[j]; }); for (int i : order) { for (int j : g[i]) { if (j == pr[i] || hd[i] == j) { continue; } node nd = Query(1, 0, n - 1, from[j], to[j]); dp_a[i] += min({nd.a[0][0], nd.a[0][1], nd.a[1][0] + 1, nd.a[1][1] + 1}); dp_b[i] += min({nd.a[1][0], nd.a[1][1], nd.a[0][0] + 1, nd.a[0][1] + 1}); } Modify(1, 0, n - 1, id[i]); } } int solve() { node nd = Query(1, 0, n - 1, from[0], to[0]); int res = inf; for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { res = min(res, nd.a[i][j]); } } return res; } int cat(int v) { --v; col[v] = 0; Update(v); return solve(); } int dog(int v) { --v; col[v] = 1; Update(v); return solve(); } int neighbor(int v) { --v; col[v] = -1; Update(v); return solve(); }

Compilation message (stderr)

catdog.cpp: In function 'void Build(int, int, int)':
catdog.cpp:89:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |   int mid = l + r >> 1;
      |             ~~^~~
catdog.cpp: In function 'void Modify(int, int, int, int)':
catdog.cpp:103:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |   int mid = l + r >> 1;
      |             ~~^~~
catdog.cpp: In function 'node Query(int, int, int, int, int)':
catdog.cpp:116:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  116 |   int mid = l + r >> 1;
      |             ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...