Submission #952015

#	Time	Username	Problem	Language	Result	Execution time	Memory
952015		vjudge1	Museum (CEOI17_museum)	C++17	0 / 100	170 ms	392536 KiB

museum

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e4 + 5;
struct node { int to, cost; };
int dp[N][N], siz[N];
vector <node> G[N];
int n, p, x, w[N];
inline void dfs(int u, int fa) {
	siz[u] = 1;
	dp[u][0] = w[u];
	for (auto & e : G[u]) {
		int v = e.to;
		if(v == fa) continue;
		dfs(v, u);
		siz[u] += siz[v];
		for (int i = min(p, siz[u]); i >= 0; --i)
			for (int j = min(i - 1, siz[v]); j >= 0; --j)
				dp[u][i] = min(dp[u][i], dp[v][i - j - 1] + dp[i][j] - e.cost);
	}
}
int main() {
	int sum = 0;
	scanf("%d%d%d", &n, &p, &x);
	for (int i = 1; i < n; ++i) {
		int u, v;
		scanf("%d%d%d", &u, &v, &w[i]);
		G[u].push_back({v, w[i]});
		G[v].push_back({u, w[i]});
		sum += w[i];
	}
	for (int i = 0; i <= n; ++i)
		for (int j = 0; j <= n; ++j)
			dp[i][j] = 1e9;
	dfs(1, 0);
	printf("%d", sum - abs(dp[x][p - 1]));
	return 0;
}

Compilation message (stderr)

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

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