oj.uz

Submission #951266

# Submission time Handle Problem Language Result Execution time Memory
951266 2024-03-21T14:05:59 Z ting39 Museum (CEOI17_museum) C++17
100 / 100
 556 ms 313200 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 432 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 6564 KB Output is correct
2 Correct 204 ms 7328 KB Output is correct
3 Correct 401 ms 313200 KB Output is correct
4 Correct 249 ms 101320 KB Output is correct
5 Correct 171 ms 25452 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 6564 KB Output is correct
2 Correct 204 ms 7328 KB Output is correct
3 Correct 401 ms 313200 KB Output is correct
4 Correct 249 ms 101320 KB Output is correct
5 Correct 171 ms 25452 KB Output is correct
6 Correct 170 ms 5148 KB Output is correct
7 Correct 293 ms 187764 KB Output is correct
8 Correct 556 ms 3184 KB Output is correct
9 Correct 408 ms 3388 KB Output is correct
10 Correct 204 ms 5108 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 432 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 158 ms 6564 KB Output is correct
7 Correct 204 ms 7328 KB Output is correct
8 Correct 401 ms 313200 KB Output is correct
9 Correct 249 ms 101320 KB Output is correct
10 Correct 171 ms 25452 KB Output is correct
11 Correct 170 ms 5148 KB Output is correct
12 Correct 293 ms 187764 KB Output is correct
13 Correct 556 ms 3184 KB Output is correct
14 Correct 408 ms 3388 KB Output is correct
15 Correct 204 ms 5108 KB Output is correct
16 Correct 159 ms 7988 KB Output is correct
17 Correct 180 ms 7516 KB Output is correct
18 Correct 245 ms 120388 KB Output is correct
19 Correct 453 ms 3288 KB Output is correct
20 Correct 211 ms 5380 KB Output is correct
21 Correct 283 ms 175068 KB Output is correct
22 Correct 174 ms 7260 KB Output is correct
23 Correct 491 ms 3292 KB Output is correct
24 Correct 224 ms 5180 KB Output is correct
25 Correct 390 ms 312036 KB Output is correct