| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 627040 | tamthegod | Road Closures (APIO21_roads) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
//#include "roads.h"
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 2e2 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
ll f[maxN][maxN];
int tmp[maxN];
int k;
vector<pair<int, int>> adj[maxN];
void dfs(int u, int par)
{
for(auto a : adj[u])
{
int v = a.fi, w = a.se;
if(v == par) continue;
dfs(v, u);
for(int i=0; i<=k; i++) tmp[i] = f[u][i];
tmp[k] += f[v][0] + w;
for(int i=k-1; i>=0; i--)
tmp[i] = min(f[u][i] + f[v][0] + w, f[u][i + 1] + f[v][1]);
for(int i=k-1; i>=1; i--)
tmp[i] = min(tmp[i], tmp[i + 1]);
for(int i=0; i<=k; i++) f[u][i] = tmp[i];
if(u == 1 && v == 3)
{
// cout << f[1][1];exit(0);
}
}
}
vector<ll> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W)
{
vector<ll> res;
bool ok = true;
ll sum = 0;
for(int i=0; i<n-1; i++)
{
int u = U[i] + 1, v = V[i] + 1, w = W[i];
//cout << u << " " << v << '\n';
sum += w;
if(U[i] != i || V[i] != i + 1) ok = false;
adj[u].pb({v, w});
adj[v].pb({u, w});
}
if(adj[1].size() == n - 1)
{
vector<int> vc;
for(int i=0; i<n-1; i++) vc.pb(W[i]);
sort(vc.begin(), vc.end());
for(int i=0; i<n; i++)
{
res.pb(sum);
sum -= vc.back();
vc.pop_back();
}
return res;
}
if(ok)
{
res.pb(sum);
f[1][1] = W[0];
for(int i=2; i<n; i++)
{
f[i][0] = f[i - 1][1];
f[i][1] = min(f[i - 1][0], f[i - 1][1]) + W[i - 1];
}
res.pb(min(f[n - 1][0], f[n - 1][1]));
while(res.size() != n) res.pb(0);
return res;
}
for(int _k=n-1; _k>=1; _k--)
{
k = _k;
memset(f, 0, sizeof f);
dfs(1, 0);
// cout << f[1][0];exit(0);
res.pb(f[1][0]);
}
res.pb(sum);
reverse(res.begin(), res.end());
return res;
}
void Solve()
{
int n;
cin >> n;
vector<int> u(n), v(n), w(n);
for(int i=0; i<n-1; i++) cin >> u[i];
for(int i=0; i<n-1; i++) cin >> v[i];
for(int i=0; i<n-1; i++) cin >> w[i];
vector<ll> res = minimum_closure_costs(n, u, v, w);
for(int v : res) cout << v << " ";
}
int32_t main()
{
// freopen("x.inp", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
Solve();
}