Submission #567705

#	Time	Username	Problem	Language	Result	Execution time	Memory
567705		amunduzbaev	Road Closures (APIO21_roads)	C++17	0 / 100	31 ms	6476 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

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

void dfs(int u, int p = -1){
	for(auto x : edges[u]){
		if(x[0] == p) continue;
		dfs(x[0], 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[0] == p) continue;
				dp[u][j][t] += x[1] + dp[x[0]][j][0];
				if(j) tt.push_back(dp[x[0]][j][1] - x[1] - dp[x[0]][j][0]);
			}
			
			sort(tt.begin(), tt.end());
			for(int l=0;l<min((int)tt.size(), j - t);l++){
				dp[u][j][t] += tt[l];
			}
		}
	}
	
	//~ for(int t=0;t<2;t++){
		//~ for(int k=0;k<5;k++){
			//~ cout<<dp[u][k][t]<<" ";
		//~ } cout<<"\n";
	//~ }
}

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-1;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: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22