oj.uz

Submission #1022735

# Submission time Handle Problem Language Result Execution time Memory
1022735 2024-07-14T04:12:08 Z anarch_y Museum (CEOI17_museum) C++17
100 / 100
 503 ms 421812 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
#define int long long

vector<int> combine(vector<int> a, vector<int> b, int x){
    vector<int> c(sz(a)+sz(b)-1, 1e18);
    for(int i=0; i<sz(a); i++){
        for(int j=0; j<sz(b); j++){
            c[i+j] = min(c[i+j], a[i]+b[j]+x);
        }
    }
    return c;
}

vector<int> find_min(vector<int> a, vector<int> b){
    vector<int> c(sz(a));
    for(int i=0; i<sz(a); i++){
        c[i] = min(a[i], b[i]);
    }
    return c;
}

const int maxn = 10001;
vector<pair<int, int>> adj[maxn];
vector<int> dp[maxn][2];

void dfs(int s, int p){
    dp[s][0] = {(int)1e18, 0};
    dp[s][1] = {(int)1e18, 0};
    for(auto [u, w]: adj[s]){
        if(u == p) continue;
        dfs(u, s);
        dp[u][0][0] = -2*w; dp[u][1][0] = -w;
        auto c = combine(dp[s][0], dp[u][0], 2*w);
        auto a = combine(dp[s][1], dp[u][0], 2*w);
        auto b = combine(dp[s][0], dp[u][1], w);
        dp[s][0] = c;
        dp[s][1] = find_min(a, b);
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, k, x; cin >> n >> k >> x;
    for(int i=0; i<n-1; i++){
        int a, b, w; cin >> a >> b >> w;
        adj[a].pb({b, w}); adj[b].pb({a, w});
    }
    dfs(x, 0);
    cout << dp[x][1][k];
}

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 6996 KB Output is correct
2 Correct 120 ms 7760 KB Output is correct
3 Correct 432 ms 421812 KB Output is correct
4 Correct 224 ms 126032 KB Output is correct
5 Correct 143 ms 27980 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 6996 KB Output is correct
2 Correct 120 ms 7760 KB Output is correct
3 Correct 432 ms 421812 KB Output is correct
4 Correct 224 ms 126032 KB Output is correct
5 Correct 143 ms 27980 KB Output is correct
6 Correct 130 ms 5608 KB Output is correct
7 Correct 312 ms 238416 KB Output is correct
8 Correct 503 ms 3536 KB Output is correct
9 Correct 393 ms 4100 KB Output is correct
10 Correct 158 ms 5420 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 992 KB Output is correct
3 Correct 1 ms 1112 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 121 ms 6996 KB Output is correct
7 Correct 120 ms 7760 KB Output is correct
8 Correct 432 ms 421812 KB Output is correct
9 Correct 224 ms 126032 KB Output is correct
10 Correct 143 ms 27980 KB Output is correct
11 Correct 130 ms 5608 KB Output is correct
12 Correct 312 ms 238416 KB Output is correct
13 Correct 503 ms 3536 KB Output is correct
14 Correct 393 ms 4100 KB Output is correct
15 Correct 158 ms 5420 KB Output is correct
16 Correct 122 ms 9040 KB Output is correct
17 Correct 121 ms 8528 KB Output is correct
18 Correct 247 ms 155476 KB Output is correct
19 Correct 397 ms 3780 KB Output is correct
20 Correct 139 ms 5952 KB Output is correct
21 Correct 297 ms 220332 KB Output is correct
22 Correct 119 ms 8016 KB Output is correct
23 Correct 433 ms 3536 KB Output is correct
24 Correct 131 ms 5468 KB Output is correct
25 Correct 419 ms 404816 KB Output is correct