제출 #570485

#제출 시각아이디문제언어결과실행 시간메모리
570485grt도로 폐쇄 (APIO21_roads)C++17
100 / 100
345 ms51172 KiB
#include <bits/stdc++.h> #define PB push_back #define ST first #define ND second //#pragma GCC optimize ("O3") //#pragma GCC target("tune=native") //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //using namespace __gnu_pbds; //typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; using namespace std; using ll = long long; using pi = pair<int, int>; using vi = vector<int>; mt19937 rng(1190310); const int nax = 100 * 1000 + 10, INF = 1e9; int n, k; set<pi>G[nax]; ll dp[nax][2]; vi ord[nax]; bool vis[nax]; int cnt[nax]; ll h[nax]; int nxt; struct Node { int pri = rng() % INF, val, sz = 1; ll sum; Node *c[2]; }; using pt = Node*; Node T[2 * nax]; pt roots[nax]; int getsz(pt x) { return (x == NULL ? 0 : x->sz); } ll getsum(pt x) { return (x == NULL ? 0 : x->sum); } pt recalc(pt x) { x->sz = getsz(x->c[0]) + getsz(x->c[1]) + 1; x->sum = getsum(x->c[0]) + getsum(x->c[1]) + x->val; return x; } pair<pt, pt>split(pt t, int kk) { if(!t) return {t, t}; if(getsz(t->c[0]) >= kk) { auto p = split(t->c[0], kk); t->c[0] = p.ND; return {p.ST, recalc(t)}; } else { auto p = split(t->c[1], kk - getsz(t->c[0]) - 1); t->c[1] = p.ST; return {recalc(t), p.ND}; } } pair<pt, pt>split_val(pt t, int vs) { if(!t) return {t, t}; if(t->val >= vs) { auto p = split_val(t->c[1], vs); t->c[1] = p.ST; return {recalc(t), p.ND}; } else { auto p = split_val(t->c[0], vs); t->c[0] = p.ND; return {p.ST, recalc(t)}; } } pt merge(pt a, pt b) { if(!a || !b) return a ? a : b; if(a->pri > b->pri) { auto t = merge(a->c[1], b); a->c[1] = t; return recalc(a); } else { auto t = merge(a, b->c[0]); b->c[0] = t; return recalc(b); } } void traverse(pt t) { if(!t) return; traverse(t->c[0]); cout << t->val << " "; traverse(t->c[1]); } void dfs(int x) { ll sum = 0; vis[x] = true; vector<ll>dx = {}; for(auto [nbh, w] : G[x]) if(!vis[nbh]) { dfs(nbh); sum += dp[nbh][0]; if(-dp[nbh][0] + dp[nbh][1] + w > 0) dx.PB(-dp[nbh][0] + dp[nbh][1] + w); } sum -= h[x]; sort(dx.rbegin(), dx.rend()); dp[x][0] = dp[x][1] = sum; int total = 0, i; pt lft = NULL; for(i = 0; i < (int)dx.size() && total < k - 1; ++i) { auto p = split_val(roots[x], dx[i]); int rem = (k - 1) - total; if(getsz(p.ST) >= rem) { auto p2 = split(p.ST, rem); dp[x][1] += getsum(p2.ST); dp[x][0] += getsum(p2.ST); total += getsz(p2.ST); lft = merge(lft, p2.ST); roots[x] = merge(p2.ND, p.ND); break; } dp[x][1] += getsum(p.ST); dp[x][0] += getsum(p.ST); total += getsz(p.ST); lft = merge(lft, p.ST); roots[x] = p.ND; //cerr << "PRZED: " << getsum(p.ST) << " " << getsz(p.ST) << " " << dx[i] << "\n"; dp[x][1] += dx[i]; dp[x][0] += dx[i]; total++; } if(total < (k-1)) { int rem = (k-1) - total; //cerr << "REM: " << rem << "\n"; auto p = split(roots[x], rem); total += getsz(p.ST); dp[x][1] += getsum(p.ST); dp[x][0] += getsum(p.ST); lft = merge(lft, p.ST); roots[x] = p.ND; } auto p = split(roots[x], 1); if(i < (int)dx.size()) { dp[x][0] += max(dx[i], getsum(p.ST)); } else { dp[x][0] += getsum(p.ST); } roots[x] = merge(p.ST, p.ND); roots[x] = merge(lft, roots[x]); //cerr << "DP: " << x << " -> " << dp[x][0] << " " << dp[x][1] << "\n"; //cout << "VALS: "; //traverse(roots[x]); //cout << "\n"; } vector<ll> minimum_closure_costs(int N, vi U, vi V, vi W) { n = N; ll sum = 0; for(int i = 0; i < n - 1; ++i) { G[U[i]].insert({V[i], W[i]}); G[V[i]].insert({U[i], W[i]}); sum += W[i]; } set<int>act = {}; for(int i = 0; i < n; ++i) { act.insert(i); } for(int i = 0; i < n; ++i) { ord[(int)G[i].size()].PB(i); T[i].val = 0; roots[i] = &T[i]; } nxt = n; vector<ll>res(n); res[0] = sum; ll delta = 0; for(k = 1; k < n; ++k) { //cerr << "K->" << k << "\n"; for(auto v : ord[k]) { act.erase(v); for(auto [nbh, w] : G[v]) { if(act.count(nbh)) { delta += w; G[nbh].erase({v, w}); cnt[nbh]++; h[nbh] += w; T[nxt].val = T[nxt].sum = w; auto p = split_val(roots[nbh], w); roots[nbh] = merge(p.ST, &T[nxt]); roots[nbh] = merge(roots[nbh], p.ND); nxt++; } } } ll s = 0; for(auto v : act) { if(!vis[v]) { dfs(v); s += dp[v][0]; } } for(auto v : act) vis[v] = false; res[k] = (sum - (s + delta)); } return res; } //int main() { //ios_base::sync_with_stdio(0); //cin.tie(0); //auto vec = minimum_closure_costs(4, {0, 2, 0}, {1, 0, 3}, {5, 10, 5}); //auto vec = minimum_closure_costs(5, {0, 0, 0, 2}, {1, 2, 3, 4}, {1, 4, 3, 2}); //cin >> n; //vi u(n-1), v(n-1), w(n-1); //for(int i = 0; i < n-1; ++i) cin >> u[i] >> v[i] >> w[i]; //auto vec = minimum_closure_costs(n, u, v, w); //for(auto x : vec) cout << x << " "; //}
#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...