oj.uz

Submission #253559

# Submission time Handle Problem Language Result Execution time Memory
253559 2020-07-28T09:52:13 Z super_j6 Museum (CEOI17_museum) C++14
100 / 100
 851 ms 784632 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second
 
const int inf = 0x3f3f3f3f;
const int mxn = 10001;
int n, k, x;
int sz[mxn];
int dp[mxn][mxn][2];
vector<pi> g[mxn];
 
void dfs(int c, int p){
	sz[c] = 1;
	memset(dp[c], inf, sizeof(dp[c]));
	dp[c][1][0] = dp[c][1][1] = 0;
	for(pi i : g[c]){
		if(i.f == p) continue;
		dfs(i.f, c);
		for(int j = min(k, sz[c] + sz[i.f]); j; j--){
			int ret[2] = {inf, inf};
			for(int l = max(1, j - sz[c]); l <= min(j, sz[i.f]); l++)
			for(int p1 = 0; p1 < 2; p1++)
			for(int p2 = 0; p2 < 2 - p1; p2++){
				ret[p1 | p2] = min(ret[p1 | p2], dp[c][j - l][p1] + dp[i.f][l][p2] + (1 + !p2) * i.s); 
			}
			for(int l = 0; l < 2; l++){
				dp[c][j][l] = min(dp[c][j][l], ret[l]);
			}
		}
		sz[c] += sz[i.f];
	}
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k >> x;
	x--;
	
	for(int i = 0; i < n - 1; i++){
		int u, v, w;
		cin >> u >> v >> w;
		u--, v--;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	
	dfs(x, -1);
	
	cout << dp[x][k][1] << endl;
 
	return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 784044 KB Output is correct
2 Correct 411 ms 783864 KB Output is correct
3 Correct 430 ms 784268 KB Output is correct
4 Correct 411 ms 784028 KB Output is correct
5 Correct 440 ms 783864 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 784044 KB Output is correct
2 Correct 411 ms 783864 KB Output is correct
3 Correct 430 ms 784268 KB Output is correct
4 Correct 411 ms 784028 KB Output is correct
5 Correct 440 ms 783864 KB Output is correct
6 Correct 422 ms 783916 KB Output is correct
7 Correct 435 ms 784120 KB Output is correct
8 Correct 445 ms 783864 KB Output is correct
9 Correct 438 ms 783992 KB Output is correct
10 Correct 421 ms 784068 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2176 KB Output is correct
2 Correct 1 ms 2176 KB Output is correct
3 Correct 2 ms 2176 KB Output is correct
4 Correct 2 ms 2176 KB Output is correct
5 Correct 1 ms 2176 KB Output is correct
6 Correct 476 ms 784044 KB Output is correct
7 Correct 411 ms 783864 KB Output is correct
8 Correct 430 ms 784268 KB Output is correct
9 Correct 411 ms 784028 KB Output is correct
10 Correct 440 ms 783864 KB Output is correct
11 Correct 422 ms 783916 KB Output is correct
12 Correct 435 ms 784120 KB Output is correct
13 Correct 445 ms 783864 KB Output is correct
14 Correct 438 ms 783992 KB Output is correct
15 Correct 421 ms 784068 KB Output is correct
16 Correct 473 ms 784064 KB Output is correct
17 Correct 632 ms 784120 KB Output is correct
18 Correct 495 ms 784248 KB Output is correct
19 Correct 526 ms 784124 KB Output is correct
20 Correct 464 ms 783992 KB Output is correct
21 Correct 759 ms 784376 KB Output is correct
22 Correct 679 ms 783964 KB Output is correct
23 Correct 851 ms 784024 KB Output is correct
24 Correct 686 ms 784092 KB Output is correct
25 Correct 811 ms 784632 KB Output is correct