Submission #981793

#	Time	Username	Problem	Language	Result	Execution time	Memory
981793		Unforgettablepl	Road Closures (APIO21_roads)	C++17	0 / 100	2078 ms	20748 KiB

roads

#include <bits/stdc++.h>
using namespace std;

vector<pair<int,int>> adj[100001];
long long DP[100001][2];
int k;

void dfs(int x,int p,int w){
    DP[x][1] = w;
    DP[x][0] = 0;
    int sub = 0;
    vector<int> options;
    for(auto&i:adj[x])if(i.first!=p){
        dfs(i.first,x,i.second);
        sub++;
        DP[x][0]+=DP[i.first][0];
        options.emplace_back(DP[i.first][1]-DP[i.first][0]);
    }
    sort(options.begin(),options.end());
    DP[x][1]+=DP[x][0];
    for(int i=0;i<max(0,sub-k+1);i++)DP[x][0]+=options[i];
    for(int i=0;i<max(0,sub-k);i++)DP[x][1]+=options[i];
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {
    long long base = 0;
    for(int i=0;i<N-1;i++){
        adj[U[i]].emplace_back(V[i],W[i]);
        adj[V[i]].emplace_back(U[i],W[i]);
        base+=W[i];
    }
    vector<long long> ans(N);
    ans[0] = base;
    for(int i=1;i<N;i++){
        k = i;
        dfs(0,-1,0);
        ans[i] = DP[0][1];
    }
    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