Submission #983994

#	Time	Username	Problem	Language	Result	Execution time	Memory
983994		The_Samurai	Road Closures (APIO21_roads)	C++17	24 / 100	2050 ms	26452 KiB

roads

#include "bits/stdc++.h"
#include "roads.h"
using namespace std;
using ll = long long;

const int N = 1e5 + 5, sq = 2000;
const ll inf = 1e18;
vector<vector<pair<int, int>>> g(N);
vector<int> par(N);

pair<ll, ll> dfs(int u, int came, int k) {
    int need = (int) g[u].size() - k;
    ll sum = 0;
    vector<ll> vec;
    vector<pair<ll, ll>> all;
    for (auto [v, w]: g[u]) {
        if (par[u] == v) continue;
        par[v] = u;
        auto it = dfs(v, w, k);
        all.emplace_back(it);
        if (it.first < it.second) {
            vec.emplace_back(it.second - it.first);
            sum += it.first;
        }
        else sum += it.second, need--;
    }
    sort(vec.begin(), vec.end());
    if (need <= (int) vec.size()) for (int i = 0; i < need; i++) sum += vec[i];
    else sum = inf;
    
    vec.clear();
    int need2 = (int) g[u].size() - k - 1;
    ll sum2 = came;
    int z = 0;
    for (auto [v, w]: g[u]) {
        if (par[u] == v) continue;
        auto it = all[z++];
        if (it.first < it.second) {
            vec.emplace_back(it.second - it.first);
            sum2 += it.first;
        }
        else sum2 += it.second, need2--;
    }
    sort(vec.begin(), vec.end());
    for (int i = 0; i < need2; i++) sum2 += vec[i];
    // cout << u << ' ' << sum << ' ' << sum2 << ' ' << need << endl;
    return {sum, sum2};
}

vector<ll> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w) {
    for (int i = 0; i < n - 1; i++) {
        g[u[i]].emplace_back(v[i], w[i]);
        g[v[i]].emplace_back(u[i], w[i]);
    }
    vector<ll> ans(n);
    for (int k = 0; k < min(n, sq); k++) {
        auto it = dfs(0, 0, k);
        ans[k] = it.first;
    }
    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