Submission #1208619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208619		zedanov	Museum (CEOI17_museum)	C++20	100 / 100	579 ms	784588 KiB

museum

#include <bits/stdc++.h>
using namespace std;

#define zedanov                   \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define el "\n"
const int N = 1e4 + 1, md = 1e9 + 7, inf = 1e9;
// Verify Logic, Check Constrains
// Overflow, Fits in Time/Memory ?

vector<pair<int, int>> a[N];
int sub[N], dp[N][N][2], temp[N][2];

void dfs(int node, int par)
{
    sub[node] = 1;
    dp[node][0][0] = dp[node][0][1] = 0;
    dp[node][1][0] = dp[node][1][1] = 0;

    for (auto& [ch, w] : a[node])
    {
        if (ch == par)
            continue;

        dfs(ch, node);
        for (int i = 0; i <= sub[node] + sub[ch]; i++)
        {
            temp[i][0] = inf;
            temp[i][1] = inf;
        }

        for (int i = 0; i <= sub[node]; i++)
        {
            temp[i][0] = dp[node][i][0];
            temp[i][1] = dp[node][i][1];
        }

        for (int x = 1; x <= sub[node]; x++)
        {
            for (int y = 1; y <= sub[ch]; y++)
            {
                // don't end at node's subtree
                temp[x + y][0] = min(temp[x + y][0], dp[node][x][0] + dp[ch][y][0] + 2 * w);

                // end at nodes' subtree but not in child's
                temp[x + y][1] = min(temp[x + y][1], dp[node][x][1] + dp[ch][y][0] + 2 * w);

                // end at child's subtree
                temp[x + y][1] = min(temp[x + y][1], dp[node][x][0] + dp[ch][y][1] + w);
            }
        }

        sub[node] += sub[ch];
        for (int i = 0; i <= sub[node]; i++)
        {
            dp[node][i][0] = temp[i][0];
            dp[node][i][1] = temp[i][1];
        }
    }
}

void doWork()
{
    int n, k, x;
    cin >> n >> k >> x;

    for (int i = 0; i < n - 1; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        a[u].emplace_back(v, w);
        a[v].emplace_back(u, w);
    }

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

    dfs(x, 0);
    cout << min(dp[x][k][0], dp[x][k][1]);
}

signed main()
{
    zedanov int t = 1;
    // cin >> t;
    while (t--)
        doWork();

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 35 / 35
• Subtask 4: 20 / 20