제출 #791757

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
791757		dungz	Museum (CEOI17_museum)	C++17	100 / 100	349 ms	294712 KiB

museum

#pragma GCC optimize ("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define fi first
#define se second
#define endl '\n'
#define task "task"
#define task "task"
#define prll pair<ll,ll>
#define pb push_back
#define ld long double
const ll MIN=-1e18,MAX=1e18,MOD=1e9+7;
vector<pair<int,int>> a[10005];
vector<ll> f[10005];
vector<ll> f2[10005];
int n,m,st;
void dfs(int u,int par)
{
	f[u]=f2[u]={0,0};
	for(auto i:a[u])
	{
		if(i.fi!=par)
		{
			dfs(i.fi,u);
			int v=i.fi;
			vector<ll> inter(min((ll)(m+1),(ll)(f[u].size()+f[v].size()-1)),MAX);
			vector<ll> inter2(min((ll)(m+1),(ll)(f2[u].size()+f2[v].size()-1)),MAX);
			inter2[0]=inter[0]=inter[1]=inter2[1]=0;
			for(int j=1;j<f[u].size();j++)
			{
				for(int k=0;k<f[v].size();k++)
				{
					if(j+k>m+1) break;
					inter[j+k]=min(inter[j+k],f[u][j]+f[v][k]+i.se*2*(k!=0));
					inter2[j+k]=min(inter2[j+k],min(f[v][k],f2[v][k])+f[u][j]+i.se*(k!=0));
					// if(u==3 and v==7 and j+k==2) cout<<j<<" "<<k<<" "<<f[u][j]+f[v][k]+i.se*2*(k!=0)<<endl;
					inter2[j+k]=min(inter2[j+k],f2[u][j]+f[v][k]+i.se*2*(k!=0));
				}	
			}
			// if(u==3 and v==7 ) 
			// {
				// for(int j=0;j<inter.size();j++) cout<<j<<" "<<inter[j]<<endl;
				// cout<<inter.size();
			// }
			swap(f[u],inter);
			swap(f2[u],inter2);
		}
	}
}
int main(){
	// #ifndef ONLINE_JUDGE
   	// 	freopen (task".inp", "r", stdin);
   	// 	freopen (task".out", "w", stdout);
	// #endif
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m>>st;
	for(int i=1;i<=n-1;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		a[x].push_back({y,z});
		a[y].push_back({x,z});
	}	
	dfs(st,0);
	// cout<<f2[7][5]<<endl;
	// cout<<st<<" "<<m;
	cout<<min(f[st][m],f2[st][m]);
}
/*

*/

컴파일 시 표준 에러 (stderr) 메시지

museum.cpp: In function 'void dfs(int, int)':
museum.cpp:30:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |    for(int j=1;j<f[u].size();j++)
      |                ~^~~~~~~~~~~~
museum.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int k=0;k<f[v].size();k++)
      |                 ~^~~~~~~~~~~~

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