oj.uz

Submission #253397

# Submission time Handle Problem Language Result Execution time Memory
253397 2020-07-27T22:35:49 Z super_j6 Museum (CEOI17_museum) C++14
80 / 100
 3000 ms 784248 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++){
				ret[0] = min(ret[0], dp[c][j - l][0] + dp[i.f][l][0] + 2 * i.s);
				ret[1] = min(ret[1], dp[c][j - l][1] + dp[i.f][l][0] + 2 * i.s);
				ret[1] = min(ret[1], dp[c][j - l][0] + dp[i.f][l][1] + 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 1 ms 2176 KB Output is correct
2 Correct 2 ms 2176 KB Output is correct
3 Correct 1 ms 2176 KB Output is correct
4 Correct 2 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 619 ms 784100 KB Output is correct
2 Correct 579 ms 783992 KB Output is correct
3 Correct 583 ms 784248 KB Output is correct
4 Correct 574 ms 784008 KB Output is correct
5 Correct 544 ms 784200 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 784100 KB Output is correct
2 Correct 579 ms 783992 KB Output is correct
3 Correct 583 ms 784248 KB Output is correct
4 Correct 574 ms 784008 KB Output is correct
5 Correct 544 ms 784200 KB Output is correct
6 Correct 531 ms 783980 KB Output is correct
7 Correct 527 ms 784248 KB Output is correct
8 Correct 521 ms 783992 KB Output is correct
9 Correct 525 ms 783992 KB Output is correct
10 Correct 543 ms 784080 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2176 KB Output is correct
2 Correct 2 ms 2176 KB Output is correct
3 Correct 1 ms 2176 KB Output is correct
4 Correct 2 ms 2176 KB Output is correct
5 Correct 2 ms 2176 KB Output is correct
6 Correct 619 ms 784100 KB Output is correct
7 Correct 579 ms 783992 KB Output is correct
8 Correct 583 ms 784248 KB Output is correct
9 Correct 574 ms 784008 KB Output is correct
10 Correct 544 ms 784200 KB Output is correct
11 Correct 531 ms 783980 KB Output is correct
12 Correct 527 ms 784248 KB Output is correct
13 Correct 521 ms 783992 KB Output is correct
14 Correct 525 ms 783992 KB Output is correct
15 Correct 543 ms 784080 KB Output is correct
16 Execution timed out 3108 ms 217740 KB Time limit exceeded
17 Halted 0 ms 0 KB -