Submission #1177976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177976		stdfloat	Road Closures (APIO21_roads)	C++20	0 / 100	2095 ms	19832 KiB

roads

#include <bits/stdc++.h>
#include "roads.h"
// #include "grader.cpp"
using namespace std;

using ll = long long;

#define sz(v)    (int)(v).size()

vector<ll> u;

vector<vector<ll>> dp;

vector<vector<pair<int, int>>> E;

void dfs(int x, int k, int p = -1) {
    for (auto [i, w] : E[x]) {
        if (i != p) {
            dp[i][0] = w;
            dfs(i, k, x);
        }
    }

    u.clear();
    for (auto [i, w] : E[x]) {
        if (i == p) continue;

        dp[x][0] += dp[i][1];
        dp[x][1] += dp[i][1];
        u.push_back(dp[i][0] - dp[i][1]);
    }

    sort(u.begin(), u.end());

    for (int i = 0; i < sz(u); i++) {
        dp[x][0] += (i < sz(u) - k || u[i] < 0 ? u[i] : 0);
        dp[x][1] += (i <= sz(u) - k || u[i] < 0 ? u[i] : 0);
    }
}

vector<ll> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W) {
    E.assign(n, {});
    for (int i = 0; i < n - 1; i++) {
        E[U[i]].push_back({V[i], W[i]});
        E[V[i]].push_back({U[i], W[i]});
    }

    vector<ll> v(n);
    for (int i = 0; i <= n; i++) {
        dp.assign(n, vector<ll>(2));
        dfs(0, i);
    
        v[i] = dp[0][0];
    }

    return v;
}

• 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