oj.uz

Submission #492812

# Submission time Handle Problem Language Result Execution time Memory
492812 2021-12-09T02:50:39 Z ntabc05101 Museum (CEOI17_museum) C++14
100 / 100
 603 ms 746048 KB 
#include<bits/stdc++.h>
using namespace std;

#define taskname ""

const int inf = 1e9 + 9;
const int mxN = 10002;

int n, k, x;
vector< pair<int, int> > adj[mxN];
int sz[mxN];
int dp[mxN][mxN][2];

void dfs(int u, int p = -1) {
	sz[u] = 1;
	for (int i = 2; i <= k; i++) {
		dp[u][i][0] = dp[u][i][1] = inf;
	}
	for (auto &to: adj[u]) {
		if (to.first != p) {
			dfs(to.first, u);
			for (int i = min(sz[u] + sz[to.first], k); i > 1; i--) {
				for (int j = min(sz[to.first] , i - 1); j >= max(1, i - sz[u]); j--) {
					dp[u][i][1] = min({dp[u][i][1], dp[u][i - j][1] + dp[to.first][j][0] + (to.second << 1), dp[u][i - j][0] + dp[to.first][j][1] + to.second});
					dp[u][i][0] = min({dp[u][i][0], dp[u][i - j][0] + dp[to.first][j][0] + (to.second << 1)});
				}
			}
			sz[u] += sz[to.first];
		}
	}
}

int main() {
	if (fopen(taskname".inp", "r")) {
		freopen(taskname".inp", "r", stdin);
		freopen(taskname".out", "w", stdout);
	}
	else {
		if (fopen(taskname".in", "r")) {
			freopen(taskname".in", "r", stdin);
			freopen(taskname".out", "w", stdout);
		}
	}

	cin.tie(0)->sync_with_stdio(0);

	cin >> n >> k >> x; x--;
	for (int i = 0, x, y, w; i < n - 1; i++) {
		cin >> x >> y >> w; x--; y--;
		adj[x].push_back({y, w});
		adj[y].push_back({x, w});
	}

	dfs(x);

	cout << dp[x][k][1] << "\n";

	return 0;
}

Compilation message

museum.cpp: In function 'int main()':
museum.cpp:35:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |   freopen(taskname".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:36:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |   freopen(taskname".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:40:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |    freopen(taskname".in", "r", stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:41:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |    freopen(taskname".out", "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 50052 KB Output is correct
2 Correct 30 ms 50280 KB Output is correct
3 Correct 34 ms 50552 KB Output is correct
4 Correct 37 ms 50152 KB Output is correct
5 Correct 45 ms 50116 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 50052 KB Output is correct
2 Correct 30 ms 50280 KB Output is correct
3 Correct 34 ms 50552 KB Output is correct
4 Correct 37 ms 50152 KB Output is correct
5 Correct 45 ms 50116 KB Output is correct
6 Correct 37 ms 50256 KB Output is correct
7 Correct 37 ms 50464 KB Output is correct
8 Correct 36 ms 50196 KB Output is correct
9 Correct 36 ms 50244 KB Output is correct
10 Correct 32 ms 50244 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 29 ms 50052 KB Output is correct
7 Correct 30 ms 50280 KB Output is correct
8 Correct 34 ms 50552 KB Output is correct
9 Correct 37 ms 50152 KB Output is correct
10 Correct 45 ms 50116 KB Output is correct
11 Correct 37 ms 50256 KB Output is correct
12 Correct 37 ms 50464 KB Output is correct
13 Correct 36 ms 50196 KB Output is correct
14 Correct 36 ms 50244 KB Output is correct
15 Correct 32 ms 50244 KB Output is correct
16 Correct 133 ms 120520 KB Output is correct
17 Correct 365 ms 433016 KB Output is correct
18 Correct 112 ms 120652 KB Output is correct
19 Correct 116 ms 120508 KB Output is correct
20 Correct 102 ms 120488 KB Output is correct
21 Correct 543 ms 745716 KB Output is correct
22 Correct 553 ms 745640 KB Output is correct
23 Correct 603 ms 745512 KB Output is correct
24 Correct 526 ms 745716 KB Output is correct
25 Correct 570 ms 746048 KB Output is correct