oj.uz

Submission #1100632

# Submission time Handle Problem Language Result Execution time Memory
1100632 2024-10-14T10:59:33 Z vjudge1 Museum (CEOI17_museum) C++17
100 / 100
 449 ms 748620 KB 
#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.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 505172 KB Output is correct
2 Correct 160 ms 515596 KB Output is correct
3 Correct 449 ms 711792 KB Output is correct
4 Correct 247 ms 623692 KB Output is correct
5 Correct 190 ms 581840 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 505172 KB Output is correct
2 Correct 160 ms 515596 KB Output is correct
3 Correct 449 ms 711792 KB Output is correct
4 Correct 247 ms 623692 KB Output is correct
5 Correct 190 ms 581840 KB Output is correct
6 Correct 163 ms 527692 KB Output is correct
7 Correct 324 ms 681524 KB Output is correct
8 Correct 357 ms 8392 KB Output is correct
9 Correct 253 ms 8684 KB Output is correct
10 Correct 119 ms 42828 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4692 KB Output is correct
2 Correct 2 ms 4692 KB Output is correct
3 Correct 1 ms 4692 KB Output is correct
4 Correct 1 ms 4692 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 167 ms 505172 KB Output is correct
7 Correct 160 ms 515596 KB Output is correct
8 Correct 449 ms 711792 KB Output is correct
9 Correct 247 ms 623692 KB Output is correct
10 Correct 190 ms 581840 KB Output is correct
11 Correct 163 ms 527692 KB Output is correct
12 Correct 324 ms 681524 KB Output is correct
13 Correct 357 ms 8392 KB Output is correct
14 Correct 253 ms 8684 KB Output is correct
15 Correct 119 ms 42828 KB Output is correct
16 Correct 158 ms 567796 KB Output is correct
17 Correct 170 ms 574540 KB Output is correct
18 Correct 244 ms 619084 KB Output is correct
19 Correct 289 ms 8524 KB Output is correct
20 Correct 113 ms 67408 KB Output is correct
21 Correct 293 ms 640268 KB Output is correct
22 Correct 193 ms 539468 KB Output is correct
23 Correct 284 ms 8644 KB Output is correct
24 Correct 111 ms 56908 KB Output is correct
25 Correct 407 ms 748620 KB Output is correct