oj.uz

Submission #952156

# Submission time Handle Problem Language Result Execution time Memory
952156 2024-03-23T07:05:12 Z vjudge1 Museum (CEOI17_museum) C++14
80 / 100
 3000 ms 785192 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 i=min(k,son[u]);i>=2;i--){
			for(int j=min(i,son[v.first]);j>=0;j--){
				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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 784212 KB Output is correct
2 Correct 212 ms 784212 KB Output is correct
3 Correct 254 ms 784208 KB Output is correct
4 Correct 218 ms 784504 KB Output is correct
5 Correct 194 ms 784208 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 784612 KB Output is correct
2 Correct 212 ms 784720 KB Output is correct
3 Correct 309 ms 784724 KB Output is correct
4 Correct 258 ms 784720 KB Output is correct
5 Correct 240 ms 784472 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 784612 KB Output is correct
2 Correct 212 ms 784720 KB Output is correct
3 Correct 309 ms 784724 KB Output is correct
4 Correct 258 ms 784720 KB Output is correct
5 Correct 240 ms 784472 KB Output is correct
6 Correct 222 ms 784512 KB Output is correct
7 Correct 307 ms 785192 KB Output is correct
8 Correct 204 ms 784464 KB Output is correct
9 Correct 205 ms 784668 KB Output is correct
10 Correct 207 ms 784460 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 784212 KB Output is correct
2 Correct 212 ms 784212 KB Output is correct
3 Correct 254 ms 784208 KB Output is correct
4 Correct 218 ms 784504 KB Output is correct
5 Correct 194 ms 784208 KB Output is correct
6 Correct 209 ms 784612 KB Output is correct
7 Correct 212 ms 784720 KB Output is correct
8 Correct 309 ms 784724 KB Output is correct
9 Correct 258 ms 784720 KB Output is correct
10 Correct 240 ms 784472 KB Output is correct
11 Correct 222 ms 784512 KB Output is correct
12 Correct 307 ms 785192 KB Output is correct
13 Correct 204 ms 784464 KB Output is correct
14 Correct 205 ms 784668 KB Output is correct
15 Correct 207 ms 784460 KB Output is correct
16 Correct 373 ms 784452 KB Output is correct
17 Correct 1298 ms 784812 KB Output is correct
18 Execution timed out 3062 ms 784724 KB Time limit exceeded
19 Halted 0 ms 0 KB -