Submission #951266

#	Time	Username	Problem	Language	Result	Execution time	Memory
951266		ting39	Museum (CEOI17_museum)	C++17	100 / 100	556 ms	313200 KiB

museum

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
vector<vector<pii>> g;
vector<vector<int>> dp[2];
void dfs(int pre,int pos){
	dp[0][pos]={(int)1e18,0};
	dp[1][pos]={(int)1e18,0};
	for(auto i:g[pos]){
		if(i.F==pre) continue;
		dfs(pos,i.F);
		vector<int> tmp(dp[1][i.F].size()+dp[1][pos].size()-1,1e18);
		for(int j=0;j<dp[1][i.F].size();j++){
			for(int k=1;k<dp[1][pos].size();k++){
				tmp[j+k]=min(tmp[j+k],dp[1][i.F][j]+dp[1][pos][k]+2*i.S);
				if(j==0){
					tmp[j+k]=min(tmp[j+k],dp[1][pos][k]);
				}
			}
		}
		int sz=max(dp[0][pos].size()+dp[1][i.F].size()-1,dp[1][pos].size()+dp[0][i.F].size()-1);
		vector<int> tmp1(sz,1e18);
		for(int j=1;j<dp[0][pos].size();j++){
			for(int k=0;k<dp[1][i.F].size();k++){
				tmp1[j+k]=min(tmp1[j+k],dp[0][pos][j]+dp[1][i.F][k]+2*i.S);
				if(k==0){
					tmp1[j]=min(tmp1[j],dp[0][pos][j]);
				}
			}
		}
		vector<int> tmp2(sz,1e18);
		for(int j=1;j<dp[1][pos].size();j++){
			for(int k=0;k<dp[0][i.F].size();k++){
				tmp2[j+k]=min(tmp2[j+k],dp[1][pos][j]+dp[0][i.F][k]+i.S);
				if(k==0){
					tmp2[j]=min(tmp2[j],dp[1][pos][j]);
				}
			}
		}
		dp[0][pos].resize(sz);
		for(int j=0;j<sz;j++){
			dp[0][pos][j]=min(tmp1[j],tmp2[j]);
		}
		dp[1][pos]=tmp;
	}
	for(int i=0;i<min(dp[0][pos].size(),dp[1][pos].size());i++){
		dp[0][pos][i]=min(dp[0][pos][i],dp[1][pos][i]);
	}
	dp[0][pos][0]=0;
	dp[1][pos][0]=0;
}
signed main(){
	int n,k,x;
	cin>>n>>k>>x;
	x--;
	g.resize(n);
	for(auto &i:dp) i.resize(n);
	for(int i=0;i<n-1;i++){
		int a,b,c;
		cin>>a>>b>>c;
		a--;
		b--;
		g[a].push_back({b,c});
		g[b].push_back({a,c});
	}
	dfs(x,x);
	cout<<dp[0][x][k]<<endl;
}

Compilation message (stderr)

museum.cpp: In function 'void dfs(long long int, long long int)':
museum.cpp:16:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   for(int j=0;j<dp[1][i.F].size();j++){
      |               ~^~~~~~~~~~~~~~~~~~
museum.cpp:17:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |    for(int k=1;k<dp[1][pos].size();k++){
      |                ~^~~~~~~~~~~~~~~~~~
museum.cpp:26:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for(int j=1;j<dp[0][pos].size();j++){
      |               ~^~~~~~~~~~~~~~~~~~
museum.cpp:27:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |    for(int k=0;k<dp[1][i.F].size();k++){
      |                ~^~~~~~~~~~~~~~~~~~
museum.cpp:35:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int j=1;j<dp[1][pos].size();j++){
      |               ~^~~~~~~~~~~~~~~~~~
museum.cpp:36:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    for(int k=0;k<dp[0][i.F].size();k++){
      |                ~^~~~~~~~~~~~~~~~~~
museum.cpp:49:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'const long unsigned int' [-Wsign-compare]
   49 |  for(int i=0;i<min(dp[0][pos].size(),dp[1][pos].size());i++){
      |              ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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