Submission #907522

#	Time	Username	Problem	Language	Result	Execution time	Memory
907522		pragmatist	Road Closures (APIO21_roads)	C++17	14 / 100	2079 ms	19036 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];
long long cost[201][201];
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);
    }

    vector<Data> cur;
    for(auto [to, w] : g[v]) {
        if(to == pr) {
            continue;
        }
        cur.push_back({dp[to][0], dp[to][1]});
    }
    int m = (int)g[v].size()-(v != pr);
    for(int i = 0; i <= m; ++i) {
        for(int j = 0; j <= m; ++j) {
            cost[i][j] = INF;
        }
    }
    cost[0][0] = 0;
    for(int i = 1; i <= m; ++i) {
        for(int j = 0; j <= m; ++j) {
            cost[i][j] = min(cost[i][j], cost[i-1][j]+cur[i-1].x);
            if(j) {
                cost[i][j] = min(cost[i][j], cost[i-1][j-1]+cur[i-1].y);
            }
        }
    }
    int need = max(0, (int)g[v].size()-k);
    if(need <= m) {
        dp[v][0] = INF;
        for(int i = need; i <= m; ++i) {
            dp[v][0] = min(dp[v][0], cost[m][i]);
        }
    } else {
        dp[v][0] = INF;
    }
    need = max((int)g[v].size()-k-1, 0);
    if(need <= m) {
        dp[v][1] = INF;
        for(int i = need; i <= m; ++i) {
            dp[v][1] = min(dp[v][1], cost[m][i]+last);
        }
    } else {
        assert(0);
        dp[v][1] = 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: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22