Submission #909652

#	Time	Username	Problem	Language	Result	Execution time	Memory
909652		pragmatist	Road Closures (APIO21_roads)	C++17	24 / 100	2097 ms	22200 KiB

roads

#include <bits/stdc++.h>

using namespace std;

const int N = (int)1e5 + 7;
const long long INF = (long long)1e18 + 7;
const long long oo = (long long)1e15 + 7;
const int inf = (int)1e9 + 7;

int n, k;
long long dp[N][2];
vector<pair<int, int> > g[N];

struct Data {
    long long x, y;
};

void dfs(int v, int pr, int last) {
    for(auto [to, w] : g[v]) {
        if(to == pr) {
            continue;
        }
        dfs(to, v, w);
    }
    long long tot = 0;
    vector<long long> cur;
    for(auto [to, w] : g[v]) {
        if(to == pr) {
            continue;
        }
        tot += dp[to][1];
        cur.push_back(dp[to][0]-dp[to][1]);
    }
    sort(cur.begin(), cur.end());
    dp[v][1] = tot+last;
    if(k+(v == pr)) {
        dp[v][0] = tot;
        for(int i = 0; i < min((int)cur.size(), k); ++i) {
            if(cur[i] > oo) {
                break;
            }
            tot += cur[i];
            if(i < k+(v == pr)-1) {
                dp[v][0] = min(dp[v][0], tot);
            }
            dp[v][1] = min(dp[v][1], tot+last);
        }
    } else {
        dp[v][0] = INF;
    }
}

vector<long long> minimum_closure_costs(int _N, vector<int> _U, vector<int> _V, vector<int> _W) {
    n = _N;
    for(int i = 0; i < n-1; ++i) {
        int u = _U[i];
        int v = _V[i];
        int w = _W[i];
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    vector<long long> ans;
    for(int i = 0; i < n; ++i) {
        k = i;
        dfs(0, 0, inf);
        ans.push_back(dp[0][0]);
    }
    return ans;
}

• 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