oj.uz

Submission #716948

# Submission time Handle Problem Language Result Execution time Memory
716948 2023-03-31T13:10:42 Z Dan4Life Museum (CEOI17_museum) C++17
80 / 100
 3000 ms 834880 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 <= min(k,sub[s]); j++)
			dp2[i][j][0]=dp2[i][j][1]=LINF;
	dp2[0][0][0] = dp2[0][0][1] = 0; int tot = 0;
	for(int i = 1; i <= sz(v); i++){
		auto u = v[i-1].se; tot+=sub[u];
		for(int j = 0; j <= min(k,sub[s]); 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*u);
					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]+u);
				}
				
			}
		}
	}
	for(int i = 2; i <= min(k,sub[s]); 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 784884 KB Output is correct
2 Correct 344 ms 784796 KB Output is correct
3 Correct 333 ms 784820 KB Output is correct
4 Correct 326 ms 784852 KB Output is correct
5 Correct 367 ms 784884 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 785352 KB Output is correct
2 Correct 404 ms 785324 KB Output is correct
3 Correct 617 ms 785964 KB Output is correct
4 Correct 516 ms 785416 KB Output is correct
5 Correct 453 ms 785300 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 785352 KB Output is correct
2 Correct 404 ms 785324 KB Output is correct
3 Correct 617 ms 785964 KB Output is correct
4 Correct 516 ms 785416 KB Output is correct
5 Correct 453 ms 785300 KB Output is correct
6 Correct 459 ms 785288 KB Output is correct
7 Correct 617 ms 785796 KB Output is correct
8 Correct 864 ms 834880 KB Output is correct
9 Correct 806 ms 795468 KB Output is correct
10 Correct 758 ms 785864 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 784884 KB Output is correct
2 Correct 344 ms 784796 KB Output is correct
3 Correct 333 ms 784820 KB Output is correct
4 Correct 326 ms 784852 KB Output is correct
5 Correct 367 ms 784884 KB Output is correct
6 Correct 388 ms 785352 KB Output is correct
7 Correct 404 ms 785324 KB Output is correct
8 Correct 617 ms 785964 KB Output is correct
9 Correct 516 ms 785416 KB Output is correct
10 Correct 453 ms 785300 KB Output is correct
11 Correct 459 ms 785288 KB Output is correct
12 Correct 617 ms 785796 KB Output is correct
13 Correct 864 ms 834880 KB Output is correct
14 Correct 806 ms 795468 KB Output is correct
15 Correct 758 ms 785864 KB Output is correct
16 Correct 803 ms 785320 KB Output is correct
17 Execution timed out 3075 ms 785508 KB Time limit exceeded
18 Halted 0 ms 0 KB -