oj.uz

Submission #253424

# Submission time Handle Problem Language Result Execution time Memory
253424 2020-07-28T04:10:30 Z super_j6 Museum (CEOI17_museum) C++14
80 / 100
 3000 ms 784504 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);
	}
	sort(g[c].begin(), g[c].end(), [&](pi x, pi y){
		return sz[x.f] < sz[y.f];	
	});
	for(pi i : g[c]){
		if(i.f == p) continue;
		sz[c] += sz[i.f];
		for(int j = min(k, sz[c]); ~j; j--){
			int ret[2] = {inf, inf};
			for(int l = 0; 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]);
			}
		}
	}
}
 
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 2 ms 2176 KB Output is correct
4 Correct 1 ms 2120 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 433 ms 783820 KB Output is correct
2 Correct 400 ms 784120 KB Output is correct
3 Correct 485 ms 784504 KB Output is correct
4 Correct 442 ms 784248 KB Output is correct
5 Correct 424 ms 783996 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 783820 KB Output is correct
2 Correct 400 ms 784120 KB Output is correct
3 Correct 485 ms 784504 KB Output is correct
4 Correct 442 ms 784248 KB Output is correct
5 Correct 424 ms 783996 KB Output is correct
6 Correct 425 ms 784136 KB Output is correct
7 Correct 485 ms 784248 KB Output is correct
8 Correct 400 ms 784228 KB Output is correct
9 Correct 412 ms 784120 KB Output is correct
10 Correct 420 ms 784076 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 2 ms 2176 KB Output is correct
4 Correct 1 ms 2120 KB Output is correct
5 Correct 1 ms 2176 KB Output is correct
6 Correct 433 ms 783820 KB Output is correct
7 Correct 400 ms 784120 KB Output is correct
8 Correct 485 ms 784504 KB Output is correct
9 Correct 442 ms 784248 KB Output is correct
10 Correct 424 ms 783996 KB Output is correct
11 Correct 425 ms 784136 KB Output is correct
12 Correct 485 ms 784248 KB Output is correct
13 Correct 400 ms 784228 KB Output is correct
14 Correct 412 ms 784120 KB Output is correct
15 Correct 420 ms 784076 KB Output is correct
16 Correct 563 ms 783988 KB Output is correct
17 Correct 1631 ms 784092 KB Output is correct
18 Execution timed out 3111 ms 575588 KB Time limit exceeded
19 Halted 0 ms 0 KB -