Submission #1114455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114455		vladilius	Road Closures (APIO21_roads)	C++17	0 / 100	736 ms	1048576 KiB

roads

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

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<vector<ll>> dp(n + 1, vector<ll>(n));
    function<void(int, int)> dfs = [&](int v, int pr){
        for (auto [i, w]: g[v]){
            if (i == pr) continue;
            dfs(i, v);
        }
        
        for (int k = 1; k < n; k++){
            dp[v][k] = 0;
            vector<ll> all;
            for (auto [i, w]: g[v]){
                if (i == pr) continue;
                dp[v][k] += dp[i][k];
                all.pb(dp[i][k - 1] - dp[i][k] + w);
            }
            sort(all.begin(), all.end(), greater<ll>());
            for (int j = 0; j < min((int) all.size(), k); j++){
                if (all[j] <= 0) break;
                dp[v][k] += all[j];
            }
        }
        for (int k = 1; k < n; k++){
            dp[v][k] = max(dp[v][k], dp[v][k - 1]);
        }
    };
    dfs(1, 0);
    
    vector<ll> out;
    for (int i = 0; i < n; i++){
        out.pb(tot - dp[1][i]);
    }
    return out;
}

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