제출 #893881

#제출 시각아이디문제언어결과실행 시간메모리
893881azosiMin-max tree (BOI18_minmaxtree)C++17
29 / 100
176 ms54664 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_N = 70001; const int INF = 1e9; vector<int> g[MAX_N], tree[MAX_N]; int n, k; struct SegmentTree { typedef int (*F)(int, int); F merge; int identity; int tree[MAX_N * 4]{}, lazy[MAX_N * 4]{}; SegmentTree(F func, int identity) : merge(func), identity(identity) { for (int i = 0; i < MAX_N * 4; ++i) tree[i] = lazy[i] = identity; } void push(int node, int l, int r) { if (lazy[node] != identity) { tree[node] = merge(tree[node], lazy[node]); if (l != r) { lazy[node * 2] = merge(lazy[node * 2], lazy[node]); lazy[node * 2 + 1] = merge(lazy[node * 2 + 1], lazy[node]); } } lazy[node] = identity; } void update(int s, int e, int val, int node = 1, int l = 1, int r = n) { push(node, l, r); if (e < l || r < s) return; if (s <= l && r <= e) { lazy[node] = val; push(node, l, r); return; } int mid = (l + r) / 2; update(s, e, val, node * 2, l, mid); update(s, e, val, node * 2 + 1, mid + 1, r); tree[node] = merge(tree[node * 2], tree[node * 2 + 1]); } int query(int s, int e, int node = 1, int l = 1, int r = n) { push(node, l, r); if (e < l || r < s) return identity; if (s <= l && r <= e) return tree[node]; int mid = (l + r) / 2; return merge(query(s, e, node * 2, l, mid), query(s, e, node * 2 + 1, mid + 1, r)); } }; int _mn(int a, int b) { return min(a, b); } int _mx(int a, int b) { return max(a, b); } SegmentTree minSeg(_mn, INF); SegmentTree maxSeg(_mx, -INF); void makeTree(int here = 1, int prev = 0) { for (auto there: g[here]) { if (there == prev) continue; tree[here].push_back(there); makeTree(there, here); } } int sz[MAX_N], dep[MAX_N], par[MAX_N], top[MAX_N], in[MAX_N]; void dfs1(int here = 1) { sz[here] = 1; for (auto &there: tree[here]) { dep[there] = dep[here] + 1; par[there] = here; dfs1(there); sz[here] += sz[there]; if (sz[there] > sz[tree[here][0]]) swap(there, tree[here][0]); } } int counter; void dfs2(int here = 1) { in[here] = ++counter; for (auto there: tree[here]) { top[there] = there == tree[here][0] ? top[here] : there; dfs2(there); } } void update(int a, int b, int val, bool qType) { while (top[a] != top[b]) { if (dep[top[a]] < dep[top[b]]) swap(a, b); int st = top[a]; qType ? minSeg.update(in[st], in[a], val) : maxSeg.update(in[st], in[a], val); a = par[st]; } if (a == b) return; if (dep[a] > dep[b]) swap(a, b); qType ? minSeg.update(in[a] + 1, in[b], val) : maxSeg.update(in[a] + 1, in[b], val); } pair<int, int> query(int a, int b) { pair<int, int> ret = {INF, -INF}; while (top[a] != top[b]) { if (dep[top[a]] < dep[top[b]]) swap(a, b); int st = top[a]; ret.first = min(ret.first, minSeg.query(in[st], in[a])); ret.second = max(ret.second, maxSeg.query(in[st], in[a])); a = par[st]; } if (a == b) return ret; if (dep[a] > dep[b]) swap(a, b); ret.first = min(ret.first, minSeg.query(in[a] + 1, in[b])); ret.second = max(ret.second, maxSeg.query(in[a] + 1, in[b])); return ret; } int mn[MAX_N], mx[MAX_N], cnt[MAX_N], ans[MAX_N], ans2[MAX_N], chk[MAX_N]; vector<int> bench[MAX_N]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n; for (int i = 0; i < n - 1; ++i) { int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); } cin >> k; makeTree(); dfs1(); dfs2(); char q; int a, b; int c; vector<int> weight; map<int, int> idx; for (int i = 0; i < k; ++i) { cin >> q >> a >> b >> c; if (q == 'M') { update(a, b, c, false); } else { update(a, b, c, true); } weight.push_back(c); idx[c] = i; } for (int i = 2; i <= n; ++i) { auto [l, h] = query(i, par[i]); mn[i] = l; mx[i] = h; if (l != INF) { bench[idx[l]].push_back(i); cnt[idx[l]]++; ans2[i] = l; } if (h != -INF) { bench[idx[h]].push_back(i); cnt[idx[h]]++; ans2[i] = h; } } for (int i = 0; i <= n; ++i) { ans[i] = INF; } priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; vector<pair<int, int> > srt; for (int i = 0; i < k; ++i) { pq.emplace(cnt[i], i); srt.emplace_back(cnt[i], i); } while (!pq.empty()) { auto [count, id] = pq.top(); pq.pop(); if (cnt[id] != count || chk[id]) continue; int mxid = -1, target = 0; for (auto node: bench[id]) { if (ans[node] == INF) { int oth = idx[mn[node]] + idx[mx[node]] - id; if (mxid < cnt[oth]) { mxid = cnt[oth]; target = node; } } } ans[target] = weight[id]; int tid = idx[mn[target]] + idx[mx[target]] - id; cnt[tid]--; pq.emplace(cnt[tid], tid); chk[id] = true; cnt[id] = max(cnt[id], MAX_N); } for (int i = 2; i <= n; ++i) { cout << i << " " << par[i] << " "; if (ans[i] != INF) { cout << ans[i] << "\n"; } else { cout << ans2[i] << "\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...