Submission #1100632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100632		vjudge1	Museum (CEOI17_museum)	C++17	100 / 100	449 ms	748620 KiB

museum

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 2;
std::vector<array<int, 2>> g[N];
const long long mx = 1LL << 60;
long long dp[2][N][N];
int dfs(int v, int par) {
	int sz = 1;
	for(auto &[u, w]:g[v]) {
		if(u == par) continue;
		int p = dfs(u, v);
		for(int i = sz + 1; i <= sz + p; i++)
			dp[0][v][i] = dp[1][v][i] = mx;
		for(int i = sz + p; i >= 0; i--) {
			for(int j = max(i - p, 0); j <= min(i, sz); j++) {
				int k = i - j;
				dp[0][v][i] = min(dp[0][v][i], dp[0][v][j] + dp[1][u][k] + w + w);
				dp[0][v][i] = min(dp[0][v][i], dp[1][v][j] + dp[0][u][k] + w);
				dp[1][v][i] = min(dp[1][v][i], dp[1][v][j] + dp[1][u][k] + w + w);
			}
		}
		sz += p;
	}
	return sz;
}
int main() {
	ios_base::sync_with_stdio(0);
    cin.tie(0);
	int t = 1; 
	//cin >> t;
	while(t--) {
		int n, k, x; cin >> n >> k >> x;
		for(int i = 1; i < n; i++) {
			int a, b, c; cin >> a >> b >> c;
			g[a].push_back({b, c});
			g[b].push_back({a, c});
		}
		dfs(x, 0);
		cout << min(dp[0][x][k], dp[1][x][k]) << "\n";
	}
	
	return 0;
}

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