oj.uz

Submission #778838

# Submission time Handle Problem Language Result Execution time Memory
778838 2023-07-10T19:56:21 Z borisAngelov Museum (CEOI17_museum) C++17
100 / 100
 699 ms 784948 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 10005;
const int inf = 2000000000;

int n, k, start;

vector<pair<int, unsigned int>> g[maxn];

unsigned int dp1[maxn][maxn];
unsigned int dp2[maxn][maxn];

int subtree_size[maxn];

void dfs(int node, int par)
{
    subtree_size[node] = 1;

    for (auto [next_node, w] : g[node])
    {
        if (next_node != par)
        {
            dfs(next_node, node);
        }
    }

    dp1[node][1] = 0;
    dp2[node][1] = 0;

    for (auto [next_node, w] : g[node])
    {
        if (next_node != par)
        {
            for (int i = subtree_size[node]; i >= 0; --i)
            {
                for (int j = subtree_size[next_node]; j >= 0; --j)
                {
                    dp1[node][i + j] = min(dp1[node][i + j], dp1[node][i] + dp1[next_node][j] + 2 * w);
                    dp2[node][i + j] = min(dp2[node][i + j], dp2[node][i] + dp1[next_node][j] + 2 * w);
                    dp2[node][i + j] = min(dp2[node][i + j], dp1[node][i] + dp2[next_node][j] + 1 * w);
                    dp2[node][i + j] = min(dp2[node][i + j], dp1[node][i] + dp1[next_node][j] + 1 * w);
                }
            }

            subtree_size[node] += subtree_size[next_node];
        }
    }
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> k >> start;

    for (int i = 1; i <= n - 1; ++i)
    {
        int x, y, w;
        cin >> x >> y >> w;

        g[x].push_back(make_pair(y, w));
        g[y].push_back(make_pair(x, w));
    }

    for (int i = 0; i <= n; ++i)
    {
        for (int j = 0; j <= n; ++j)
        {
            dp1[i][j] = inf;
            dp2[i][j] = inf;
        }
    }

    dfs(start, -1);

    cout << dp2[start][k] << endl;

    return 0;
}

/*
11 8 3
1 3 3
3 2 5
6 4 5
1 11 3
9 1 2
9 10 2
3 7 10
6 7 1
7 8 1
7 5 1
*/

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 784232 KB Output is correct
2 Correct 420 ms 784224 KB Output is correct
3 Correct 488 ms 784640 KB Output is correct
4 Correct 444 ms 784432 KB Output is correct
5 Correct 434 ms 784444 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 784232 KB Output is correct
2 Correct 420 ms 784224 KB Output is correct
3 Correct 488 ms 784640 KB Output is correct
4 Correct 444 ms 784432 KB Output is correct
5 Correct 434 ms 784444 KB Output is correct
6 Correct 424 ms 784312 KB Output is correct
7 Correct 474 ms 784664 KB Output is correct
8 Correct 699 ms 784308 KB Output is correct
9 Correct 599 ms 784308 KB Output is correct
10 Correct 449 ms 784332 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 0 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 0 ms 724 KB Output is correct
5 Correct 0 ms 724 KB Output is correct
6 Correct 443 ms 784232 KB Output is correct
7 Correct 420 ms 784224 KB Output is correct
8 Correct 488 ms 784640 KB Output is correct
9 Correct 444 ms 784432 KB Output is correct
10 Correct 434 ms 784444 KB Output is correct
11 Correct 424 ms 784312 KB Output is correct
12 Correct 474 ms 784664 KB Output is correct
13 Correct 699 ms 784308 KB Output is correct
14 Correct 599 ms 784308 KB Output is correct
15 Correct 449 ms 784332 KB Output is correct
16 Correct 424 ms 784460 KB Output is correct
17 Correct 441 ms 784372 KB Output is correct
18 Correct 456 ms 784536 KB Output is correct
19 Correct 631 ms 784368 KB Output is correct
20 Correct 435 ms 784412 KB Output is correct
21 Correct 471 ms 784716 KB Output is correct
22 Correct 428 ms 784356 KB Output is correct
23 Correct 628 ms 784416 KB Output is correct
24 Correct 438 ms 784416 KB Output is correct
25 Correct 492 ms 784948 KB Output is correct