oj.uz

Submission #952016

# Submission time Handle Problem Language Result Execution time Memory
952016 2024-03-23T03:46:37 Z vjudge1 Museum (CEOI17_museum) C++17
0 / 100
 116 ms 392532 KB 
#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

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.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 35.0

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

Subtask #4
0 / 20.0

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