Submission #1262319

#TimeUsernameProblemLanguageResultExecution timeMemory
1262319son2008Cats or Dogs (JOI18_catdog)C++20
0 / 100
9 ms19008 KiB
#include <bits/stdc++.h> using namespace std; #define ii pair<int, int> #define fi first #define se second // #define int long long #define ll long long #define ld double #define mp make_pair #define lg2 30 #define iii pair<int, ii> #define iiii pair<ii, ii> #define base 29 #define eps 1e-8 #define MASK(i) (1LL << (i)) #define BIT(S, i) (((S) >> (i)) & 1) int dx[] = {0LL, 0LL, 1, -1, 1, 1, -1, -1}; int dy[] = {1, -1, 0LL, 0LL, 1, -1, 1, -1}; const int maxn = 4e5 + 5; const int mod = 1e9 + 7; int n, dp[maxn][3], tt[maxn], sz[maxn], head[maxn], pos[maxn], siz[maxn], par[maxn]; vector<int> a[maxn]; void prepare(int u, int cha) { sz[u] = 1; for (int v : a[u]) { if (v == cha) continue; par[v] = u; sz[u] += sz[v]; prepare(v, u); } } void hld(int u, int dau, int cha) { cout<<u<<" "<<dau<<'\n'; head[u] = dau; pos[u] = ++siz[dau]; int bigchild = 0; for (int v : a[u]) { if (v == cha) continue; if (sz[bigchild] < sz[v]) { bigchild = v; } } if (bigchild) hld(bigchild, dau, u); for (int v : a[u]) { if (v != bigchild && v != cha) { hld(v, v, u); } } } struct node { int x[2][2]; node() { for (int i = 0; i <= 1; i++) { for (int j = 0; j <= 1; j++) { x[i][j] = n; } } } }; struct segmentree { vector<node> tree; void init(int _n) { tree.resize(4 * n + 5); } node Merge(node &a, node &b) { node ans; for (int i = 0; i <= 1; i++) { for (int j = 0; j <= 1; j++) { for (int x = 0; x <= 1; x++) { for (int y = 0; y <= 1; y++) { ans.x[i][y] = min(ans.x[i][y], a.x[i][j] + b.x[x][y] + (j != x)); } } } } return ans; } void build(int id, int l, int r) { if (l == r) { tree[id].x[1][1] = tree[id].x[0][0] = 0; return ; } int mid = (l + r) / 2; build(id * 2, l, mid); build(id * 2 + 1, mid + 1, r); tree[id] = Merge(tree[id * 2], tree[id * 2 + 1]); } void update(int id, int l, int r, int i, int cat, int dog) { if (l == r) { tree[id].x[0][0] += cat; tree[id].x[1][1] += dog; return; } int mid = (l + r) / 2; if (i <= mid) update(id * 2, l, mid, i, cat, dog); else update(id * 2 + 1, mid + 1, r, i, cat, dog); tree[id] = Merge(tree[id * 2], tree[id * 2 + 1]); } node get() { return tree[1]; } } st[maxn]; void update(int u, int cat, int dog) { while (u) { node trc = st[head[u]].get(); int trc_cat = min({trc.x[0][0], trc.x[0][1], trc.x[1][0] + 1, trc.x[1][1] + 1}); int trc_dog = min({trc.x[1][1], trc.x[1][0], trc.x[0][1] + 1, trc.x[0][0] + 1}); st[head[u]].update(1, 1, siz[head[u]], pos[u], cat, dog); trc = st[head[u]].get(); int ht_cat = min({trc.x[0][0], trc.x[0][1], trc.x[1][0] + 1, trc.x[1][1] + 1}); int ht_dog = min({trc.x[1][1], trc.x[1][0], trc.x[0][1] + 1, trc.x[0][0] + 1}); cat = ht_cat - trc_cat; dog = ht_dog - trc_dog; u = par[head[u]]; } } int getans() { return min({st[1].tree[1].x[0][1], st[1].tree[1].x[1][0], st[1].tree[1].x[1][1], st[1].tree[1].x[0][0]}); } int cat(int v) { tt[v] = 1; update(v, 0, n); return getans(); } int dog(int v) { tt[v] = 2; update(v, n, 0); return getans(); } int neighbor(int v) { if (tt[v] == 1) { update(v, 0, -n); } else update(v, -n, 0); tt[v] = 0; return getans(); } void initialize(int N, vector<int> A, vector<int> B) { n = N; for (int i = 0; i < n - 1; i++) { a[A[i]].push_back(B[i]); a[B[i]].push_back(A[i]); } prepare(1, -1); hld(1, 1, -1); for (int i = 1; i <= n; i++) { if (head[i] == i) { st[i].init(siz[i]); st[i].build(1, 1, siz[i]); } } } /*signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define task "task" if (fopen(task ".inp", "r")) { freopen(task ".inp", "r", stdin); freopen(task ".out", "w", stdout); } initialize(3, {1, 2}, {2, 3}); cout << cat(1) << " "; cout << cat(3) << " "; cout << dog(2) << " "; cout << neighbor(2); cerr << endl << "TIME : " << clock() * 0.001 << "s" << endl; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...