Submission #952163

#	Time	Username	Problem	Language	Result	Execution time	Memory
952163		vjudge1	Museum (CEOI17_museum)	C++17	100 / 100	552 ms	759060 KiB

museum

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e4 + 1;
struct node { int to, cost; };
vector <node> G[N];
int dp[N][N][2], siz[N];
int n, k, x;
inline void dfs(int u, int fa) {
	siz[u] = 1; dp[u][1][0] = dp[u][1][1] = 0;
	for (auto & e : G[u]) {
		int v = e.to;
		if(v == fa) continue;
		dfs(v, u);
		for (int i = min(k, siz[u]); i >= 0; --i) {
			for (int j = 0; j <= min(k - i, siz[v]); ++j) {
				dp[u][i + j][0] = min(dp[u][i + j][0], dp[u][i][0] + dp[v][j][0] + e.cost * 2);
				dp[u][i + j][1] = min(dp[u][i + j][1], dp[u][i][0] + dp[v][j][1] + e.cost);
				dp[u][i + j][1] = min(dp[u][i + j][1], dp[u][i][1] + dp[v][j][0] + e.cost * 2);
			}
		}
		siz[u] += siz[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 = 0; i <= n; ++i)
		for	(int j = 0; j <= k; ++j)
			dp[i][j][0] = dp[i][j][1] = 1e8;
	dfs(x, -1);
	printf("%d", min(dp[x][k][0], dp[x][k][1]));
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 35 / 35
• Subtask 4: 20 / 20