oj.uz

Submission #253407

# Submission time Handle Problem Language Result Execution time Memory
253407 2020-07-28T02:23:34 Z super_j6 Museum (CEOI17_museum) C++14
80 / 100
 3000 ms 784376 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 dp[mxn][mxn][2];
vector<pi> g[mxn];
 
void dfs(int c, int p){
	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 = k; ~j; j--){
			int ret[2] = {inf, inf};
			for(int l = 0; l <= j; 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]);
			}
		}
	}
}
 
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 2 ms 2176 KB Output is correct
2 Correct 1 ms 2176 KB Output is correct
3 Correct 1 ms 2176 KB Output is correct
4 Correct 1 ms 2176 KB Output is correct
5 Correct 2 ms 2176 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 652 ms 784028 KB Output is correct
2 Correct 644 ms 783928 KB Output is correct
3 Correct 648 ms 784376 KB Output is correct
4 Correct 657 ms 784248 KB Output is correct
5 Correct 654 ms 783992 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 652 ms 784028 KB Output is correct
2 Correct 644 ms 783928 KB Output is correct
3 Correct 648 ms 784376 KB Output is correct
4 Correct 657 ms 784248 KB Output is correct
5 Correct 654 ms 783992 KB Output is correct
6 Correct 682 ms 784052 KB Output is correct
7 Correct 649 ms 784248 KB Output is correct
8 Correct 652 ms 783992 KB Output is correct
9 Correct 651 ms 784192 KB Output is correct
10 Correct 653 ms 784036 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2176 KB Output is correct
2 Correct 1 ms 2176 KB Output is correct
3 Correct 1 ms 2176 KB Output is correct
4 Correct 1 ms 2176 KB Output is correct
5 Correct 2 ms 2176 KB Output is correct
6 Correct 652 ms 784028 KB Output is correct
7 Correct 644 ms 783928 KB Output is correct
8 Correct 648 ms 784376 KB Output is correct
9 Correct 657 ms 784248 KB Output is correct
10 Correct 654 ms 783992 KB Output is correct
11 Correct 682 ms 784052 KB Output is correct
12 Correct 649 ms 784248 KB Output is correct
13 Correct 652 ms 783992 KB Output is correct
14 Correct 651 ms 784192 KB Output is correct
15 Correct 653 ms 784036 KB Output is correct
16 Execution timed out 3098 ms 105548 KB Time limit exceeded
17 Halted 0 ms 0 KB -