Submission #952137

#	Time	Username	Problem	Language	Result	Execution time	Memory
952137		vjudge1	Museum (CEOI17_museum)	C++17	100 / 100	535 ms	784840 KiB

museum

#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 (stderr)

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 / 20
• Subtask 2: 25 / 25
• Subtask 3: 35 / 35
• Subtask 4: 20 / 20