| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1277122 | pvpro | 도로 폐쇄 (APIO21_roads) | C++20 | 0 ms | 0 KiB |
#define _GLIBCXX_DEBUG
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <chrono>
#include <random>
#include <complex>
#include <numeric>
#include <assert.h>
#include <functional>
#include <climits>
#include <cstring>
#include <iterator>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using ushort = unsigned short;
#ifndef LOCAL
#define endl "\n"
#endif
#define f first
#define s second
#define vec vector
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define mp make_pair
template<typename T1, typename T2>
istream& operator>> (istream &in, pair<T1, T2> &p) { in >> p.f >> p.s; return in; }
template<typename T1, typename T2>
ostream& operator<< (ostream &out, pair<T1, T2> p) { out << "(" << p.f << " " << p.s << ")"; return out; }
#define printv(v) cerr << #v << " "; for (auto &x : v) { cerr << x << " "; } cerr << endl;
#define printvv(v) cerr << #v << " "; for (auto &x : v) { for (auto &y : x) { cerr << y << " "; } cerr << endl; }
#define debug(x) cerr << #x << " " << x << endl;
template<typename T>
istream& operator>> (istream &in, vector<T> &v) {
for (auto &x : v) {
in >> x;
}
return in;
}
template<typename T>
ostream& operator<< (ostream &out, vector<T> v) {
for (auto &x : v) {
out << x << " ";
}
return out;
}
template<typename T>
void operator-=(vector<T> &v, int delta) {
for (auto &x : v) {
x -= delta;
}
}
template<typename T>
void operator+=(vector<T> &v, int delta) {
for (auto &x : v) {
x += delta;
}
}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
vector<vector<pii>> graph;
vector<vector<pii>> DP;
vector<pii> D;
vector<int> W;
int dfs(int v, int prev = -1, int w = 0) {
vector<int> res;
for (auto &u : graph[v]) {
if (u.f != prev) {
res.pb(dfs(u.f, v, u.s));
}
}
sort(all(res), [&](int &a, int &b) {
return DP[a].size() > DP[b].size();
});
if (res.empty()) {
DP[v] = {mp(w, w)};
D[v] = mp(0, 0);
W[v] = w;
return v;
}
int pw = graph[v].size();
vector<vector<int>> SUB(pw);
vector<vector<int>> toAdd(max((int)DP[res[0]].size(), pw) + 1);
for (int i = 1; i < res.size(); ++i) {
for (int j = 0; j < DP[res[i]].size(); ++j) {
if (j >= pw) {
DP[res[0]][j].f += min(DP[res[i]][j].f + D[res[i]].f, DP[res[i]][j].s + D[res[i]].s);
DP[res[0]][j].s += min(DP[res[i]][j].f + D[res[i]].f, DP[res[i]][j].s + D[res[i]].s);
} else {
DP[res[0]][j].f += DP[res[i]][j].f + D[res[i]].f;
DP[res[0]][j].s += DP[res[i]][j].f + D[res[i]].f;
SUB[j].pb(DP[res[i]][j].s + D[res[i]].s - (DP[res[i]][j].f + D[res[i]].f));
}
}
toAdd[DP[res[i]].size()].pb(-W[res[i]]);
}
toAdd[DP[res[0]].size()].pb(-W[res[0]]);
while (DP[res[0]].size() < pw) {
DP[res[0]].pb(mp(-D[res[0]].f, -D[res[0]].s));
}
vector<int> dop;
ll dopX = 0;
for (int i = 0; i < pw; ++i) {
for (auto &x : dop) {
SUB[i].pb(x);
}
sort(all(SUB[i]));
DP[res[0]][i].s += dopX;
for (int j = 0; j < min((int)SUB[i].size(), i - 1); ++j) {
DP[res[0]][i].s += SUB[i][j];
}
for (auto &x : toAdd[i]) {
dop.pb(x);
SUB[i].pb(x);
dopX -= x;
}
sort(all(SUB[i]));
DP[res[0]][i].f += dopX;
for (int j = 0; j < min((int)SUB[i].size(), i); ++j) {
DP[res[0]][i].f += SUB[i][j];
}
}
D[res[0]].f += w;
W[res[0]] = w;
DP[res[0]][0].s += w;
return res[0];
}
vector<ll> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w) {
graph.assign(n, {});
DP.assign(n, {});
W.assign(n, -1);
D.assign(n, mp(0, 0));
for (int i = 0; i < n - 1; ++i) {
graph[u[i]].pb(mp(v[i], w[i]));
graph[v[i]].pb(mp(u[i], w[i]));
}
auto ans = dfs(0);
vector<ll> fin(n);
for (int i = 0; i < DP[ans].size(); ++i) {
fin[i] = DP[ans][i].f + D[ans].f;
}
return fin;
}
#ifdef LOCAL
int main() {
freopen("in.txt", "r", stdin);
int N;
assert(1 == scanf("%d", &N));
std::vector<int> U(N - 1), V(N - 1), W(N - 1);
for (int i = 0; i < N - 1; ++i) {
assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
}
std::vector<long long> closure_costs = minimum_closure_costs(N, U, V, W);
for (int i = 0; i < static_cast<int>(closure_costs.size()); ++i) {
if (i > 0) {
printf(" ");
}
printf("%lld",closure_costs[i]);
}
printf("\n");
return 0;
}
#endif