oj.uz

Submission #975315

# Submission time Handle Problem Language Result Execution time Memory
975315 2024-05-04T18:29:13 Z dosts Museum (CEOI17_museum) C++17
100 / 100
 629 ms 784752 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 2648 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 783956 KB Output is correct
2 Correct 401 ms 784312 KB Output is correct
3 Correct 548 ms 784556 KB Output is correct
4 Correct 436 ms 784360 KB Output is correct
5 Correct 424 ms 784120 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 783956 KB Output is correct
2 Correct 401 ms 784312 KB Output is correct
3 Correct 548 ms 784556 KB Output is correct
4 Correct 436 ms 784360 KB Output is correct
5 Correct 424 ms 784120 KB Output is correct
6 Correct 401 ms 783956 KB Output is correct
7 Correct 471 ms 784432 KB Output is correct
8 Correct 629 ms 784212 KB Output is correct
9 Correct 535 ms 783956 KB Output is correct
10 Correct 424 ms 784356 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 431 ms 783956 KB Output is correct
7 Correct 401 ms 784312 KB Output is correct
8 Correct 548 ms 784556 KB Output is correct
9 Correct 436 ms 784360 KB Output is correct
10 Correct 424 ms 784120 KB Output is correct
11 Correct 401 ms 783956 KB Output is correct
12 Correct 471 ms 784432 KB Output is correct
13 Correct 629 ms 784212 KB Output is correct
14 Correct 535 ms 783956 KB Output is correct
15 Correct 424 ms 784356 KB Output is correct
16 Correct 407 ms 784200 KB Output is correct
17 Correct 398 ms 784072 KB Output is correct
18 Correct 443 ms 784356 KB Output is correct
19 Correct 593 ms 784212 KB Output is correct
20 Correct 408 ms 784184 KB Output is correct
21 Correct 458 ms 784416 KB Output is correct
22 Correct 414 ms 784096 KB Output is correct
23 Correct 561 ms 784268 KB Output is correct
24 Correct 403 ms 784208 KB Output is correct
25 Correct 503 ms 784752 KB Output is correct