Submission #1049154

#TimeUsernameProblemLanguageResultExecution timeMemory
1049154fryingducConstruction of Highway (JOI18_construction)C++17
100 / 100
1305 ms32804 KiB
#include "bits/stdc++.h" using namespace std; const int maxn = 1e5 + 5; const int lg = 18; int n, a[maxn]; vector<int> g[maxn]; int pos[maxn], cur_pos, head[maxn]; int up[maxn][lg + 1]; int sz[maxn], par[maxn]; int h[maxn]; int eu[maxn], ev[maxn]; int rev[maxn]; pair<int, int> tree[maxn * 4]; int lazy[maxn * 4]; pair<int, int> operator+(const pair<int, int> &a, const pair<int, int> &b) { return {max(a.first, b.first), min(a.second, b.second)}; } struct fenwick_tree { #define gb(x) (x) & (-x) int n; vector<long long> bit; fenwick_tree() {} fenwick_tree(int n) : n(n), bit(n + 5, 0) {} void update(int x, long long val) { for(int i = x; i <= n; i += gb(i)) bit[i] += val; } long long get(int x) { int ans = 0; for(int i = x; i > 0; i -= gb(i)) ans += bit[i]; return ans; } } fen; struct segment_tree { int n; segment_tree() {} segment_tree(int n) : n(n) { for(int i = 1; i <= n * 4; ++i) { tree[i] = {0, 2e9}; } } void build(int ind, int l, int r) { if(l == r) { tree[ind] = {a[rev[l]], a[rev[l]]}; return; } int mid = (l + r) / 2; build(ind * 2, l, mid); build(ind * 2 + 1, mid + 1, r); tree[ind] = tree[ind * 2] + tree[ind * 2 + 1]; } void down(int ind, int l, int r) { tree[ind].first = tree[ind].second = lazy[ind]; if(l != r) { lazy[ind * 2] = lazy[ind * 2 + 1] = lazy[ind]; } lazy[ind] = 0; } void update(int ind, int l, int r, int x, int y, int val) { if(lazy[ind]) down(ind, l, r); if(l > y || r < x) return; if(x <= l and r <= y) { lazy[ind] = val; down(ind, l, r); return; } int mid = (l + r) / 2; update(ind * 2, l, mid, x, y, val); update(ind * 2 + 1, mid + 1, r, x, y, val); tree[ind] = tree[ind * 2] + tree[ind * 2 + 1]; } pair<int, int> get(int ind, int l, int r, int x, int y) { if(lazy[ind]) down(ind, l, r); if(l > y || r < x) return {0, 2e9}; if(x <= l and r <= y) return tree[ind]; int mid = (l + r) / 2; return get(ind * 2, l, mid, x, y) + get(ind * 2 + 1, mid + 1, r, x, y); } void update(int x, int y, int val) { update(1, 1, n, x, y, val); } pair<int, int> get(int x, int y) { return get(1, 1, n, x, y); } } st; void pre_dfs(int u, int prev) { sz[u] = 1; for(auto v:g[u]) { if(v == prev) continue; par[v] = u; h[v] = h[u] + 1; up[v][0] = u; pre_dfs(v, u); sz[u] += sz[v]; } } void hld(int u, int prev) { if(!head[u]) { head[u] = u; } pos[u] = ++cur_pos; rev[cur_pos] = u; int big_child = -1; for(auto v:g[u]) { if(v == prev) continue; if(big_child == -1 || sz[big_child] < sz[v]) big_child = v; } if(big_child != -1) { head[big_child] = head[u]; hld(big_child, u); } for(auto v:g[u]) { if(v == prev || v == big_child) continue; hld(v, u); } } void update(int u, int v, int val) { while(head[u] != head[v]) { if(h[u] > h[v]) swap(u, v); st.update(pos[head[v]], pos[v], val); v = par[head[v]]; } if(h[u] > h[v]) swap(u, v); st.update(pos[u], pos[v], val); } pair<int, int> get(int u, int v) { pair<int, int> ans = {0, 2e9}; while(head[u] != head[v]) { if(h[u] > h[v]) swap(u, v); ans = ans + st.get(pos[head[v]], pos[v]); v = par[head[v]]; } if(h[u] > h[v]) swap(u, v); ans = ans + st.get(pos[u], pos[v]); return ans; } void solve() { cin >> n; vector<int> cpr; for(int i = 1; i <= n; ++i) { cin >> a[i]; cpr.push_back(a[i]); } sort(cpr.begin(), cpr.end()); cpr.erase(unique(cpr.begin(), cpr.end()), cpr.end()); for(int i = 1; i <= n; ++i) { a[i] = lower_bound(cpr.begin(), cpr.end(), a[i]) - cpr.begin() + 1; } fen = fenwick_tree((int)cpr.size() + 5); for(int i = 1; i < n; ++i) { int u, v; cin >> u >> v; eu[i] = u, ev[i] = v; g[u].push_back(v); // g[v].push_back(u); } pre_dfs(1, 0); for(int i = 1; i <= lg; ++i) { for(int u = 1; u <= n; ++u) { up[u][i] = up[up[u][i - 1]][i - 1]; } } hld(1, 0); st = segment_tree(n); st.build(1, 1, n); for(int t = 1; t < n; ++t) { int u = eu[t], v = ev[t]; vector<pair<int, int>> vec; int ver = u; while(ver) { vec.push_back({st.get(pos[ver], pos[ver]).first, 1}); for(int i = lg; i >= 0; --i) { if(!up[ver][i]) continue; int nxt = up[ver][i]; pair<int, int> dit = get(ver, nxt); if(dit.first == dit.second) { ver = nxt; vec.back().second += (1 << i); } } ver = par[ver]; } long long ans = 0; for(int i = 0; i < (int)vec.size(); ++i) { ans += vec[i].second * fen.get(vec[i].first - 1); fen.update(vec[i].first, vec[i].second); } for(auto i:vec) { fen.update(i.first, -i.second); } cout << ans << '\n'; update(1, u, st.get(pos[v], pos[v]).first); } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...