제출 #1178509

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178509		Muhammet	도로 폐쇄 (APIO21_roads)	C++17	0 / 100	89 ms	20548 KiB

roads

#include "bits/stdc++.h"
#include "roads.h"
// #include "grader.cpp"

using namespace std;

#define ll long long
#define SZ(s) (int)s.size()

const int N = 2e3 + 5;

int n, dp[N][N];

vector <pair <int, int>> v[N];

void f(int x, int y, int k) {
    vector <ll> v1;
    for(auto [i, w] : v[x]) {
        if(i == y) continue;
        f(i, x, k);
        v1.push_back(((!k ? 0 : dp[i][k-1]) + w - dp[i][k]));
        dp[x][k] += dp[i][k];
    }
    sort(v1.rbegin(), v1.rend());
    for(int i = 0; i < min(SZ(v1), k); i++) {
        dp[x][k] += v1[i];
    }
    return;
}

vector<ll> minimum_closure_costs(int NN, vector<int> u1, vector<int> u2, vector<int> w) {
    n = NN;
    vector <ll> ans(n, 0);
    ll s = 0;
    for(int i = 0; i < n-1; i++) {
        v[u1[i]].push_back({u2[i], w[i]});
        v[u2[i]].push_back({u1[i], w[i]});
        s += w[i];
    }
    for(int k = 0; k < n; k++) {
        f(0, -1, k);
        ans[k] = (s - dp[0][k]);
    }
    return ans;
}

• 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