Submission #1205369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205369		phamtienhoang	Museum (CEOI17_museum)	C++17	20 / 100	612 ms	1056836 KiB

museum

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <cassert>
#include <cstring> 

using namespace std;
const int N = 10001;
int n , k , root;
vector<pair<int , int > >  adj[N];
int  f[N][N][2];
int sz[N];


void dfs(int u , int father){
	sz[u] = 1;
	f[u][1][0] = f[u][1][1] = 0LL;
	for(int i = 0 ; i < adj[u].size() ; i++){
		int v = adj[u][i].first;
		int  cost = adj[u][i].second;
		if(v == father){
			continue;
		}
		dfs(v,  u);
		int  g[N][2];
		for(int j=0;j<=k;j++){
  			g[j][0]=g[j][1]=1e9 + 7;
		}
		for(int i = sz[u] ; i >= 0 ; i-- ){
			for(int j = sz[v] ; j >= 0 ; j--){
				g[i + j][0] = min(g[i + j][0]  , f[u][i][1] + f[v][j][0] +  cost);
				g[i + j][0] = min(g[i + j][0] , f[u][i][0] + f[v][j][1] + 2 * cost);
				g[i + j][1] = min(g[i + j][1] , f[u][i][1] + f[v][j][1] + 2 * cost);
			}
		}
		sz[u] += sz[v];
		for(int i = 1; i <= sz[u] ; i++){
			f[u][i][0] = min(f[u][i][0] , g[i][0]);
			f[u][i][1] = min(f[u][i][1] , g[i][1]);
		}
	}
}

int main(){
	cin >> n >> k >> root;
	for(int i = 1; i < n ; i++){
		int u , v ;
		int cost;
		cin >> u >> v >> cost;
		adj[u].push_back(make_pair(v, cost));
		adj[v].push_back(make_pair(u , cost));
	}
	for(int i = 1; i <= n ; i++){
		for(int j = 1; j <= n ; j++){
			f[i][j][0] = f[i][j][1] = 1e9 + 7;
		}
	}
	dfs(root, -1);
	cout << f[root][k][0];
	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 25
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20