oj.uz

Submission #244601

# Submission time Handle Problem Language Result Execution time Memory
244601 2020-07-04T11:29:31 Z apostoldaniel854 Museum (CEOI17_museum) C++14
100 / 100
 566 ms 784508 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

/**
->  We use a simple tree dp:
    dp[node][size][0/1] = the minimum time it takes to visit size nodes in the subtree of node if we start in node
    0 -> we don't visit all
    1 -> we visit all
**/

const int N = 10000;
vector <pair <int, int>> gr[1 + N];

int dp[1 + N][1 + N][2];
int sz[1 + N];

void _ (int &a, int b) {
    if (a > b)
        a = b;
}

void dfs (int node, int par) {
    sz[node] = 1;
    dp[node][1][0] = dp[node][1][1] = 0;
    for (pair <int, int> edge : gr[node]) {
        int son = edge.first;
        int cost = edge.second;
        if (par != son) {
            dfs (son, node);
            for (int cur = sz[node]; cur >= 0; cur--)
                for (int add = sz[son]; add > 0; add--) {
                    _ (dp[node][cur + add][0], dp[node][cur][0] + dp[son][add][0] + 2 * cost);
                    _ (dp[node][cur + add][1], dp[node][cur][0] + dp[son][add][1] + cost);
                    _ (dp[node][cur + add][1], dp[node][cur][1] + dp[son][add][0] + 2 * cost);
                }
            sz[node] += sz[son];
        }
    }
}

int main() {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    int n, k, x;
    cin >> n >> k >> x;
    for (int i = 1; i < n; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        gr[x].pb ({y, c});
        gr[y].pb ({x, c});
    }

    for (int node = 1; node <= n; node++)
        for (int i = 1; i <= n; i++)
            dp[node][i][0] = dp[node][i][1] = (1 << 29);

    dfs (x, 0);
    cout << dp[x][k][1] << "\n";

    return 0;
}

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 535 ms 783992 KB Output is correct
2 Correct 526 ms 783992 KB Output is correct
3 Correct 558 ms 784504 KB Output is correct
4 Correct 541 ms 784248 KB Output is correct
5 Correct 527 ms 784036 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 783992 KB Output is correct
2 Correct 526 ms 783992 KB Output is correct
3 Correct 558 ms 784504 KB Output is correct
4 Correct 541 ms 784248 KB Output is correct
5 Correct 527 ms 784036 KB Output is correct
6 Correct 523 ms 784120 KB Output is correct
7 Correct 538 ms 784248 KB Output is correct
8 Correct 542 ms 783992 KB Output is correct
9 Correct 532 ms 783992 KB Output is correct
10 Correct 514 ms 784120 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 535 ms 783992 KB Output is correct
7 Correct 526 ms 783992 KB Output is correct
8 Correct 558 ms 784504 KB Output is correct
9 Correct 541 ms 784248 KB Output is correct
10 Correct 527 ms 784036 KB Output is correct
11 Correct 523 ms 784120 KB Output is correct
12 Correct 538 ms 784248 KB Output is correct
13 Correct 542 ms 783992 KB Output is correct
14 Correct 532 ms 783992 KB Output is correct
15 Correct 514 ms 784120 KB Output is correct
16 Correct 527 ms 784120 KB Output is correct
17 Correct 551 ms 784124 KB Output is correct
18 Correct 566 ms 784220 KB Output is correct
19 Correct 536 ms 784080 KB Output is correct
20 Correct 519 ms 784120 KB Output is correct
21 Correct 553 ms 784508 KB Output is correct
22 Correct 516 ms 784208 KB Output is correct
23 Correct 532 ms 784120 KB Output is correct
24 Correct 513 ms 783992 KB Output is correct
25 Correct 551 ms 784504 KB Output is correct