Submission #952009

#	Time	Username	Problem	Language	Result	Execution time	Memory
952009		vjudge1	Museum (CEOI17_museum)	C++14	80 / 100	3052 ms	756836 KiB

museum

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int n, k, x;
int dp[N][N][2];
int son[N];
vector<pair<int, int>> G[N];
void dfs(int fa, int u){
	son[u] = 1;
	dp[u][0][0] = dp[u][1][0] = dp[u][1][1] = dp[u][0][1] = 0;
	for(auto e : G[u]){
		int v = e.first;
		int w = e.second;
		if(v == fa) continue;
		dfs(u, v);
		son[u] += son[v];
		for(int i = min(son[u], k); i >= 0; i--){
			for(int j = 0; j <= min(i, son[v]); j++){
				dp[u][i][0] = min(dp[u][i - j][0] + dp[v][j][0] + 2 * w, dp[u][i][0]);
				dp[u][i][1] = min(dp[u][i - j][1] + dp[v][j][0] + w * 2, dp[u][i][1]);
				dp[u][i][1] = min(dp[u][i - j][0] + dp[v][j][1] + w, dp[u][i][1]);
			}
		}
	}
}
int main(){
//	freopen("museum.in","r", stdin);
//	freopen("museum.out","w", stdout);
	scanf("%d %d %d", &n, &k, &x);
	for(int i = 1; i < n; i++){
		int x, y ,z;
		scanf("%d %d %d", &x, &y, &z);
		G[x].push_back({y, z});
		G[y].push_back({x, z});
	}
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= k; j++){
			dp[i][j][1] = dp[i][j][0] = 1e9;	
		}
	}
	dfs(0, x);
	printf("%d", dp[x][k][1]);
} 

Compilation message (stderr)

museum.cpp: In function 'int main()':
museum.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |  scanf("%d %d %d", &n, &k, &x);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   scanf("%d %d %d", &x, &y, &z);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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