Submission #527396

#TimeUsernameProblemLanguageResultExecution timeMemory
527396QingyuCats or Dogs (JOI18_catdog)C++17
100 / 100
802 ms33724 KiB
#include "catdog.h" #include <bits/stdc++.h> const int N = 1e5 + 50; int n, fa[N], top[N], dep[N], g[N][2], siz[N], son[N], dfn[N], dp[N][2], tot, tail[N], delta[N][2], id[N]; std::vector<int> G[N]; inline int lc(int o) { return o << 1; } inline int rc(int o) { return o << 1 | 1; } struct matrix_t { int M[2][2], n, m; matrix_t(int n = 0, int m = 0) : n(n), m(m) { memset(M, 0x3f, sizeof M); } void set(int g0, int g1) { M[0][0] = g0, M[1][0] = g0 + 1; M[0][1] = g1 + 1, M[1][1] = g1; } } gm[N], tr[N << 2]; matrix_t operator*(const matrix_t &lhs, const matrix_t &rhs) { matrix_t res; for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) for (int k = 0; k < 2; ++k) res.M[i][j] = std::min(res.M[i][j], lhs.M[i][k] + rhs.M[k][j]); return res; } void dfs(int x, int f, int d) { fa[x] = f, dep[x] = d, siz[x] = 1; int mx = -1; dp[x][0] = dp[x][1] = 0; for (int y : G[x]) if (y != f) { dfs(y, x, d + 1); siz[x] += siz[y]; if (siz[y] > mx) { mx = siz[y]; son[x] = y; } dp[x][0] = std::min(dp[y][0], dp[y][1] + 1); dp[x][1] = std::min(dp[y][1], dp[y][0] + 1); } } void dfs2(int x, int topf) { dfn[x] = ++tot; id[tot] = x; top[x] = topf; tail[topf] = x; g[x][0] = g[x][1] = 0; if (son[x]) { dfs2(son[x], topf); for (int y : G[x]) if (y != fa[x] && y != son[x]) { dfs2(y, y); g[x][0] += std::min(dp[y][0], dp[y][1] + 1); g[x][1] += std::min(dp[y][1], dp[y][0] + 1); } } gm[x].set(g[x][0], g[x][1]); } void push_up(int o) { tr[o] = tr[rc(o)] * tr[lc(o)]; } void build(int o, int l, int r) { if (l == r) { tr[o] = gm[id[l]]; } else { const int mid = l + r >> 1; build(lc(o), l, mid); build(rc(o), mid + 1, r); push_up(o); } } matrix_t query(int o, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return tr[o]; const int mid = l + r >> 1; if (qr <= mid) return query(lc(o), l, mid, ql, qr); if (ql > mid) return query(rc(o), mid + 1, r, ql, qr); return query(rc(o), mid + 1, r, ql, qr) * query(lc(o), l, mid, ql, qr); } void modify(int o, int l, int r, int p) { if (l == r) { tr[o] = gm[id[l]]; } else { const int mid = l + r >> 1; if (p <= mid) modify(lc(o), l, mid, p); else modify(rc(o), mid + 1, r, p); push_up(o); } } void initialize(int N, std::vector<int> A, std::vector<int> B) { n = N; for (int i = 0; i < A.size(); ++i) { G[A[i]].push_back(B[i]); G[B[i]].push_back(A[i]); } dfs(1, 0, 1); dfs2(1, 1); assert(tot == N); build(1, 1, N); } void cancel(int v) { g[v][0] -= delta[v][0]; g[v][1] -= delta[v][1]; } void update(int v) { g[v][0] += delta[v][0]; g[v][1] += delta[v][1]; gm[v].set(g[v][0], g[v][1]); } void travel(int x) { while (x) { matrix_t old = query(1, 1, n, dfn[top[x]], dfn[tail[top[x]]]); modify(1, 1, n, dfn[x]); matrix_t now = query(1, 1, n, dfn[top[x]], dfn[tail[top[x]]]); x = fa[top[x]]; if (!x) break; { int f0 = std::min(old.M[0][0], old.M[1][0]); int f1 = std::min(old.M[0][1], old.M[1][1]); g[x][0] -= std::min(f0, f1 + 1); g[x][1] -= std::min(f1, f0 + 1); } { int f0 = std::min(now.M[0][0], now.M[1][0]); int f1 = std::min(now.M[0][1], now.M[1][1]); g[x][0] += std::min(f0, f1 + 1); g[x][1] += std::min(f1, f0 + 1); } gm[x].set(g[x][0], g[x][1]); } } int getans() { auto M = query(1, 1, n, dfn[1], dfn[tail[top[1]]]); int ans = std::min(M.M[0][0], M.M[0][1]); ans = std::min(ans, M.M[1][0]); ans = std::min(ans, M.M[1][1]); return ans; } int cat(int v) { cancel(v); delta[v][0] = 0, delta[v][1] = 0x3f3f3f3f; update(v); travel(v); return getans(); } int dog(int v) { cancel(v); delta[v][0] = 0x3f3f3f3f, delta[v][1] = 0; update(v); travel(v); return getans(); } int neighbor(int v) { cancel(v); delta[v][0] = delta[v][1] = 0; update(v); travel(v); return getans(); }

Compilation message (stderr)

catdog.cpp: In function 'void build(int, int, int)':
catdog.cpp:75:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |   const int mid = l + r >> 1;
      |                   ~~^~~
catdog.cpp: In function 'matrix_t query(int, int, int, int, int)':
catdog.cpp:85:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |  const int mid = l + r >> 1;
      |                  ~~^~~
catdog.cpp: In function 'void modify(int, int, int, int)':
catdog.cpp:96:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |   const int mid = l + r >> 1;
      |                   ~~^~~
catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:105:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |  for (int i = 0; i < A.size(); ++i) {
      |                  ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...