Submission #1276638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276638		random_user27	Museum (CEOI17_museum)	C++20	100 / 100	630 ms	786764 KiB

museum

// In The Name Of God

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define pb push_back
#define endl '\n'
#define test(x) cout<<x,exit(0)
#define fast (ios_base::sync_with_stdio(false),cin.tie(NULL))

const int maxn=1e4+10;
const int inf=1e9;
vector<int>adj[maxn];
vector<int>w[maxn];
int dp1[maxn][maxn];
int dp2[maxn][maxn];
int tmp[maxn];
int tmp2[maxn];
int sz[maxn];

void dfs(int v,int p){
	if(adj[v].size()==1 and p!=0){
		sz[v]=1;
		dp1[v][1]=0;
		dp2[v][1]=0;
		return;
	}
	for(int i=0;i<adj[v].size();i++){
		if(adj[v][i]!=p){
			dfs(adj[v][i],v);
			int u=adj[v][i];
			for(int j=1;j<maxn;j++){
				tmp[j]=inf;
				tmp2[j]=inf;
			}
			tmp[0]=tmp2[0]=0;
			for(int j=0;j<=sz[v];j++){
				for(int k=1;k<=sz[u];k++){
					tmp[k+j]=min(tmp[k+j],dp1[v][j]+w[v][i]*2+dp1[u][k]);
					tmp2[k+j]=min(tmp2[k+j],dp1[v][j]+w[v][i]+dp2[u][k]);
					tmp2[k+j]=min(tmp2[k+j],dp2[v][j]+w[v][i]*2+dp1[u][k]);
				}
			}
			sz[v]+=sz[u];
			for(int j=0;j<=sz[v];j++){
				dp1[v][j]=min(dp1[v][j],tmp[j]);
				dp2[v][j]=min(dp2[v][j],tmp2[j]);
			}
		}
	}
	sz[v]++;
	for(int i=sz[v];i>=1;i--){
		dp1[v][i]=dp1[v][i-1];
		dp2[v][i]=dp2[v][i-1];
	}

}

int main(){
	fast;
	int n,k,x;cin>>n>>k>>x;
	for(int i=1;i<n;i++){
		int u,v,we;
		cin>>u>>v>>we;
		adj[u].pb(v);
		adj[v].pb(u);
		w[v].pb(we);
		w[u].pb(we);
	}
	if(k==1){
		test(0);
	}
	for(int i=0;i<maxn;i++){
		for(int j=1;j<maxn;j++){
			dp1[i][j]=dp2[i][j]=inf;
		}
	}
	dfs(x,0);
	cout<<dp2[x][k]<<endl;
	
}

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