Submission #955159

#	Time	Username	Problem	Language	Result	Execution time	Memory
955159		TAhmed33	Museum (CEOI17_museum)	C++98	100 / 100	672 ms	212712 KiB

museum

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 25;
const int inf = 1e9;
int n, k, x;
vector <pair <int, int>> adj[MAXN];
vector <int> dp[MAXN][2];
vector <int> minimize (vector <int> a, vector <int> b) {
	vector <int> ret(max((int)a.size(), (int)b.size()));
	for (auto &i : ret) i = inf;
	for (int i = 0; i < (int)a.size(); i++) ret[i] = min(ret[i], a[i]);
	for (int i = 0; i < (int)b.size(); i++) ret[i] = min(ret[i], b[i]);
	return ret;
}
vector <int> add (vector <int> x, int a) {
	for (auto &i : x) i += a;
	return x;
}
vector <int> convolve (vector <int> a, vector <int> b) {
	vector <int> ret((int)a.size() + (int)b.size() - 1);
	for (auto &i : ret) i = inf;
	for (int i = 0; i < (int)a.size(); i++) {
		for (int j = 0; j < (int)b.size(); j++) {
			ret[i + j] = min(ret[i + j], a[i] + b[j]);
		}
	}
	return ret;
}
void dfs (int pos, int par) {
	dp[pos][0] = {0, 0};
	dp[pos][1] = {0, 0};
	for (auto j : adj[pos]) {
		if (j.first == par) continue;
		dfs(j.first, pos);
		auto a = dp[pos][0], b = dp[pos][1];
		dp[pos][0] = minimize(a, convolve(a, add(dp[j.first][0], 2 * j.second)));
		dp[pos][1] = minimize(b, minimize(convolve(b, add(dp[j.first][0], 2 * j.second)), convolve(a, add(dp[j.first][1], j.second))));
	}
	/*cout << pos << ": \n";
	for (auto i : dp[pos][0]) cout << i << " ";
	cout << '\n';
	for (auto i : dp[pos][1]) cout << i << " ";
	cout << '\n';
	cout << '\n';*/
}
int main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, k, x; cin >> n >> k >> x;
	for (int i = 1; i < n; i++) {
		int a, b, c; cin >> a >> b >> c;
		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
	}
	dfs(x, -1);
	cout << dp[x][1][k] << '\n';
}

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