oj.uz

Submission #952149

# Submission time Handle Problem Language Result Execution time Memory
952149 2024-03-23T06:46:12 Z vjudge1 Museum (CEOI17_museum) C++14
0 / 100
 374 ms 784464 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int n,k,x,son[N];
int dp[N][N][2];
vector<pair<int,int> >g[N];
inline void dfs(int u,int fa){
	dp[u][0][1]=dp[u][1][1]=0;
	son[u]=1;
	for(auto v:g[u]){
		if(v.first==fa)continue;
		dfs(v.first,u);
		son[u]+=son[v.first];
		for(int i=min(k,son[u]);i>=2;i--){
			for(int j=min(i,son[v.first]);j>=0;j--){
				dp[u][i][0]=min(dp[u][i][0],dp[u][i-j][0]+dp[v.first][j][0]+v.second*2);
				dp[u][i][1]=min(dp[u][i][1],dp[u][i-j][0]+dp[v.first][j][1]+v.second);
				dp[u][i][1]=min(dp[u][i][1],dp[u][i-j][1]+dp[v.first][j][0]+v.second*2);
			}
		}
	}
}
int main(){
	//freopen("museum.in","r",stdin);
	//freopen("museum.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(dp,0x7f,sizeof dp);
	cin>>n>>k>>x;
	for(int i=1,a,b,c;i<n;i++){
		cin>>a>>b>>c;
		g[a].push_back({b,c});
		g[b].push_back({a,c});
	}
	dfs(x,-1);
	cout<<min(dp[x][k][0],dp[x][k][1]);
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 374 ms 784212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 222 ms 784464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 222 ms 784464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 374 ms 784212 KB Output isn't correct
2 Halted 0 ms 0 KB -