oj.uz

Submission #716965

# Submission time Handle Problem Language Result Execution time Memory
716965 2023-03-31T14:15:01 Z Dan4Life Museum (CEOI17_museum) C++17
100 / 100
 749 ms 784576 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];
 
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){
	for(int tot = 1; auto [u,w] : adj[s]){ 
		if(u==p) continue; 
		dfs(u,s); tot+=sub[u];
		for(int i = tot; i >= 2; i--)
            for(int j = max(0, i-tot+sub[u]); j<=min(i,sub[u]); j++)
				dp[s][i][0] = min(dp[s][i][0], dp[s][i-j][0] + dp[u][j][1]+2*w),
				dp[s][i][0] = min(dp[s][i][0], dp[s][i-j][1]+dp[u][j][0]+w),
				dp[s][i][1] = min(dp[s][i][1], dp[s][i-j][1]+dp[u][j][1]+2*w);
	}
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k >> s;
	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});
	}
	for(int i=1; i<=n; i++){
        for(int j=2; j<=n; j++){
            dp[i][j][0] = dp[i][j][1] = LINF;
        }
    }
	findSize(s,-1); dfs(s,-1); cout << dp[s][k][0];
}

Compilation message

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

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 783904 KB Output is correct
2 Correct 498 ms 783924 KB Output is correct
3 Correct 628 ms 784332 KB Output is correct
4 Correct 493 ms 783948 KB Output is correct
5 Correct 497 ms 783944 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 783904 KB Output is correct
2 Correct 498 ms 783924 KB Output is correct
3 Correct 628 ms 784332 KB Output is correct
4 Correct 493 ms 783948 KB Output is correct
5 Correct 497 ms 783944 KB Output is correct
6 Correct 492 ms 783888 KB Output is correct
7 Correct 527 ms 784172 KB Output is correct
8 Correct 720 ms 783892 KB Output is correct
9 Correct 691 ms 783928 KB Output is correct
10 Correct 522 ms 783912 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 489 ms 783904 KB Output is correct
7 Correct 498 ms 783924 KB Output is correct
8 Correct 628 ms 784332 KB Output is correct
9 Correct 493 ms 783948 KB Output is correct
10 Correct 497 ms 783944 KB Output is correct
11 Correct 492 ms 783888 KB Output is correct
12 Correct 527 ms 784172 KB Output is correct
13 Correct 720 ms 783892 KB Output is correct
14 Correct 691 ms 783928 KB Output is correct
15 Correct 522 ms 783912 KB Output is correct
16 Correct 458 ms 783924 KB Output is correct
17 Correct 476 ms 783928 KB Output is correct
18 Correct 509 ms 784072 KB Output is correct
19 Correct 749 ms 783896 KB Output is correct
20 Correct 474 ms 783972 KB Output is correct
21 Correct 599 ms 784216 KB Output is correct
22 Correct 473 ms 783948 KB Output is correct
23 Correct 674 ms 784100 KB Output is correct
24 Correct 491 ms 784108 KB Output is correct
25 Correct 608 ms 784576 KB Output is correct