oj.uz

Submission #492808

# Submission time Handle Problem Language Result Execution time Memory
492808 2021-12-09T02:48:05 Z ntabc05101 Museum (CEOI17_museum) C++14
80 / 100
 499 ms 1048580 KB 
#include<bits/stdc++.h>
using namespace std;

#define taskname ""

const long long inf = 1e18;
const int mxN = 10002;

int n, k, x;
vector< pair<int, int> > adj[mxN];
int sz[mxN];
long long 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 33 ms 59384 KB Output is correct
2 Correct 30 ms 59464 KB Output is correct
3 Correct 33 ms 59816 KB Output is correct
4 Correct 34 ms 59204 KB Output is correct
5 Correct 38 ms 59152 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 59384 KB Output is correct
2 Correct 30 ms 59464 KB Output is correct
3 Correct 33 ms 59816 KB Output is correct
4 Correct 34 ms 59204 KB Output is correct
5 Correct 38 ms 59152 KB Output is correct
6 Correct 34 ms 59448 KB Output is correct
7 Correct 36 ms 59648 KB Output is correct
8 Correct 33 ms 59468 KB Output is correct
9 Correct 40 ms 59404 KB Output is correct
10 Correct 34 ms 59416 KB Output is correct

Subtask #4
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 33 ms 59384 KB Output is correct
7 Correct 30 ms 59464 KB Output is correct
8 Correct 33 ms 59816 KB Output is correct
9 Correct 34 ms 59204 KB Output is correct
10 Correct 38 ms 59152 KB Output is correct
11 Correct 34 ms 59448 KB Output is correct
12 Correct 36 ms 59648 KB Output is correct
13 Correct 33 ms 59468 KB Output is correct
14 Correct 40 ms 59404 KB Output is correct
15 Correct 34 ms 59416 KB Output is correct
16 Correct 106 ms 199988 KB Output is correct
17 Correct 423 ms 825176 KB Output is correct
18 Correct 119 ms 200188 KB Output is correct
19 Correct 135 ms 200092 KB Output is correct
20 Correct 113 ms 200052 KB Output is correct
21 Runtime error 499 ms 1048580 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -