oj.uz

Submission #952137

# Submission time Handle Problem Language Result Execution time Memory
952137 2024-03-23T06:34:45 Z vjudge1 Museum (CEOI17_museum) C++17
100 / 100
 535 ms 784840 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 1e4 + 2;
int n, k, x;
int dp[N][N][2], son[N];
vector<pii> g[N];
void dfs(int u, int fa) {
	son[u] = 1;
	dp[u][1][0] = dp[u][1][1] = 0;
	for (pii f : g[u]) {
		int v = f.first, w = f.second;
		if (v == fa) continue;
		dfs(v, u);
		for (int i = min(son[u], k); i >= 0; i--) {
			for (int j = 0; j <= min(son[v], k - i); j++) {
				dp[u][i + j][0] = min(dp[u][i + j][0], dp[u][i][0] + dp[v][j][0] + w * 2);
				dp[u][i + j][1] = min(dp[u][i + j][1], dp[u][i][0] + dp[v][j][1] + w);
				dp[u][i + j][1] = min(dp[u][i + j][1], dp[u][i][1] + dp[v][j][0] + w * 2);
			}
		}
		son[u] += son[v];
	}
}
int main() {
	scanf("%d%d%d", &n, &k, &x);
	for (int i = 1; i < n; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	memset(dp, 0x3f, sizeof dp);
	dfs(x, -1);
	printf("%d\n", min(dp[x][k][0], dp[x][k][1]));
}

Compilation message

museum.cpp: In function 'int main()':
museum.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |  scanf("%d%d%d", &n, &k, &x);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
museum.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |   scanf("%d%d%d", &u, &v, &w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 783740 KB Output is correct
2 Correct 216 ms 783712 KB Output is correct
3 Correct 219 ms 783696 KB Output is correct
4 Correct 224 ms 783720 KB Output is correct
5 Correct 215 ms 783624 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 783968 KB Output is correct
2 Correct 222 ms 784272 KB Output is correct
3 Correct 229 ms 784468 KB Output is correct
4 Correct 230 ms 784644 KB Output is correct
5 Correct 239 ms 784208 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 783968 KB Output is correct
2 Correct 222 ms 784272 KB Output is correct
3 Correct 229 ms 784468 KB Output is correct
4 Correct 230 ms 784644 KB Output is correct
5 Correct 239 ms 784208 KB Output is correct
6 Correct 238 ms 784212 KB Output is correct
7 Correct 237 ms 784324 KB Output is correct
8 Correct 239 ms 784320 KB Output is correct
9 Correct 232 ms 784208 KB Output is correct
10 Correct 233 ms 784212 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 783740 KB Output is correct
2 Correct 216 ms 783712 KB Output is correct
3 Correct 219 ms 783696 KB Output is correct
4 Correct 224 ms 783720 KB Output is correct
5 Correct 215 ms 783624 KB Output is correct
6 Correct 229 ms 783968 KB Output is correct
7 Correct 222 ms 784272 KB Output is correct
8 Correct 229 ms 784468 KB Output is correct
9 Correct 230 ms 784644 KB Output is correct
10 Correct 239 ms 784208 KB Output is correct
11 Correct 238 ms 784212 KB Output is correct
12 Correct 237 ms 784324 KB Output is correct
13 Correct 239 ms 784320 KB Output is correct
14 Correct 232 ms 784208 KB Output is correct
15 Correct 233 ms 784212 KB Output is correct
16 Correct 245 ms 784180 KB Output is correct
17 Correct 311 ms 784296 KB Output is correct
18 Correct 267 ms 784224 KB Output is correct
19 Correct 297 ms 784508 KB Output is correct
20 Correct 256 ms 784212 KB Output is correct
21 Correct 382 ms 784720 KB Output is correct
22 Correct 380 ms 784320 KB Output is correct
23 Correct 535 ms 784356 KB Output is correct
24 Correct 330 ms 784196 KB Output is correct
25 Correct 385 ms 784840 KB Output is correct