oj.uz

Submission #223909

# Submission time Handle Problem Language Result Execution time Memory
223909 2020-04-16T20:40:52 Z Leonardo_Paes Museum (CEOI17_museum) C++17
100 / 100
 818 ms 785272 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<=n; 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 583 ms 784800 KB Output is correct
2 Correct 525 ms 784888 KB Output is correct
3 Correct 643 ms 785144 KB Output is correct
4 Correct 600 ms 784784 KB Output is correct
5 Correct 567 ms 784760 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 784800 KB Output is correct
2 Correct 525 ms 784888 KB Output is correct
3 Correct 643 ms 785144 KB Output is correct
4 Correct 600 ms 784784 KB Output is correct
5 Correct 567 ms 784760 KB Output is correct
6 Correct 556 ms 784632 KB Output is correct
7 Correct 647 ms 784888 KB Output is correct
8 Correct 818 ms 784976 KB Output is correct
9 Correct 756 ms 784760 KB Output is correct
10 Correct 543 ms 784760 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 583 ms 784800 KB Output is correct
7 Correct 525 ms 784888 KB Output is correct
8 Correct 643 ms 785144 KB Output is correct
9 Correct 600 ms 784784 KB Output is correct
10 Correct 567 ms 784760 KB Output is correct
11 Correct 556 ms 784632 KB Output is correct
12 Correct 647 ms 784888 KB Output is correct
13 Correct 818 ms 784976 KB Output is correct
14 Correct 756 ms 784760 KB Output is correct
15 Correct 543 ms 784760 KB Output is correct
16 Correct 526 ms 784780 KB Output is correct
17 Correct 577 ms 784760 KB Output is correct
18 Correct 568 ms 784888 KB Output is correct
19 Correct 730 ms 784952 KB Output is correct
20 Correct 547 ms 784760 KB Output is correct
21 Correct 597 ms 785168 KB Output is correct
22 Correct 526 ms 784780 KB Output is correct
23 Correct 762 ms 784888 KB Output is correct
24 Correct 532 ms 784760 KB Output is correct
25 Correct 664 ms 785272 KB Output is correct