oj.uz

Submission #952154

# Submission time Handle Problem Language Result Execution time Memory
952154 2024-03-23T06:58:41 Z vjudge1 Museum (CEOI17_museum) C++14
0 / 100
 355 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][1][0]=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 j=1;j<=min(son[v.first],k);j++){
			for(int i=min(k,son[u]-son[v.first]+j);i>=j+1;i--){
				if(dp[u][i-j][0]+dp[v.first][j][0]+v.second*2>=0)dp[u][i][0]=min(dp[u][i][0],dp[u][i-j][0]+dp[v.first][j][0]+v.second*2);
				if(dp[u][i-j][0]+dp[v.first][j][1]+v.second>=0)dp[u][i][1]=min(dp[u][i][1],dp[u][i-j][0]+dp[v.first][j][1]+v.second);
				if(dp[u][i-j][1]+dp[v.first][j][0]+v.second*2>=0)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 Correct 355 ms 784124 KB Output is correct
2 Incorrect 220 ms 784132 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 221 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 221 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 Correct 355 ms 784124 KB Output is correct
2 Incorrect 220 ms 784132 KB Output isn't correct
3 Halted 0 ms 0 KB -