oj.uz

Submission #952111

# Submission time Handle Problem Language Result Execution time Memory
952111 2024-03-23T06:07:22 Z vjudge1 Museum (CEOI17_museum) C++17
0 / 100
 63 ms 217684 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] + 3, k); i >= 0; i--) {
			for (int j = 0; j <= min(son[v] + 3, i); j++) {
				dp[u][i][0] = min(dp[u][i][0], dp[u][i - j][0] + dp[v][j][0] + w * 2);
				dp[u][i][1] = min(dp[u][i][1], dp[u][i - j][0] + dp[v][j][1] + w);
				dp[u][i][1] = min(dp[u][i][1], dp[u][i - j][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});
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= k; j++) {
			dp[i][j][0] = dp[i][j][1] = 0x3f3f3f3f;
		}
	}
	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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2656 KB Output is correct
2 Incorrect 1 ms 2648 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 217684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 217684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2656 KB Output is correct
2 Incorrect 1 ms 2648 KB Output isn't correct
3 Halted 0 ms 0 KB -