oj.uz

Submission #223915

# Submission time Handle Problem Language Result Execution time Memory
223915 2020-04-16T20:46:31 Z Leonardo_Paes Museum (CEOI17_museum) C++17
100 / 100
 440 ms 169592 KB 
#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

#pragma "Ofast"

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];

inline 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];
    }
}

inline 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:8:0: warning: ignoring #pragma "Ofast"  [-Wunknown-pragmas]
 #pragma "Ofast"
 
museum.cpp: In function 'int solve(int, int)':
museum.cpp:50: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 165 ms 28920 KB Output is correct
2 Correct 177 ms 29184 KB Output is correct
3 Correct 352 ms 164904 KB Output is correct
4 Correct 230 ms 72956 KB Output is correct
5 Correct 177 ms 40292 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 28920 KB Output is correct
2 Correct 177 ms 29184 KB Output is correct
3 Correct 352 ms 164904 KB Output is correct
4 Correct 230 ms 72956 KB Output is correct
5 Correct 177 ms 40292 KB Output is correct
6 Correct 168 ms 23424 KB Output is correct
7 Correct 285 ms 107768 KB Output is correct
8 Correct 440 ms 2808 KB Output is correct
9 Correct 337 ms 2936 KB Output is correct
10 Correct 180 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 165 ms 28920 KB Output is correct
7 Correct 177 ms 29184 KB Output is correct
8 Correct 352 ms 164904 KB Output is correct
9 Correct 230 ms 72956 KB Output is correct
10 Correct 177 ms 40292 KB Output is correct
11 Correct 168 ms 23424 KB Output is correct
12 Correct 285 ms 107768 KB Output is correct
13 Correct 440 ms 2808 KB Output is correct
14 Correct 337 ms 2936 KB Output is correct
15 Correct 180 ms 3960 KB Output is correct
16 Correct 166 ms 29568 KB Output is correct
17 Correct 166 ms 29304 KB Output is correct
18 Correct 238 ms 82680 KB Output is correct
19 Correct 358 ms 2808 KB Output is correct
20 Correct 166 ms 4736 KB Output is correct
21 Correct 279 ms 105852 KB Output is correct
22 Correct 160 ms 29056 KB Output is correct
23 Correct 367 ms 2812 KB Output is correct
24 Correct 162 ms 4736 KB Output is correct
25 Correct 354 ms 169592 KB Output is correct