Submission #567714

#	Time	Username	Problem	Language	Result	Execution time	Memory
567714		amunduzbaev	Road Closures (APIO21_roads)	C++17	24 / 100	393 ms	63556 KiB

roads

#include "roads.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
#define ar array
#define ff first
#define ss second

const int N = 2e3 + 5;
vector<pair<int, ll>> edges[N];
ll dp[N][N][2];

void dfs(int u, int p = -1){
	for(auto x : edges[u]){
		if(x.ff == p) continue;
		dfs(x.ff, u);
	}
	
	for(int t=0;t<2;t++){
		for(int j=0;j<N;j++){
			vector<ll> tt;
			for(auto x : edges[u]){
				if(x.ff == p) continue;
				dp[u][j][t] += dp[x.ff][j][0] + x.ss;
				if(j){
					tt.push_back(dp[x.ff][j][1] - dp[x.ff][j][0] - x.ss);
				}
			}
			
			sort(tt.begin(), tt.end());
			for(int l=0;l<min((int)tt.size(), j - t);l++){
				if(tt[l] > 0) break;
				dp[u][j][t] += tt[l];
			}
		}
	}
}

vector<ll> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w) {
	for(int i=0;i<n-1;i++){
		edges[v[i]].push_back({u[i], w[i]});
		edges[u[i]].push_back({v[i], w[i]});
	}
	
	dfs(0);
	vector<ll> res;
	for(int k=0;k<n;k++){
		res.push_back(dp[0][k][0]);
	} return res;
}

/*

5
0 1 1
0 2 4
0 3 3
2 4 2

*/

• 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