Submission #1114470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114470		vladilius	Road Closures (APIO21_roads)	C++17	24 / 100	677 ms	1048576 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<vector<pll>> f(n, vector<pll>(n + 1));
    for (int k = 1; k < n; k++){
        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[k][i].ss;
                all.pb(f[k][i].ff + w - f[k][i].ss);
            }
            sort(all.begin(), all.end(), greater<ll>());
            
            f[k][v].ff = sum;
            for (int i = 0; i < min((int) all.size(), k - 1); i++){
                if (all[i] <= 0) break;
                f[k][v].ff += all[i];
            }
            f[k][v].ss = sum;
            for (int i = 0; i < min((int) all.size(), k); i++){
                if (all[i] <= 0) break;
                f[k][v].ss += all[i];
            }
        };
        dfs(1, 0);
    }
    
    int cnt = 0;
    for (int v = 1; v <= n; v++){
        for (int k = 1; k < n; k++){
            if (f[k - 1][v].ff != f[k][v].ff){
                cnt++;
            }
            if (f[k - 1][v].ss != f[k][v].ss){
                cnt++;
            }
        }
    }
    
    assert(cnt <= (6 * n));
    
    vector<ll> out;
    for (int i = 0; i < n; i++){
        out.pb(tot - f[i][1].ss);
    }
    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