Submission #680634

#TimeUsernameProblemLanguageResultExecution timeMemory
680634nutellaCats or Dogs (JOI18_catdog)C++17
0 / 100
8 ms11560 KiB
#include <bits/stdc++.h> #include "catdog.h" using namespace std; using ll = long long; int n; constexpr int N = 100001, inf = 1e9 + 7; vector<int> g[N]; int head[N], sz[N], parent[N], tin[N], T = 0, hld_sz[N], type[N]; void dfs_init(int v) { auto it = find(g[v].begin(), g[v].end(), parent[v]); if (it != g[v].end()) { g[v].erase(it); } sz[v] = 1; for (int &to: g[v]) { parent[to] = v; dfs_init(to); sz[v] += sz[to]; if (sz[to] > sz[g[v][0]]) { swap(to, g[v][0]); } } } void dfs_hld(int v) { if (head[v] == 0) { head[v] = v; } tin[v] = T++; hld_sz[head[v]] += 1; for (int &to: g[v]) { if (to == g[v][0]) { head[to] = head[v]; } dfs_hld(to); } } struct Info { array<ll, 4> dp{0, inf, inf, 0}; Info() = default; Info(array<ll, 4> d) : dp(d) {} }; Info operator+(Info a, Info b) { Info res; fill(res.dp.begin(), res.dp.end(), inf); for (int i = 0; i < 4; ++i) { for (int j = 0; j < 4; ++j) { int x = (i & 2) + (j & 1); res.dp[x] = min(res.dp[x], a.dp[i] + b.dp[j] + ((i & 1) != bool(j & 2))); } } return res; } struct SegmentTree { vector<Info> t; int n{}; void init(int m) { n = 1 << (__lg(m) + bool(m & (m - 1))); t.assign(2 * n, {}); } void modify(int i, ll x, ll y) { i += n; t[i].dp[0] += x, t[i].dp[3] += y; while (i >>= 1) { t[i] = t[i << 1] + t[i << 1 | 1]; } } }; array<ll, 2> transform(array<ll, 4> &a) { ll x = min(a[0], a[1]), y = min(a[2], a[3]); return {min(x, y + 1), min(x + 1, y)}; } SegmentTree t[N]; void update(int v, ll x, ll y) { while (v != 0) { int u = head[v]; auto was = transform(t[u].t[1].dp); t[u].modify(tin[v] - tin[u], x, y); auto now = transform(t[u].t[1].dp); v = parent[u]; x = now[0] - was[0]; y = now[1] - was[1]; } } void initialize(int N, std::vector<int> A, std::vector<int> B) { n = A.size(); for (int i = 0; i < n - 1; ++i) { g[A[i]].push_back(B[i]); g[B[i]].push_back(A[i]); } dfs_init(1); dfs_hld(1); for (int i = 1; i <= n; ++i) { if (head[i] == i) { t[i].init(hld_sz[i]); } } } int query() { auto res = t[1].t[1].dp; return *min_element(res.begin(), res.end()); } int cat(int v) { type[v] = 0; update(v, 0, N); return query(); } int dog(int v) { type[v] = 1; update(v, N, 0); return query(); } int neighbor(int v) { if (type[v] == 0) { update(v, 0, -N); } else { update(v, -N, 0); } type[v] = 2; return query(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...