oj.uz

Submission #223914

# Submission time Handle Problem Language Result Execution time Memory
223914 2020-04-16T20:46:00 Z Leonardo_Paes Museum (CEOI17_museum) C++17
100 / 100
 581 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(const int &u, const 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(const int &u, const 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(const int&, const 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 4 ms 640 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 6 ms 640 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 28816 KB Output is correct
2 Correct 215 ms 29184 KB Output is correct
3 Correct 581 ms 164912 KB Output is correct
4 Correct 305 ms 72952 KB Output is correct
5 Correct 439 ms 40312 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 28816 KB Output is correct
2 Correct 215 ms 29184 KB Output is correct
3 Correct 581 ms 164912 KB Output is correct
4 Correct 305 ms 72952 KB Output is correct
5 Correct 439 ms 40312 KB Output is correct
6 Correct 266 ms 23672 KB Output is correct
7 Correct 348 ms 107640 KB Output is correct
8 Correct 441 ms 2784 KB Output is correct
9 Correct 336 ms 2816 KB Output is correct
10 Correct 231 ms 3840 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 4 ms 640 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 6 ms 640 KB Output is correct
6 Correct 251 ms 28816 KB Output is correct
7 Correct 215 ms 29184 KB Output is correct
8 Correct 581 ms 164912 KB Output is correct
9 Correct 305 ms 72952 KB Output is correct
10 Correct 439 ms 40312 KB Output is correct
11 Correct 266 ms 23672 KB Output is correct
12 Correct 348 ms 107640 KB Output is correct
13 Correct 441 ms 2784 KB Output is correct
14 Correct 336 ms 2816 KB Output is correct
15 Correct 231 ms 3840 KB Output is correct
16 Correct 250 ms 29664 KB Output is correct
17 Correct 287 ms 29428 KB Output is correct
18 Correct 317 ms 82680 KB Output is correct
19 Correct 355 ms 2808 KB Output is correct
20 Correct 238 ms 4736 KB Output is correct
21 Correct 508 ms 105724 KB Output is correct
22 Correct 246 ms 29176 KB Output is correct
23 Correct 355 ms 2808 KB Output is correct
24 Correct 248 ms 4864 KB Output is correct
25 Correct 564 ms 169592 KB Output is correct