oj.uz

Submission #292047

# Submission time Handle Problem Language Result Execution time Memory
292047 2020-09-06T08:33:39 Z shivensinha4 Museum (CEOI17_museum) C++17
100 / 100
 368 ms 220808 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 = 10001;
int n, k;
vector<vector<pair<int, int>>> adj;
int dp[MXN][2][MXN];
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 0 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 0 ms 512 KB Output is correct
5 Correct 0 ms 512 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 84176 KB Output is correct
2 Correct 206 ms 84384 KB Output is correct
3 Correct 348 ms 215456 KB Output is correct
4 Correct 258 ms 124984 KB Output is correct
5 Correct 216 ms 92664 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 84176 KB Output is correct
2 Correct 206 ms 84384 KB Output is correct
3 Correct 348 ms 215456 KB Output is correct
4 Correct 258 ms 124984 KB Output is correct
5 Correct 216 ms 92664 KB Output is correct
6 Correct 201 ms 83448 KB Output is correct
7 Correct 295 ms 160760 KB Output is correct
8 Correct 262 ms 82680 KB Output is correct
9 Correct 235 ms 82808 KB Output is correct
10 Correct 214 ms 83320 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 0 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 0 ms 512 KB Output is correct
5 Correct 0 ms 512 KB Output is correct
6 Correct 230 ms 84176 KB Output is correct
7 Correct 206 ms 84384 KB Output is correct
8 Correct 348 ms 215456 KB Output is correct
9 Correct 258 ms 124984 KB Output is correct
10 Correct 216 ms 92664 KB Output is correct
11 Correct 201 ms 83448 KB Output is correct
12 Correct 295 ms 160760 KB Output is correct
13 Correct 262 ms 82680 KB Output is correct
14 Correct 235 ms 82808 KB Output is correct
15 Correct 214 ms 83320 KB Output is correct
16 Correct 212 ms 84728 KB Output is correct
17 Correct 206 ms 84472 KB Output is correct
18 Correct 261 ms 134776 KB Output is correct
19 Correct 240 ms 82680 KB Output is correct
20 Correct 201 ms 83576 KB Output is correct
21 Correct 283 ms 157560 KB Output is correct
22 Correct 207 ms 84400 KB Output is correct
23 Correct 243 ms 82680 KB Output is correct
24 Correct 206 ms 83420 KB Output is correct
25 Correct 368 ms 220808 KB Output is correct