oj.uz

Submission #223910

# Submission time Handle Problem Language Result Execution time Memory
223910 2020-04-16T20:42:11 Z Leonardo_Paes Museum (CEOI17_museum) C++17
100 / 100
 426 ms 169848 KB 
#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

const int maxn = 1e4+10, inf = 0x3f3f3f3f;

typedef pair<int,int> pii;

int n, k, x, siz[maxn], dp[maxn][maxn][2];

vector<pii> grafo[maxn];

void dfs(int u, int p = 0){
    siz[u] = 1;

    for(auto v : grafo[u]){
        if(v.f == p) continue;

        dfs(v.f, u);

        siz[u] += siz[v.f];
    }
}

int solve(int u, int p = 0){
    int sizes = 1, d;

    for(auto v : grafo[u]){
        if(v.f == p) continue;

        solve(v.f, u);

        sizes += siz[v.f];

        d = v.s;

        for(int i=sizes; i>=2; i--){
            for(int j=max(0, i-sizes+siz[v.f]); j<=min(i, siz[v.f]); j++){
                dp[u][i][0] = min({dp[u][i][0], dp[u][i-j][0] + dp[v.f][j][1]
                + 2*d, dp[u][i-j][1] + dp[v.f][j][0] + d});
                dp[u][i][1] = min({dp[u][i][1], dp[u][i-j][1] + dp[v.f][j][1] + 2*d});
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    cin >> n >> k >> x;

    for(int i=1; i<n; i++){
        int u, v, d;

        cin >> u >> v >> d;

        grafo[u].push_back({v, d});
        grafo[v].push_back({u, d});
    }

    dfs(x);

    for(int i=1; i<=n; i++){
        for(int j=2; j<=siz[i]; j++){
            dp[i][j][0] = dp[i][j][1] = inf;
        }
    }

    solve(x);

    cout << dp[x][k][0] << endl;

    return 0;
}

Compilation message

museum.cpp: In function 'int solve(int, int)':
museum.cpp:48:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 28920 KB Output is correct
2 Correct 165 ms 29148 KB Output is correct
3 Correct 356 ms 165140 KB Output is correct
4 Correct 224 ms 73088 KB Output is correct
5 Correct 179 ms 40184 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 28920 KB Output is correct
2 Correct 165 ms 29148 KB Output is correct
3 Correct 356 ms 165140 KB Output is correct
4 Correct 224 ms 73088 KB Output is correct
5 Correct 179 ms 40184 KB Output is correct
6 Correct 160 ms 23552 KB Output is correct
7 Correct 283 ms 107768 KB Output is correct
8 Correct 426 ms 2688 KB Output is correct
9 Correct 330 ms 2936 KB Output is correct
10 Correct 178 ms 3960 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 169 ms 28920 KB Output is correct
7 Correct 165 ms 29148 KB Output is correct
8 Correct 356 ms 165140 KB Output is correct
9 Correct 224 ms 73088 KB Output is correct
10 Correct 179 ms 40184 KB Output is correct
11 Correct 160 ms 23552 KB Output is correct
12 Correct 283 ms 107768 KB Output is correct
13 Correct 426 ms 2688 KB Output is correct
14 Correct 330 ms 2936 KB Output is correct
15 Correct 178 ms 3960 KB Output is correct
16 Correct 162 ms 29568 KB Output is correct
17 Correct 168 ms 29312 KB Output is correct
18 Correct 244 ms 82680 KB Output is correct
19 Correct 357 ms 2884 KB Output is correct
20 Correct 161 ms 4736 KB Output is correct
21 Correct 269 ms 105976 KB Output is correct
22 Correct 161 ms 29056 KB Output is correct
23 Correct 354 ms 2804 KB Output is correct
24 Correct 163 ms 4736 KB Output is correct
25 Correct 358 ms 169848 KB Output is correct