oj.uz

Submission #292037

# Submission time Handle Problem Language Result Execution time Memory
292037 2020-09-06T08:29:28 Z shivensinha4 Museum (CEOI17_museum) C++17
100 / 100
 364 ms 220540 KB 
#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'

const int MXN = 10010;
int n, k;
vector<vector<pair<int, int>>> adj;
int dp[MXN+1][2][MXN+1];
int sub[MXN+1];
const int INF = 1e9;

void dfs(int p, int parent) {
	sub[p] = 1;
	dp[p][0][1] = dp[p][1][1] = 0;
	
	for (auto i: adj[p]) if (i.first != parent) {
		dfs(i.first, p);
		for_(j, 1, sub[i.first]+1) dp[p][0][sub[p]+j] = dp[p][1][sub[p]+j] = INF;
		for (int ct = sub[p]; ct >= 0; ct--) for (int t = sub[i.first]; t >= 1; t--) {
			dp[p][1][ct+t] = min(dp[p][1][ct+t], dp[p][1][ct] + dp[i.first][1][t] + 2*i.second);
			dp[p][0][ct+t] = min(dp[p][0][ct+t], dp[p][0][ct] + dp[i.first][1][t] + 2*i.second);
			dp[p][0][ct+t] = min(dp[p][0][ct+t], dp[p][1][ct] + dp[i.first][0][t] + i.second);
		}
		sub[p] += sub[i.first];
	}
}

int main() {
	#ifndef ONLINE_JUDGE
	//freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int x; cin >> n >> k >> x;
	adj.resize(n);
	for_(i, 0, n-1) {
		int a, b, w; cin >> a >> b >> w;
		a -= 1; b -= 1; 
		adj[a].push_back({b, w});
		adj[b].push_back({a, w});
	}
	
	x -= 1;
	dfs(x, x);
	
	cout << dp[x][0][k] << endl;

	return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 84284 KB Output is correct
2 Correct 206 ms 84544 KB Output is correct
3 Correct 355 ms 216060 KB Output is correct
4 Correct 245 ms 125048 KB Output is correct
5 Correct 211 ms 93056 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 84284 KB Output is correct
2 Correct 206 ms 84544 KB Output is correct
3 Correct 355 ms 216060 KB Output is correct
4 Correct 245 ms 125048 KB Output is correct
5 Correct 211 ms 93056 KB Output is correct
6 Correct 205 ms 83704 KB Output is correct
7 Correct 295 ms 161080 KB Output is correct
8 Correct 269 ms 82804 KB Output is correct
9 Correct 240 ms 82936 KB Output is correct
10 Correct 209 ms 83448 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 204 ms 84284 KB Output is correct
7 Correct 206 ms 84544 KB Output is correct
8 Correct 355 ms 216060 KB Output is correct
9 Correct 245 ms 125048 KB Output is correct
10 Correct 211 ms 93056 KB Output is correct
11 Correct 205 ms 83704 KB Output is correct
12 Correct 295 ms 161080 KB Output is correct
13 Correct 269 ms 82804 KB Output is correct
14 Correct 240 ms 82936 KB Output is correct
15 Correct 209 ms 83448 KB Output is correct
16 Correct 202 ms 84856 KB Output is correct
17 Correct 213 ms 84736 KB Output is correct
18 Correct 264 ms 135032 KB Output is correct
19 Correct 246 ms 82808 KB Output is correct
20 Correct 226 ms 83708 KB Output is correct
21 Correct 286 ms 157944 KB Output is correct
22 Correct 213 ms 84408 KB Output is correct
23 Correct 248 ms 82680 KB Output is correct
24 Correct 203 ms 83452 KB Output is correct
25 Correct 364 ms 220540 KB Output is correct