제출 #1204203

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1204203		the_moon	Museum (CEOI17_museum)	C++17	20 / 100	836 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 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;
}

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<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){
//	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
	int 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];
	
}

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