Submission #1204200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204200		the_moon	Museum (CEOI17_museum)	C++17	100 / 100	213 ms	151796 KiB

museum

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define The_Moon ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int MAX_N = 10005, oo = 6e8;

void minimise(int& a, const int& b){
	if(a > b)a = b;
}
void maximise(int& a, const int& b){
	if(a < b)a = b;
}

struct node_edge{
	int x, val;
};

vector<node_edge> adj[MAX_N]; 

vector<int> merge_dp(const vector<int>& a, const vector<int>& b, const int& k){
	vector<int> res; res.resize(a.size()-1 + b.size()-1 +1); for(auto& i : res)i = oo;
	res[0] = 0;
	for(int i = 1; i < a.size(); i++){
		minimise(res[i], a[i]);
		for(int j = 1; j < b.size(); j++)
			minimise(res[i+j], a[i]+k+b[j]);		
	}
	return res;
}

void merge_dp(vector<int>& res, const vector<int>& a, const vector<int>& b, const int& k){
	for(int i = 1; i < a.size(); i++){
		minimise(res[i], a[i]);
		for(int j = 1; j < b.size(); j++)
			minimise(res[i+j], a[i]+k+b[j]);		
	}
}

vector<int> dp[MAX_N][2]; // 0: k có đg ĐB | 1: có đg ĐB

void solve(int u, int par){
	dp[u][0] = {0, 0};
	dp[u][1] = {0, 0};
	
	for(auto v : adj[u]){
		if(v.x == par)continue;
		solve(v.x, u);
		
		dp[u][1] = merge_dp(dp[u][1], dp[v.x][0], v.val*2);
		merge_dp(dp[u][1], dp[u][0], dp[v.x][1], v.val);	
		dp[u][0] = merge_dp(dp[u][0], dp[v.x][0], v.val*2);
	}
}

int main(){
	The_Moon
	int n, k, x; cin >> n >> k >> x;
	
	for(int i = 0; i < n-1; i++){
		int a, b, c; 
		cin >> a >> b >> c;
		// test
//		a = i+1; b = i+2; c = i+1;
		// end test
		
		adj[a].push_back({b, c});
		
		adj[b].push_back({a, c});
	}	
	solve(x, -1);
	
//	ll cnt = 0;
//	for(ll i = 0; i <= n; i++){
//		cnt += dp[i][0].size() + dp[i][1].size();
//	}
//	cout << cnt << '\n';
	
	cout << dp[x][1][k];
	
}

/*
11 8 3
1 3 3
3 2 5
6 4 5
1 11 3
9 1 2
9 10 2
3 7 10
6 7 1
7 8 1
7 5 1

10 10 10
1 2 1 
2 3 2
3 4 3
4 5 4
5 6 5
6 7 6
7 8 7
8 9 8 
9 10 9
*/

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