Submission #1204164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204164		the_moon	Museum (CEOI17_museum)	C++17	20 / 100	616 ms	1114112 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 ll MAX_N = 10005, oo = 1e17;

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

int lst[MAX_N]{0}, nxt[MAX_N]{0}, cxt = 0;
struct node_edge{
	int x, val;
}trans[MAX_N]; 

void add_edge(int u, int v, int val){
	
//	cout << "add " << u << ' ' << v << ' ' << val << '\n';
	
	cxt++;
	trans[cxt].x = v; trans[cxt].val = val;
	nxt[cxt] = lst[u];
	lst[u] = cxt;
}

vector<ll> merge_dp(const vector<ll>& a, const vector<ll>& b, const ll& k){
	vector<ll> 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<ll>& res, const vector<ll>& a, const vector<ll>& b, const ll& 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<ll> dp[MAX_N][2]; // 0: k có đg ĐB | 1: có đg ĐB

void solve(int u, int par){
//	cout << "solve " << u << ' ' << par << '\n';
	dp[u][0] = {0, 0};
	dp[u][1] = {0, 0};
	
	for(int vid = lst[u]; vid > 0; vid = nxt[vid]){
		if(trans[vid].x == par)continue;
		solve(trans[vid].x, u);
		
		dp[u][1] = merge_dp(dp[u][1], dp[trans[vid].x][0], trans[vid].val*2);
		merge_dp(dp[u][1], dp[u][0], dp[trans[vid].x][1], trans[vid].val);	
		dp[u][0] = merge_dp(dp[u][0], dp[trans[vid].x][0], trans[vid].val*2);
	}
	
//	cout << "? " << u << " : "; for(auto i : dp[u])cout << i << ' '; cout << endl;
}

int main(){
	The_Moon
	ll n, k, x; cin >> n >> k >> x;
	
	for(int i = 0; i < n-1; i++){
		int a, b, c; cin >> a >> b >> c;
		add_edge(a, b, c); add_edge(b, a, c);
	}
	
	solve(x, -1);
	
	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
*/

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