oj.uz

Submission #716935

# Submission time Handle Problem Language Result Execution time Memory
716935 2023-03-31T12:29:29 Z Dan4Life Museum (CEOI17_museum) C++17
80 / 100
 3000 ms 35924 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
const int mxN=(int)1e4+10;
const int mxK=(int)1e2+10;
const int LINF = (int)1e16;
int n, k, s;
vector<pair<int,int>> adj[mxN];
int dp[mxN][mxK][2],dp2[mxN][mxK][2];

void dfs(int s, int p){
	vector<pair<int,int>> v; v.clear();
	for(auto [u,w] : adj[s])
		if(u!=p) dfs(u,s), v.pb({u,w});
	dp[s][1][0]=dp[s][1][1]=0;
	if(!sz(v)) return;
	for(int i = 0; i <= sz(v); i++)
		for(int j = 0; j <= k; j++)
			dp2[i][j][0]=dp2[i][j][1]=LINF;
	dp2[0][0][0] = dp2[0][0][1] = 0;
	for(int i = 1; i <= sz(v); i++){
		for(int j = 0; j <= k; j++){
			for(int x = 0; x < 2; x++){
				dp2[i][j][x] = min(dp2[i][j][x],dp2[i-1][j][x]);
				for(int l = 1; l <= j; l++){
					dp2[i][j][x] = min(dp2[i][j][x], dp2[i-1][j-l][x]+
					dp[v[i-1].fi][l][1]+2*v[i-1].se);
					if(x) continue;
					dp2[i][j][x] = min(dp2[i][j][x], dp2[i-1][j-l][1]+
					dp[v[i-1].fi][l][0]+v[i-1].se);
				}
				
			}
			
		}
	}
	for(int i = 2; i <= k; i++)
		for(int j = 0; j < 2; j++)
			dp[s][i][j] = min(dp[s][i][j],dp2[sz(v)][i-1][j]);
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k >> s;
	for(int i = 0; i < mxN; i++)
		for(int j = 0; j < mxK; j++)
			dp[i][j][0]=dp[i][j][1]=LINF;
	for(int i = 1; i < n; i++){
		int a, b, c; cin >> a >> b >> c;
		adj[a].pb({b,c}), adj[b].pb({a,c});
	}
	dfs(s,-1); cout << dp[s][k][0];
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17748 KB Output is correct
2 Correct 8 ms 17748 KB Output is correct
3 Correct 8 ms 17748 KB Output is correct
4 Correct 8 ms 17748 KB Output is correct
5 Correct 8 ms 17740 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 18496 KB Output is correct
2 Correct 465 ms 18644 KB Output is correct
3 Correct 463 ms 19024 KB Output is correct
4 Correct 446 ms 18684 KB Output is correct
5 Correct 442 ms 18524 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 18496 KB Output is correct
2 Correct 465 ms 18644 KB Output is correct
3 Correct 463 ms 19024 KB Output is correct
4 Correct 446 ms 18684 KB Output is correct
5 Correct 442 ms 18524 KB Output is correct
6 Correct 443 ms 18472 KB Output is correct
7 Correct 450 ms 18856 KB Output is correct
8 Correct 456 ms 35924 KB Output is correct
9 Correct 451 ms 22044 KB Output is correct
10 Correct 444 ms 18792 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17748 KB Output is correct
2 Correct 8 ms 17748 KB Output is correct
3 Correct 8 ms 17748 KB Output is correct
4 Correct 8 ms 17748 KB Output is correct
5 Correct 8 ms 17740 KB Output is correct
6 Correct 457 ms 18496 KB Output is correct
7 Correct 465 ms 18644 KB Output is correct
8 Correct 463 ms 19024 KB Output is correct
9 Correct 446 ms 18684 KB Output is correct
10 Correct 442 ms 18524 KB Output is correct
11 Correct 443 ms 18472 KB Output is correct
12 Correct 450 ms 18856 KB Output is correct
13 Correct 456 ms 35924 KB Output is correct
14 Correct 451 ms 22044 KB Output is correct
15 Correct 444 ms 18792 KB Output is correct
16 Execution timed out 3046 ms 18528 KB Time limit exceeded
17 Halted 0 ms 0 KB -