Submission #1035596

#TimeUsernameProblemLanguageResultExecution timeMemory
1035596mispertionRoad Closures (APIO21_roads)C++17
53 / 100
2025 ms54608 KiB
#include "roads.h" #include <bits/stdc++.h> #include <vector> using namespace std; #pragma GCC optimize("unroll-loops") #pragma GCC optimize("O3") mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define pb push_back #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() #define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define F first #define S second #define getlast(s) (*s.rbegin()) #define debg cout << "OK\n" const ld PI = 3.1415926535; const int N = 5e5+10; const int M = 1e4 + 5; int mod = 1e9+7; const int infi = INT_MAX; const ll infl = LLONG_MAX; const int P = 467743; ll dp[N][2], sm[N], used[N]; int n, k, tresh = 170; vector<pair<ll, ll>> g[N]; vector<pair<ll, ll>> ng[N]; vector<ll> vs[N]; pair<ll, pll> tmp[N]; void dfs(int v, int p, int w){ dp[v][0] = dp[v][1] = 0; for(auto u : g[v]) if(u.F != p) dfs(u.F, v, u.S); int ctmp = 0; for(auto u : g[v]){ if(u.F != p){ tmp[ctmp++] = {dp[u.F][1] - dp[u.F][0], {dp[u.F][1], dp[u.F][0]}}; } } sort(tmp, tmp + ctmp); reverse(tmp, tmp + ctmp); for(int i = 0; i < min(k, ctmp); i++){ if(tmp[i].F > 0){ dp[v][0] += tmp[i].S.F; }else{ dp[v][0] += tmp[i].S.S; } } for(int i = min(k, ctmp); i < ctmp; i++){ dp[v][0] += tmp[i].S.S; } for(int i = 0; i < min(k - 1,ctmp); i++){ if(tmp[i].F > 0){ dp[v][1] += tmp[i].S.F; }else{ dp[v][1] += tmp[i].S.S; } } for(int i = min(k - 1, ctmp); i < ctmp; i++){ dp[v][1] += tmp[i].S.S; } dp[v][1] += w; } void dfs1(int v, int p, int w){ used[v] = 1; dp[v][0] = dp[v][1] = 0; for(auto u : ng[v]){ if(u.F != p) dfs1(u.F, v, u.S); } //cout << v << '\n'; while(sz(vs[v]) > k){ sm[v] -= vs[v].back(); vs[v].pop_back(); } int ps = min(sz(vs[v]), k) - 1, cur = min(sz(vs[v]), k); vector<pair<ll, pll>> ha = {}; for(auto u : ng[v]){ if(u.F != p){ ha.pb({dp[u.F][1] - dp[u.F][0], {dp[u.F][1], dp[u.F][0]}}); } } /*cout << sm[v] << ": "; for(auto e : vs[v]){ cout << e << ' '; } cout << '\n';*/ sort(all(ha)); reverse(all(ha)); dp[v][0] = sm[v]; for(auto e : ha){ //cout << e.F << ' ' << e.S.F << ' ' << e.S.S << ' ' << ps << ' ' << cur << '\n'; if(e.F <= 0 || ps < 0){ dp[v][0] += e.S.S; //cout << "1\n"; }else{ if(cur < k){ cur++; dp[v][0] += e.S.F; //cout << "2\n"; }else{ if(e.F > vs[v][ps]){ dp[v][0] -= vs[v][ps]; dp[v][0] += e.S.F; ps--; //cout << "3\n"; }else{ dp[v][0] += e.S.S; //cout << "4\n"; } } } } while(sz(vs[v]) > k - 1){ sm[v] -= vs[v].back(); vs[v].pop_back(); } /*cout << sm[v] << ": "; for(auto e : vs[v]){ cout << e << ' '; } cout << '\n';*/ ps = min(sz(vs[v]), k - 1) - 1, cur = min(sz(vs[v]), k - 1); dp[v][1] = sm[v] + w; for(auto e : ha){ if(e.F <= 0 || ps < 0){ dp[v][1] += e.S.S; }else{ if(cur < k - 1){ cur++; dp[v][1] += e.S.F; }else{ if(e.F > vs[v][ps]){ dp[v][1] -= vs[v][ps]; dp[v][1] += e.S.F; ps--; }else{ dp[v][1] += e.S.S; } } } } //cout << dp[v][0] << ' ' << dp[v][1] << '\n'; } vector<long long> minimum_closure_costs(int _n, vector<int> U, vector<int> V, vector<int> W) { n = _n; vector<ll> ans(n, 0); for(int i = 0; i < n - 1; i++){ U[i]++; V[i]++; g[V[i]].pb({U[i], W[i]}); g[U[i]].pb({V[i], W[i]}); ans[0] += W[i]; } k = 1; for(; k < min(tresh, n); k++){ dfs(1, -1, 0); ans[k] = ans[0] - dp[1][0]; } vector<int> heavy = {}; ll ad = 0; for(int i = 1; i <= n; i++){ if(sz(g[i]) > tresh){ heavy.pb(i); for(auto e : g[i]){ int u = e.F, w = e.S; if(sz(g[u]) > tresh){ ng[i].pb({u, w}); }else{ vs[i].pb(w); } } sort(all(vs[i])); reverse(all(vs[i])); for(auto e : vs[i]) sm[i] += e; }else{ for(auto e : g[i]){ int u = e.F, w = e.S; if(sz(g[u]) <= tresh){ ad += w; } } } } ad /= 2; /*for(auto e : heavy){ cout << e << ' ' << sm[e] << ": "; for(auto u : ng[e]){ cout << "(" << u.F << ", " << u.S << ") "; } for(auto u : vs[e]){ cout << u << ' '; } cout << '\n'; } cout << ad << "\n";*/ for(k = n - 1; k >= tresh; k--){ //cout << k << ":\n"; ll ret = ad; for(auto e : heavy){ if(!used[e]){ dfs1(e, -1, 0); ret += dp[e][0]; } } for(auto e : heavy) used[e] = 0; ans[k] = ans[0] - ret; } return ans; }
#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...