Submission #894006

#TimeUsernameProblemLanguageResultExecution timeMemory
894006azosiMin-max tree (BOI18_minmaxtree)C++17
29 / 100
184 ms30492 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_N = 70070; const int INF = 1e9 + 100; int n, q; 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 = MAX_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 = MAX_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), maxSeg(_mx, -INF); int in[MAX_N], dep[MAX_N], par[MAX_N], top[MAX_N], sz[MAX_N], chk[MAX_N]; int pv; vector<int> g[MAX_N], inp[MAX_N]; void dfs(int v = 1) { chk[v] = 1; for (auto i: inp[v]) { if (chk[i]) continue; chk[i] = 1; g[v].push_back(i); dfs(i); } } void dfs1(int v = 1) { sz[v] = 1; for (auto &i: g[v]) { dep[i] = dep[v] + 1; par[i] = v; dfs1(i); sz[v] += sz[i]; if (sz[i] > sz[g[v][0]]) swap(i, g[v][0]); } } void dfs2(int v = 1) { in[v] = ++pv; for (auto i: g[v]) { top[i] = i == g[v][0] ? top[v] : i; dfs2(i); } } void update(int a, int b, int op, int k) { while (top[a] != top[b]) { if (dep[top[a]] < dep[top[b]]) swap(a, b); int st = top[a]; if (op == 1) minSeg.update(in[st], in[a], k); else maxSeg.update(in[st], in[a], k); a = par[st]; } if (dep[a] > dep[b]) swap(a, b); if (op == 1) minSeg.update(in[a] + 1, in[b], k); else maxSeg.update(in[a] + 1, in[b], k); } int maxi[MAX_N], mini[MAX_N], cnt[MAX_N], ans[MAX_N], vis[MAX_N]; struct Query { int s, e, x, mx; }; vector<Query> qry; map<int, int> mp; vector<int> bench[MAX_N]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; top[1] = 1; for (int i = 2; i <= n; i++) { int s, e; cin >> s >> e; inp[s].push_back(e); inp[e].push_back(s); } dfs(); dfs1(); dfs2(); cin >> q; for (int i = 0; i < q; i++) { char op; int a, b, c; cin >> op >> a >> b >> c; if (op == 'm') update(a, b, 2, c); else update(a, b, 1, c); qry.push_back({a, b, c, op == 'M'}); } for (int i = 0; i < q; i++) { mp[qry[i].x] = i; } for (int i = 2; i <= n; i++) { int mx = maxSeg.query(in[i], in[i]); int mn = minSeg.query(in[i], in[i]); if (mx != -INF) { maxi[i] = mp[mx]; bench[maxi[i]].push_back(i); } else maxi[i] = -1; if (mn != INF) { mini[i] = mp[mn]; bench[mini[i]].push_back(i); } else mini[i] = -1; } memset(chk, 0, sizeof chk); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; for (int i = 0; i < q; i++) { cnt[i] = bench[i].size(); pq.push({bench[i].size(), i}); } while (!pq.empty()) { auto [x, y] = pq.top(); pq.pop(); if (x != cnt[y]) continue; vis[y] = true; for (int i: bench[y]) { if (chk[i]) continue; ans[i] = qry[y].x; chk[i] = true; if (qry[y].mx) { if (maxi[i] != -INF) { cnt[mp[maxi[i]]]--; if (!vis[mp[maxi[i]]]) pq.push({cnt[mp[maxi[i]]], mp[maxi[i]]}); } } else { if (mini[i] != INF) { cnt[mp[mini[i]]]--; if (!vis[mp[mini[i]]]) pq.push({cnt[mp[mini[i]]], mp[mini[i]]}); } } break; } } for (int i = 2; i <= n; i++) { if (!chk[i]) ans[i] = maxi[i]; } for (int i = 2; i <= n; i++) { cout << par[i] << " " << i << " " << ans[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...