Submission #1209634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209634		PieArmy	Museum (CEOI17_museum)	C++20	80 / 100	3097 ms	96816 KiB

museum

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;

const int inf=1e9;

int n,k,root;
vector<pair<int,int>>komsu[10023];
int dp[10023][2][10023];
int sub[10023];

void dfs(int pos,int par,int val){
	int m=0;
	for(auto[x,c]:komsu[pos]){
		if(x==par)continue;
		dfs(x,pos,c);
		sub[pos]+=sub[x];
		int m2=m;
		m=min(sub[pos],k);
		for(int i=m2+1;i<=m;i++){
			dp[pos][0][i]=dp[pos][1][i]=inf;
		}
		for(int i=m-1;i>=0;i--){
			for(int j=min(m-i,min(sub[x],k));j>=1;j--){
				dp[pos][0][i+j]=min(dp[pos][0][i+j],dp[pos][0][i]+dp[x][0][j]);
				dp[pos][1][i+j]=min(dp[pos][1][i+j],dp[pos][1][i]+dp[x][0][j]);
				dp[pos][1][i+j]=min(dp[pos][1][i+j],dp[pos][0][i]+dp[x][1][j]);
			}
		}
	}
	sub[pos]++;
	m=min(sub[pos],k);
	for(int i=m;i>=1;i--){
		dp[pos][0][i]=dp[pos][0][i-1]+val*2;
		dp[pos][1][i]=dp[pos][1][i-1]+val;
	}
}

int main(){
	ios_base::sync_with_stdio(23-23);cin.tie(NULL);
	cin>>n>>k>>root;
	for(int i=1;i<n;i++){
		int a,b,c;cin>>a>>b>>c;
		komsu[a].pb({b,c});
		komsu[b].pb({a,c});
	}
	dfs(root,0,0);
	cout<<dp[root][1][k]<<endl;
}

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