Submission #952157

#	Time	Username	Problem	Language	Result	Execution time	Memory
952157		vjudge1	Museum (CEOI17_museum)	C++14	100 / 100	501 ms	784980 KiB

museum

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
const int N=1e4+5;
int n,k,x,son[N];
int dp[N][N][2];
vector<pair<int,int> >g[N];
inline int read(){
   int x=0,f=1;
   char ch=getchar();
   while(ch < '0' || ch > '9'){
        if(ch=='-') f = -1;
        ch = getchar();
   }
   while(ch >='0' && ch <= '9'){
        x = (x<<3) + (x<<1) + ch - '0';
        ch = getchar();
   }
   return x*f;
}
inline void dfs(int u,int fa){
	dp[u][1][0]=dp[u][1][1]=0;
	son[u]=1;
	for(auto v:g[u]){
		if(v.first==fa)continue;
		dfs(v.first,u);
		int mxi=min(k,son[u]);
		for(int i=mxi;i>=0;i--){
			int mxj=min(k-i,son[v.first]);
			for(int j=mxj;j>=0;j--){
				if(dp[u][i][0]+dp[v.first][j][0]+v.second*2>=0)dp[u][i+j][0]=min(dp[u][i+j][0],dp[u][i][0]+dp[v.first][j][0]+v.second*2);
				if(dp[u][i][0]+dp[v.first][j][1]+v.second>=0)dp[u][i+j][1]=min(dp[u][i+j][1],dp[u][i][0]+dp[v.first][j][1]+v.second);
				if(dp[u][i][1]+dp[v.first][j][0]+v.second*2>=0)dp[u][i+j][1]=min(dp[u][i+j][1],dp[u][i][1]+dp[v.first][j][0]+v.second*2);
			}
		}
		son[u]+=son[v.first];
	}
}
int main(){
	memset(dp,0x7f,sizeof dp);
	n=read();
	k=read();
	x=read();
	for(int i=1,a,b,c;i<n;i++){
		a=read();
		b=read();
		c=read();
		g[a].push_back({b,c});
		g[b].push_back({a,c});
	}
	dfs(x,-1);
	cout<<min(dp[x][k][0],dp[x][k][1]);
} 

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