Submission #960734

#TimeUsernameProblemLanguageResultExecution timeMemory
960734peterandvoiRoad Closures (APIO21_roads)C++17
29 / 100
198 ms159700 KiB
#include "roads.h" #include <bits/stdc++.h> using namespace std; #ifdef ngu #include "debug.h" #else #define debug(...) 42 #endif const int mxN = (int) 1e5 + 5; const int LOG = 30; const int NODE = mxN * LOG; const long long INF = (long long) 1e18; #define BIT(x, i) ((x) >> (i) & 1) int N, K; int node; long long dp[mxN][2]; int deg[mxN]; bool vis[mxN], on[mxN]; int nxt[NODE][2], cnt[NODE]; long long sum[NODE]; vector<int> pos[mxN]; vector<pair<int, int>> g[mxN], graph[mxN]; void ins(int u, int x) { int p = u; for (int i = LOG - 1; i >= 0; --i) { int c = BIT(x, i); if (!nxt[p][c]) { nxt[p][c] = ++node; } p = nxt[p][c]; sum[p] += x; cnt[p]++; } } void ers(int u, int x) { int p = u; for (int i = LOG - 1; i >= 0; --i) { int c = BIT(x, i); p = nxt[p][c]; sum[p] -= x; cnt[p]--; } } long long get(int u, int k) { k = max(0, k); if (!k) { return 0; } long long res = 0; int p = u; for (int i = LOG - 1; i >= 0; --i) { if (cnt[nxt[p][0]] >= k) { p = nxt[p][0]; } else { k -= cnt[nxt[p][0]]; res += sum[nxt[p][0]]; p = nxt[p][1]; } } if (!p) { exit(0); } return res + k * (sum[p] / cnt[p]); } int rt; void dfs(int u) { dp[u][0] = dp[u][1] = INF; vis[u] = true; long long s = 0; vector<long long> delta; for (auto [v, w] : graph[u]) { if (!vis[v]) { dfs(v); delta.emplace_back(dp[v][1] - dp[v][0] + w); s += dp[v][0]; } } sort(delta.begin(), delta.end()); for (int i = 1; i < (int) delta.size(); ++i) { delta[i] += delta[i - 1]; } int need = deg[u] - K; int m = (int) delta.size(), tm = deg[u] - m - (u != rt); for (int i = 0; i <= m; ++i) { if (need - 1 - i <= tm) { dp[u][1] = min(dp[u][1], s + (i ? delta[i - 1] : 0LL) + get(u, need - 1 - i)); } if (need - i <= tm) { dp[u][0] = min(dp[u][0], s + (i ? delta[i - 1] : 0LL) + get(u, need - i)); } } } vector<int> ver; void turn_on(int u) { on[u] = true; ver.emplace_back(u); for (auto [v, w] : g[u]) { if (on[v]) { ers(v, w); graph[u].emplace_back(v, w); graph[v].emplace_back(u, w); } else { ins(u, w); } } } std::vector<long long> minimum_closure_costs(int n, std::vector<int> U, std::vector<int> V, std::vector<int> W) { N = n; node = N; vector<long long> res(N); for (int i = 0; i < N - 1; ++i) { U[i]++; V[i]++; deg[U[i]]++; deg[V[i]]++; g[U[i]].emplace_back(V[i], W[i]); g[V[i]].emplace_back(U[i], W[i]); } for (int i = 1; i <= N; ++i) { pos[deg[i]].emplace_back(i); } for (int i = N - 1; i >= 0; --i) { K = i; for (int u : pos[i + 1]) { turn_on(u); } for (int u : ver) { if (!vis[u]) { rt = u; dfs(u); res[i] += dp[u][0]; } } for (int u : ver) { vis[u] = false; } } return res; } #ifdef ngu signed main() { freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); int n; cin >> n; vector<int> 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 res = minimum_closure_costs(n, U, V, W); for (auto x : res) { cout << x << " "; } } #endif // ngu
#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...