제출 #1258711

#제출 시각아이디문제언어결과실행 시간메모리
1258711biankTree (IOI24_tree)C++20
17 / 100
129 ms42116 KiB
#include "tree.h" #include <bits/stdc++.h> #define forsn(i, s, n) for (int i = int(s); i < int(n); i++) #define forn(i, n) forsn(i, 0, n) #define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--) #define dforn(i, n) dforsn(i, 0, n) #define sz(x) int(x.size()) #define all(x) begin(x), end(x) #define pb push_back #define eb emplace_back #define fst first #define snd second using namespace std; using vi = vector<int>; using ii = pair<int, int>; using ll = long long; const int INF = 1e9 + 20; template<typename T, T (*op)(const T&, const T&), T (*id)()> struct SegTree { int n; vector<T> st; SegTree(int _n = 0) : n(_n), st(2 * n, id()) {}; void init(vector<T> v) { assert(sz(v) == n); forn(i, n) st[i + n] = v[i]; dforsn(i, 1, n) st[i] = op(st[2 * i], st[2 * i + 1]); } T query(int l, int r) { T lans = id(), rans = id(); for (l += n, r += n; l < r; l /= 2, r /= 2) { if (l & 1) lans = op(lans, st[l++]); if (r & 1) rans = op(st[--r], rans); } return op(lans, rans); } void updateSet(int p, T v) { st[p += n] = v; while (p /= 2) st[p] = op(st[2 * p], st[2 * p + 1]); } void updateAdd(int p, T v) { p += n; st[p] = op(st[p], v); while (p /= 2) st[p] = op(st[2 * p], st[2 * p + 1]); } }; const int MAX_N = 2e5 + 9; int in[MAX_N], out[MAX_N]; int w[MAX_N], t; bool done[MAX_N]; vi adj[MAX_N]; int n; bool only0and1; void dfs0(int u) { in[u] = t++; for (int v : adj[u]) dfs0(v); out[u] = t; } ii minOp(const ii &a, const ii &b) { return min(a, b); } ii minNeutr() { return ii{INF, INF}; } template<typename T> T sumOp(const T &a, const T &b) { return a + b; } template<typename T> T sumNeutr() { return 0; } SegTree<ii, minOp, minNeutr> mini; SegTree<int, sumOp, sumNeutr> sum; vector<ii> terms; ll sumOfLeafs; vector<ll> prefA, prefB; void solve(int u, int delta) { while (true) { auto [minW, v] = mini.query(in[u], out[u]); if (minW == INF) { //leaf sum.updateSet(in[v], 0); done[v] = true; return; } int leafs = sum.query(in[u], out[u]); terms.eb(leafs, minW - delta); delta = minW; for (int c : adj[v]) { if (!done[c]) solve(c, delta); } sum.updateSet(in[v], 1); mini.updateSet(in[v], ii{INF, -1}); } } void init(vi P, vi W) { n = sz(P); forsn(i, 1, n) adj[P[i]].pb(i); forn(i, n) w[i] = W[i]; t = 0; dfs0(0); vector<ii> v(n); vi c(n); mini = SegTree<ii, minOp, minNeutr>(n); sum = SegTree<int, sumOp, sumNeutr>(n); forn(u, n) { if (out[u] - in[u] == 1) { v[in[u]] = {INF, u}, c[in[u]] = 1; sumOfLeafs += w[u]; } else { v[in[u]] = {w[u], u}, c[in[u]] = 0; } } mini.init(v), sum.init(c); solve(0, 0); sort(all(terms)); prefA.resize(sz(terms) + 1); prefB.resize(sz(terms) + 1); prefA[0] = 0, prefB[0] = 0; forn(i, sz(terms)) { prefA[i + 1] = prefA[i] + terms[i].fst * terms[i].snd; prefB[i + 1] = prefB[i] - terms[i].snd; } } ll query(int L, int R) { int lo = -1, hi = sz(terms); while (hi - lo > 1) { int mid = (lo + hi) / 2; if (1LL * terms[mid].fst * L - R > 0) hi = mid; else lo = mid; } return sumOfLeafs * L + (prefA.back() - prefA[hi]) * L + (prefB.back() - prefB[hi]) * R; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...