Submission #1114460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114460		vladilius	Road Closures (APIO21_roads)	C++17	24 / 100	2076 ms	22348 KiB

roads

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>

vector<ll> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W){
    vector<pii> g[n + 1];
    ll tot = 0;
    for (int i = 0; i < n - 1; i++){
        int u = U[i] + 1, v = V[i] + 1, w = W[i];
        g[u].pb({v, w});
        g[v].pb({u, w});
        tot += w;
    }
    
    vector<ll> dp(n);
    for (int k = 1; k < n; k++){
        vector<pll> f(n + 1);
        function<void(int, int)> dfs = [&](int v, int pr){
            for (auto [i, w]: g[v]){
                if (i == pr) continue;
                dfs(i, v);
            }

            vector<ll> all;
            ll sum = 0;
            for (auto [i, w]: g[v]){
                if (i == pr) continue;
                sum += f[i].ss;
                all.pb(f[i].ff + w - f[i].ss);
            }
            sort(all.begin(), all.end(), greater<ll>());
            
            f[v].ff = sum;
            for (int i = 0; i < min((int) all.size(), k - 1); i++){
                if (all[i] <= 0) break;
                f[v].ff += all[i];
            }
            f[v].ss = sum;
            for (int i = 0; i < min((int) all.size(), k); i++){
                if (all[i] <= 0) break;
                f[v].ss += all[i];
            }
        };
        dfs(1, 0);
        
        dp[k] = f[1].ss;
    }
    
    vector<ll> out;
    for (int i = 0; i < n; i++){
        out.pb(tot - dp[i]);
    }
    return out;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22