Submission #1290093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290093		SoSmolSten	Museum (CEOI17_museum)	C++20	100 / 100	253 ms	360008 KiB

museum

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e4 + 10;
vector<pair<int, int>> adj[N];
int n, k, x;
ll dp[2][N][N], knap[2][N];
int sz[N];
void dfs(int u, int p);
int main (int argc, char const *argv[]) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k >> x;
	for(int i = 1, a, b, c; i < n; ++i) {
		cin >> a >> b >> c;
		adj[a].emplace_back(b, c);
		adj[b].emplace_back(a, c);
	}
	dfs(x, 0);
	cout << dp[1][x][k];


	
	return 0;
}
void dfs(int u, int p){
	sz[u] = 1;
	for(auto [v, w] : adj[u]) {
		if(v == p) continue;
		dfs(v, u);
		sz[u] += sz[v];
	}
	for(int i = 0; i <= sz[u]; ++i) knap[0][i] = knap[1][i] = 1e18;
	knap[0][0] = knap[1][0] = 0;
	int knapSize = 0;
	for(auto [v, w] : adj[u]) {
		if(v == p) continue;
		for(int i = knapSize; i >= 0; --i) {
			for(int j = 1; j <= sz[v]; ++j) {
				knap[0][i + j] = min(knap[0][i + j], knap[0][i] + dp[0][v][j] + w*2);
				knap[1][i + j] = min(knap[1][i + j], knap[0][i] + dp[1][v][j] + w);
				knap[1][i + j] = min(knap[1][i + j], knap[1][i] + dp[0][v][j] + w*2);
			}
		}
		knapSize += sz[v];
	}

	for (int i = 0; i < sz[u]; ++i) {
		dp[0][u][i+1] = knap[0][i];
		dp[1][u][i+1] = knap[1][i];
	}
}

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