Submission #983982

#TimeUsernameProblemLanguageResultExecution timeMemory
983982The_SamuraiRoad Closures (APIO21_roads)C++17
0 / 100
2023 ms11216 KiB
#include "bits/stdc++.h" #include "roads.h" using namespace std; using ll = long long; const int N = 1e5 + 5, sq = 2000; const ll inf = 1e18; vector<vector<pair<int, int>>> g(N); vector<int> par(N); pair<ll, ll> dfs(int u, int came, int k) { int need = (int) g[u].size() - k; ll sum = 0; vector<ll> vec; vector<pair<ll, ll>> all; for (auto [v, w]: g[u]) { if (par[u] == v) continue; par[v] = u; auto it = dfs(v, w, k); all.emplace_back(it); if (it.first < it.second) { vec.emplace_back(it.second - it.first); sum += it.first; } else sum += it.second, need--; } sort(vec.begin(), vec.end()); if (need <= (int) vec.size()) for (int i = 0; i < need; i++) sum += vec[i]; else sum = inf; vec.clear(); int need2 = (int) g[u].size() - k - 1; ll sum2 = came; int z = 0; for (auto [v, w]: g[u]) { if (par[u] == v) continue; auto it = all[z++]; if (it.first < it.second) { vec.emplace_back(it.second - it.first); sum2 += it.first; } else sum2 += it.second, need2--; } sort(vec.begin(), vec.end()); // cout << u << ' ' << sum << ' ' << sum2 << ' ' << need << endl; return {sum, sum2}; } vector<ll> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w) { for (int i = 0; i < n - 1; i++) { g[u[i]].emplace_back(v[i], w[i]); g[v[i]].emplace_back(u[i], w[i]); } vector<ll> ans(n + 1); for (int k = 0; k <= min(n, sq); k++) { auto it = dfs(0, 0, k); ans[k] = it.first; } 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...