oj.uz

Submission #716956

# Submission time Handle Problem Language Result Execution time Memory
716956 2023-03-31T13:51:08 Z Dan4Life Museum (CEOI17_museum) C++17
80 / 100
 3000 ms 835000 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
const int mxN=(int)1e4+10;
const int LINF = (int)1e9;
int n, k, s, sub[mxN];
vector<pair<int,int>> adj[mxN];
int dp[mxN][mxN][2], dp2[mxN][mxN][2];
 
int findSize(int s, int p){
	sub[s]=1;
	for(auto [u,w] : adj[s])
		if(u!=p) sub[s]+=findSize(u,s);
	return sub[s];
}
 
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; int tot = 1;
	for(int i = 1; i <= sz(v); i++){
		auto u = v[i-1].fi;
		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[u][l][1]+2*v[i-1].se);
					if(!x)dp2[i][j][x] = min(dp2[i][j][x], dp2[i-1][j-l][1]+dp[u][l][0]+v[i-1].se);
				}
			}
		}
		tot+=sub[u];
	}
	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 < mxN; 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});
	}
	findSize(s,-1); dfs(s,-1); cout << dp[s][k][0];
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 784972 KB Output is correct
2 Correct 343 ms 784796 KB Output is correct
3 Correct 344 ms 784972 KB Output is correct
4 Correct 341 ms 784988 KB Output is correct
5 Correct 328 ms 784940 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 749 ms 785396 KB Output is correct
2 Correct 758 ms 785348 KB Output is correct
3 Correct 791 ms 785980 KB Output is correct
4 Correct 757 ms 785684 KB Output is correct
5 Correct 739 ms 785360 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 749 ms 785396 KB Output is correct
2 Correct 758 ms 785348 KB Output is correct
3 Correct 791 ms 785980 KB Output is correct
4 Correct 757 ms 785684 KB Output is correct
5 Correct 739 ms 785360 KB Output is correct
6 Correct 752 ms 785376 KB Output is correct
7 Correct 769 ms 785740 KB Output is correct
8 Correct 802 ms 835000 KB Output is correct
9 Correct 828 ms 795440 KB Output is correct
10 Correct 762 ms 785892 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 784972 KB Output is correct
2 Correct 343 ms 784796 KB Output is correct
3 Correct 344 ms 784972 KB Output is correct
4 Correct 341 ms 784988 KB Output is correct
5 Correct 328 ms 784940 KB Output is correct
6 Correct 749 ms 785396 KB Output is correct
7 Correct 758 ms 785348 KB Output is correct
8 Correct 791 ms 785980 KB Output is correct
9 Correct 757 ms 785684 KB Output is correct
10 Correct 739 ms 785360 KB Output is correct
11 Correct 752 ms 785376 KB Output is correct
12 Correct 769 ms 785740 KB Output is correct
13 Correct 802 ms 835000 KB Output is correct
14 Correct 828 ms 795440 KB Output is correct
15 Correct 762 ms 785892 KB Output is correct
16 Execution timed out 3083 ms 785368 KB Time limit exceeded
17 Halted 0 ms 0 KB -