Submission #1209280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209280		vijay30046	Museum (CEOI17_museum)	C++17	100 / 100	360 ms	310408 KiB

museum

#include <bits/stdc++.h>
using namespace std;
#define int long long

using ll = long long;
using vi = vector<int>;
#define all(x) x.begin(), x.end()
#define pb push_back
#define pii pair<int,int>
#define vii vector<pair<int,int>>
#define MOD 1000000007
// #define INF 1e9
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define trav(a,x) for (auto& a: x)

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("O2")
#pragma GCC optimization ("unroll-loops")

void start() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
}

const int N = 10001;
const int INF = 1e15;
vector<pair<int, int>> g[N];
vector<int> dp[N][2];
int n, k, x;

void process(int node, int par) {
	dp[node][0] = {INF, 0};
	dp[node][1] = {INF, 0};
	for (pair<int, int> edge : g[node]) {
		int child = edge.first;
		int len = edge.second;
		if (child == par)continue;
		process(child, node);
		int a = (int)dp[node][0].size();
		int b = (int)dp[child][0].size();
		vector<int> combined(a + b - 1, INF);
		for (int i = 1; i < a; i++) {
			combined[i] = dp[node][1][i];
		}
		for (int i = 1; i < a; i++) {
			for (int j = 1; j < b; j++) {
				combined[i + j] = min(combined[i + j], dp[node][1][i] + dp[child][0][j] + 2 * len);
				combined[i + j] = min(combined[i + j], dp[node][0][i] + dp[child][1][j] + len);
			}
		}
		dp[node][1] = combined;
		combined.assign(a + b - 1, INF);
		for (int i = 1; i < a; i++) {
			combined[i] = dp[node][0][i];
		}
		for (int i = 1; i < a; i++) {
			for (int j = 1; j < b; j++) {
				combined[i + j] = min(combined[i + j], dp[node][0][i] + dp[child][0][j] + 2 * len);
			}
		}
		dp[node][0] = combined;
	}
}

void solve() {
	cin >> n >> k >> x;
	for (int i = 1; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		g[a].pb({b, c});
		g[b].pb({a, c});
	}
	process(x, 0);
	int ans = dp[x][1][k];
	cout << ans << "\n";
}

int32_t main() {
	start();
	int test = 1;
	//cin >> test;
	for (int i = 1; i <= test; i++) {
		//cout << "Case #" << i << ": ";
		solve();
	}
	return 0;
}

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