oj.uz

Submission #716963

# Submission time Handle Problem Language Result Execution time Memory
716963 2023-03-31T14:04:19 Z Dan4Life Museum (CEOI17_museum) C++17
80 / 100
 1368 ms 1048576 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+2;
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; auto [u,w] : v){ 
		tot+=sub[u];
		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 = max(1,j-tot+sub[u]); l <= min(j,sub[u]); l++){
					dp2[i][j][x] = min(dp2[i][j][x], dp2[i-1][j-l][x]+dp[u][l][1]+2*w);
					dp2[i][j][0] = min(dp2[i][j][0], dp2[i-1][j-l][1]+dp[u][l][0]+w);
				}
			}
		} i++;
	}
	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;
	memset(dp,63,sizeof(dp));
	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];
}

Compilation message

museum.cpp: In function 'void dfs(int, int)':
museum.cpp:31:17: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
   31 |  for(int i = 1; auto [u,w] : v){
      |                 ^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 783596 KB Output is correct
2 Correct 314 ms 783708 KB Output is correct
3 Correct 325 ms 783548 KB Output is correct
4 Correct 317 ms 783560 KB Output is correct
5 Correct 298 ms 783680 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 784052 KB Output is correct
2 Correct 323 ms 784076 KB Output is correct
3 Correct 314 ms 784884 KB Output is correct
4 Correct 326 ms 784404 KB Output is correct
5 Correct 350 ms 784120 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 784052 KB Output is correct
2 Correct 323 ms 784076 KB Output is correct
3 Correct 314 ms 784884 KB Output is correct
4 Correct 326 ms 784404 KB Output is correct
5 Correct 350 ms 784120 KB Output is correct
6 Correct 311 ms 784124 KB Output is correct
7 Correct 317 ms 784564 KB Output is correct
8 Correct 372 ms 833560 KB Output is correct
9 Correct 322 ms 794116 KB Output is correct
10 Correct 311 ms 784740 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 783596 KB Output is correct
2 Correct 314 ms 783708 KB Output is correct
3 Correct 325 ms 783548 KB Output is correct
4 Correct 317 ms 783560 KB Output is correct
5 Correct 298 ms 783680 KB Output is correct
6 Correct 315 ms 784052 KB Output is correct
7 Correct 323 ms 784076 KB Output is correct
8 Correct 314 ms 784884 KB Output is correct
9 Correct 326 ms 784404 KB Output is correct
10 Correct 350 ms 784120 KB Output is correct
11 Correct 311 ms 784124 KB Output is correct
12 Correct 317 ms 784564 KB Output is correct
13 Correct 372 ms 833560 KB Output is correct
14 Correct 322 ms 794116 KB Output is correct
15 Correct 311 ms 784740 KB Output is correct
16 Correct 477 ms 784116 KB Output is correct
17 Correct 1000 ms 784224 KB Output is correct
18 Correct 469 ms 784292 KB Output is correct
19 Correct 428 ms 844276 KB Output is correct
20 Correct 436 ms 784772 KB Output is correct
21 Correct 1363 ms 784736 KB Output is correct
22 Correct 1368 ms 784312 KB Output is correct
23 Runtime error 403 ms 1048576 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -