| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 925235 | TAhmed33 | 도로 폐쇄 (APIO21_roads) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 25;
vector <pair <int, int>> adj[MAXN];
ll dp[MAXN][2], cur; int n;
void dfs (int pos, int par) {
ll sum = 0;
for (auto j : adj[pos]) {
if (j.first != par) {
dfs(j.first, pos);
sum += dp[j.first][0];
}
}
dp[pos][0] = dp[pos][1] = sum;
vector <ll> k;
for (auto j : adj[pos]) {
if (j.first != par) {
k.push_back(j.second + dp[j.first][1] - dp[j.first][0]);
}
}
sort(k.begin(), k.end());
int z = (int)adj[pos].size() - (par != -1);
ll mx1 = (ll)1e18, mx2 = (ll)1e18;
sum = 0;
k.insert(k.begin(), 0);
for (int j = 0; j < (int)k.size(); j++) {
sum += k[j];
if (j >= z - cur + (par != -1)) mx1 = min(mx1, sum);
if (j >= z - cur) mx2 = min(mx2, sum);
}
dp[pos][0] += mx1; dp[pos][1] += mx2;
}
vector <ll> minimum_closure_costs (int N, vector <int> u, vector <int> v, vector <int> w) {
n = N;
for (int i = 0; i + 1 < n; i++) {
adj[u[i] + 1].push_back({v[i] + 1, w[i]});
adj[v[i] + 1].push_back({u[i] + 1, w[i]});
}
vector <ll> ans;
for (int i = 0; i < n; i++) {
cur = i; for (int j = 1; j <= n; j++) dp[j][0] = dp[j][1] = 0;
dfs(1, -1);
ans.push_back(dp[1][0]);
}
return ans;
}
int main () {
int n;
cin >> n;
vector <int> u(n - 1), v(n - 1), w(n - 1);
for (int i = 0; i + 1 < n; i++) cin >> u[i] >> v[i] >> w[i];
auto x = minimum_closure_costs(n, u, v, w);
for (auto i : x) cout << i << " ";
cout << '\n';
}