Submission #952151

#	Time	Username	Problem	Language	Result	Execution time	Memory
952151		vjudge1	Museum (CEOI17_museum)	C++14	100 / 100	535 ms	784976 KiB

museum

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
struct edge{
	int to,w;
};
int dp[N][N][2],son[N];
vector<edge>G[N];
int n,k,x;
inline void dfs(int u,int fa){
	son[u]=1;
	dp[u][1][1]=dp[u][1][0]=0;
	for(auto v:G[u]){
		if(v.to==fa) continue;
		dfs(v.to,u);
		for(int i=min(k,son[u]);i>=0;i--)
			for(int j=min(k-i,son[v.to]);j>=0;j--){
				dp[u][i+j][1]=min(dp[u][i+j][1],dp[u][i][1]+dp[v.to][j][1]+v.w*2);
				dp[u][i+j][0]=min(dp[u][i+j][0],dp[u][i][1]+dp[v.to][j][0]+v.w);
				dp[u][i+j][0]=min(dp[u][i+j][0],dp[u][i][0]+dp[v.to][j][1]+v.w*2);
			}
		son[u]+=son[v.to];
	}
}
int main(){
//	freopen("museum.in","r",stdin);
//	freopen("museum.out","w",stdout);
	memset(dp,0x3f,sizeof dp);
	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});
	}
	dfs(x,0);
	printf("%d",min(dp[x][k][1],dp[x][k][0]));
	return 0;
}

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:31:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   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