oj.uz

Submission #955159

# Submission time Handle Problem Language Result Execution time Memory
955159 2024-03-29T14:05:32 Z TAhmed33 Museum (CEOI17_museum) C++
100 / 100
 672 ms 212712 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 4560 KB Output is correct
2 Correct 123 ms 5212 KB Output is correct
3 Correct 414 ms 212712 KB Output is correct
4 Correct 205 ms 64600 KB Output is correct
5 Correct 140 ms 15196 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 4560 KB Output is correct
2 Correct 123 ms 5212 KB Output is correct
3 Correct 414 ms 212712 KB Output is correct
4 Correct 205 ms 64600 KB Output is correct
5 Correct 140 ms 15196 KB Output is correct
6 Correct 124 ms 3928 KB Output is correct
7 Correct 289 ms 120316 KB Output is correct
8 Correct 672 ms 3564 KB Output is correct
9 Correct 475 ms 3188 KB Output is correct
10 Correct 188 ms 4108 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 123 ms 4560 KB Output is correct
7 Correct 123 ms 5212 KB Output is correct
8 Correct 414 ms 212712 KB Output is correct
9 Correct 205 ms 64600 KB Output is correct
10 Correct 140 ms 15196 KB Output is correct
11 Correct 124 ms 3928 KB Output is correct
12 Correct 289 ms 120316 KB Output is correct
13 Correct 672 ms 3564 KB Output is correct
14 Correct 475 ms 3188 KB Output is correct
15 Correct 188 ms 4108 KB Output is correct
16 Correct 123 ms 5556 KB Output is correct
17 Correct 123 ms 5204 KB Output is correct
18 Correct 225 ms 78672 KB Output is correct
19 Correct 507 ms 3156 KB Output is correct
20 Correct 140 ms 4336 KB Output is correct
21 Correct 272 ms 112328 KB Output is correct
22 Correct 126 ms 4948 KB Output is correct
23 Correct 507 ms 3352 KB Output is correct
24 Correct 139 ms 4116 KB Output is correct
25 Correct 397 ms 206840 KB Output is correct