oj.uz

Submission #1084681

# Submission time Handle Problem Language Result Execution time Memory
1084681 2024-09-06T16:43:01 Z BF001 Museum (CEOI17_museum) C++17
100 / 100
 1883 ms 784512 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define N 10002
#define oo 1e9
#define fi first 
#define se second

typedef pair<int, int> ii;

int dp[2][N][N], n, root, k, siz[N];
vector<ii> adj[N];
 
void dfs(int u, int p){
    siz[u] = 1;
    dp[1][1][u] = dp[0][1][u] = dp[0][0][u] = dp[1][0][u] = 0;
    for (auto x : adj[u]){
        int v = x.fi, w = x.se;
        if (v == p) continue;
        dfs(v, u);
        for (int i = siz[u]; i >= 1; i--){
            for (int j = 1; j <= siz[v]; j++){
                dp[0][i + j][u] = min(dp[0][i + j][u], dp[1][i][u] + dp[0][j][v] + w);
                dp[0][i + j][u] = min(dp[0][i + j][u], dp[0][i][u] + dp[1][j][v] + 2 * w);
                dp[1][i + j][u] = min(dp[1][i + j][u], dp[1][i][u] + dp[1][j][v] + w * 2);
            }
        }
        siz[u] += siz[v];
    }

}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
 
    cin >> n >> k >> root;
    for (int i = 1; i <= n - 1; i++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    } 

    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= n; j++){
            dp[0][j][i] = dp[1][j][i] = oo;
        }
    }   
    
    dfs(root, 0);
    cout << dp[0][k][root];

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 0 ms 704 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 0 ms 860 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1748 ms 784396 KB Output is correct
2 Correct 1778 ms 784136 KB Output is correct
3 Correct 1694 ms 784420 KB Output is correct
4 Correct 1826 ms 784132 KB Output is correct
5 Correct 1756 ms 784208 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1748 ms 784396 KB Output is correct
2 Correct 1778 ms 784136 KB Output is correct
3 Correct 1694 ms 784420 KB Output is correct
4 Correct 1826 ms 784132 KB Output is correct
5 Correct 1756 ms 784208 KB Output is correct
6 Correct 1668 ms 784196 KB Output is correct
7 Correct 1757 ms 784512 KB Output is correct
8 Correct 1479 ms 784116 KB Output is correct
9 Correct 1619 ms 784140 KB Output is correct
10 Correct 1702 ms 784212 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 0 ms 704 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 1748 ms 784396 KB Output is correct
7 Correct 1778 ms 784136 KB Output is correct
8 Correct 1694 ms 784420 KB Output is correct
9 Correct 1826 ms 784132 KB Output is correct
10 Correct 1756 ms 784208 KB Output is correct
11 Correct 1668 ms 784196 KB Output is correct
12 Correct 1757 ms 784512 KB Output is correct
13 Correct 1479 ms 784116 KB Output is correct
14 Correct 1619 ms 784140 KB Output is correct
15 Correct 1702 ms 784212 KB Output is correct
16 Correct 1805 ms 784208 KB Output is correct
17 Correct 1729 ms 784272 KB Output is correct
18 Correct 1637 ms 784208 KB Output is correct
19 Correct 1615 ms 784212 KB Output is correct
20 Correct 1630 ms 784164 KB Output is correct
21 Correct 1720 ms 784464 KB Output is correct
22 Correct 1839 ms 784040 KB Output is correct
23 Correct 1699 ms 784100 KB Output is correct
24 Correct 1692 ms 784404 KB Output is correct
25 Correct 1883 ms 784464 KB Output is correct