Submission #778837

#	Time	Username	Problem	Language	Result	Execution time	Memory
778837		borisAngelov	Museum (CEOI17_museum)	C++17	20 / 100	1034 ms	784684 KiB

museum

#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 != node)
        {
            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 / 20
• Subtask 2: 0 / 25
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20