Submission #1119162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119162		LonlyR	Museum (CEOI17_museum)	C++17	100 / 100	409 ms	784972 KiB

museum

#include<bits/stdc++.h>

using namespace std;
const int maxn = 10004;
int n, k, x;
int f[maxn][maxn], g[maxn][maxn], sub[maxn];
vector<pair<int,int>> adj[maxn];

inline void MIN(int &x, int y)
{
    x = min(x, y);
}

void merge(int x, int y, int w)
{
    for (int i = sub[x]; i >= 0; i--)
        for (int j = sub[y]; j >= 0; j--)
        {
            MIN(f[x][i + j], min(f[x][i] + g[y][j] + w * 2, g[x][i] + f[y][j] + w));
            MIN(g[x][i + j], g[x][i] + g[y][j] + w * 2);
        }
    sub[x] += sub[y];
}

void dfs(int x, int p = 0)
{
    f[x][1] = g[x][1] = 0;
    sub[x] = 1;
    for (auto [i, j] : adj[x]) if (i != p)
    {
        dfs(i, x);
        merge(x, i, j);
    }
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n >> k >> x;
    for (int i = 1, u, v, w; i < n; i++)
        cin >> u >> v >> w,
        adj[u].emplace_back(v, w),
        adj[v].emplace_back(u, w);
    memset(f, 0x3f, sizeof f);
    memset(g, 0x3f, sizeof g);
    dfs(x);
    cout << min(f[x][k], g[x][k]);
}

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