Submission #1278241

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278241		mhn_neek	Museum (CEOI17_museum)	C++20	100 / 100	844 ms	590104 KiB

museum

//In the name of God
#include<bits/stdc++.h>
/*MHN*/
using namespace std;
typedef long long int lli;
typedef long double ld;
typedef pair<lli,lli> pii;
typedef vector<lli> ve;
typedef vector<pii> vp;
const lli N=10010;
const lli mod=1e9+7;//998244353;//1e9+9
const lli INF=1e18;
lli power(lli x,lli y){lli res = 1;x = x % mod;while(y>0){if( y & 1 ){res = (res * x) % mod;}y = y >> 1;x = (x * x)%mod;}return res;}
lli modinv(lli x){return power(x,mod-2);}
lli divide(lli x,lli y){return ((x%mod) * modinv(y))%mod;}
#define all(v) v.begin(),v.end()
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define migmig ios_base::sync_with_stdio(false),cout.tie(0), cin.tie(0);
#define read freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define debug(x) cerr << (#x) << " " << (x) << endl
#define MP make_pair
#define PB push_back
#define fi first
#define se second
#define SUM(v) accumulate(v.begin(),v.end(), 0LL)
#define FOR(x,n) for(lli x = 0; x < n; x++)
#define FORS(x,n) for(lli x = 1; x <= n; x++)
#define TEST int TQPWIEJR; cin>>TQPWIEJR;while(TQPWIEJR--)
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define sep " "
lli tmp;
vp adj[N];
lli n,k;
lli X;
vp dp[N];
bool vis[N];
lli sz[N];

/*
	dpv.fi = berim 
	dpv.se = bargardim!!!

*/

void dfs(lli v){
	vis[v] = 1;
	dp[v].resize(k+1,MP(INF,INF));
	dp[v][1].se = 0;
	dp[v][1].fi = 0;
	sz[v] = 1;
	for(auto [u,w] : adj[v]){
		if(vis[u])continue;
		dfs(u);
		vp add(k+1,MP(INF,INF));
		for(lli x = 1; x <= min(k,sz[v]); x ++){
			for(lli y = 1; y <= min(k,sz[u]) && y <= k - x; y ++){
				add[x+y].se = min(add[x+y].se, dp[v][x].se + 2*w + dp[u][y].se);
				add[x+y].fi = min(add[x+y].fi, dp[v][x].fi + 2*w + dp[u][y].se);
				add[x+y].fi = min(add[x+y].fi, dp[v][x].se + w + dp[u][y].fi);
			}
		}
		FORS(i,k){
			dp[v][i].fi = min(dp[v][i].fi,add[i].fi);
			dp[v][i].se = min(dp[v][i].se,add[i].se);
		}


		dp[u].clear();
		dp[u].shrink_to_fit();
		sz[v] += sz[u];
	}
}
int main(){
    migmig;
	cin>>n>>k>>X;
	FOR(i,n-1){
		lli a,b,c;
		cin>>a>>b>>c;
		adj[a].PB(MP(b,c));
		adj[b].PB(MP(a,c));
	}
	dfs(X);
	cout<<dp[X][k].fi<<endl;
}

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