Submission #1133732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133732		PagodePaiva	Road Closures (APIO21_roads)	C++17	24 / 100	360 ms	65860 KiB

roads

#include<bits/stdc++.h>
#include "roads.h"
#include <vector>
#define ll long long

using namespace std;

const ll N = 2010;
const ll inf = 1e18/N;
vector <pair<ll, ll>> g[N];
ll dp[N][N][2];

void solve(ll p, ll v, ll k, ll fg){
	if(dp[v][k][fg] != -1) return;
	ll sum = 0;
	vector <ll> best;
	for(auto [x, w] : g[v]){
		if(x == p) continue;
		solve(v, x, k, 0);
		solve(v, x, k, 1);
		sum += dp[x][k][0];
		best.push_back(dp[x][k][1]-dp[x][k][0]+w);
	}
	ll deg = g[v].size();
	deg -= fg;
	sort(best.begin(), best.end());
	reverse(best.begin(), best.end());
	while(deg > k or (!best.empty() ? best.back() <= 0 : false)){
		if(best.empty()) break;
		sum += best.back();
		deg--;
		best.pop_back();
	}
	dp[v][k][fg] = (deg > k ? inf : sum);
	return;
}

vector<long long> minimum_closure_costs(int n, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	memset(dp, -1, sizeof dp);
	for(ll i = 0;i < n-1;i++){
		g[U[i]+1].push_back({V[i]+1, W[i]});
		g[V[i]+1].push_back({U[i]+1, W[i]});
	}
	vector <ll> ans;
	for(ll k = 0;k < n;k++){
		solve(1, 1, k, 0);
		ans.push_back(dp[1][k][0]);
	}
	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