Submission #951999

#	Time	Username	Problem	Language	Result	Execution time	Memory
951999		vjudge1	Museum (CEOI17_museum)	C++17	80 / 100	3043 ms	757328 KiB

museum

#include<bits/stdc++.h>
using namespace std;
#define N 10005
#define son v.first
#define len v.second
inline int read(){
	int re=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-'){
			f=-1;
		}
		ch=getchar();
	}
	while(isdigit(ch)){
		re=re*10+ch-'0';
		ch=getchar();
	}
	return re*f;
}
int dp[N][N][2];
int n,p,Son[N],rt;
vector<pair<int,int>> G[N];
inline void dfs(int now,int fa){
	dp[now][1][1]=dp[now][1][0]=0;
	Son[now]=1;
	for(auto&v:G[now]){
		if(son!=fa){
			dfs(son,now);
			Son[now]+=Son[son];
			for(int i=min(p,Son[now]);i>0;i--){
				if(i-1<=Son[son]){
					dp[now][i][1]=min(dp[now][i][1],dp[son][i-1][1]+len);
					dp[now][i][0]=min(dp[now][i][0],dp[son][i-1][0]+2*len);					
				}
				for(int j=min({p,Son[son],i});j>=0;j--){
					dp[now][i][0]=min(dp[now][i][0],dp[now][i-j][0]+dp[son][j][0]+2*len);
					dp[now][i][1]=min(dp[now][i][1],dp[now][i-j][0]+dp[son][j][1]+len);
					dp[now][i][1]=min(dp[now][i][1],dp[now][i-j][1]+dp[son][j][0]+2*len);
				}				
			}		
		}
	}
}
signed main(){
	n=read();p=read();rt=read();
	for(int i=1,x,y,z;i<n;i++){
		x=read();y=read();z=read();
		G[x].push_back(make_pair(y,z));
		G[y].push_back(make_pair(x,z));
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<=p;j++){
			dp[i][j][1]=dp[i][j][0]=1e9;
		}
	}
	dfs(rt,0);
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=p;j++){
//			cout<<i<<" visit "<<j<<" :"<<dp[i][j][0]<<" "<<dp[i][j][1]<<endl;
//		}
//	}
	printf("%d",min(dp[rt][p][1],dp[rt][p][0]));
} 

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