제출 #964698

#제출 시각아이디문제언어결과실행 시간메모리
964698kilkuwu도로 폐쇄 (APIO21_roads)C++17
24 / 100
2089 ms23008 KiB
#include "roads.h" #include <bits/stdc++.h> std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) { std::vector<std::vector<std::pair<int, int>>> adj(N); long long tot = 0; for (int i = 0; i < N - 1; i++) { int u = U[i], v = V[i], w = W[i]; adj[u].emplace_back(v, w); adj[v].emplace_back(u, w); tot += w; } auto solve = [&](int k) -> long long { std::vector<std::array<long long, 2>> dp(N, {-1, -1}); auto dfs = [&](auto self, int u, int p, int s) { if (dp[u][s] != -1) return dp[u][s]; std::vector<std::pair<int, std::pair<int, int>>> options; for (auto [v, w] : adj[u]) { if (v == p) continue; self(self, v, u, 0); self(self, v, u, 1); options.emplace_back(dp[v][1] - (dp[v][0] + w), std::make_pair(v, w)); } // std::sort(options.begin(), options.end()); int rem = k - s; // 0 means we are disconnected, 1 tuc la minh noi thang tren long long ans = 0; for (int i = 0; i < (int) options.size(); i++) { int v = options[i].second.first; int w = options[i].second.second; if (i < rem) { ans += std::min(dp[v][1], dp[v][0] + w); } else { ans += dp[v][0] + w; } } return dp[u][s] = ans; }; return dfs(dfs, 0, -1, 0); }; std::vector<long long> res(N); res[0] = tot; res[N - 1] = 0; for (int i = N - 2; i >= 1; i--) { res[i] = solve(i); } return res; }
#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...