Submission #1207763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207763		vicvic	Museum (CEOI17_museum)	C++20	100 / 100	535 ms	785076 KiB

museum

#include <bits/stdc++.h>

using namespace std;
const int NMAX=1e4;
int dp[NMAX+5][NMAX+5][2], n, subtree[NMAX+5], k, x;
vector <pair <int, int>> vec[NMAX+5];
void dfs (int nod, int tatal=0)
{
    subtree[nod]=1;
    dp[nod][1][0]=dp[nod][1][1]=0;
    for (auto adj : vec[nod])
    {
        if (adj.first==tatal)
            continue;
        dfs (adj.first, nod);
        for (int i=min(k, subtree[nod]);i>=0;i--)
        {
            for (int j=min (k-i, subtree[adj.first]);j>=0;j--)
            {
                dp[nod][i+j][1]=min (dp[nod][i+j][1], dp[nod][i][1]+dp[adj.first][j][1]+adj.second*2);
                dp[nod][i+j][0]=min (dp[nod][i+j][0], dp[nod][i][1]+dp[adj.first][j][0]+adj.second);
                dp[nod][i+j][0]=min (dp[nod][i+j][0], dp[nod][i][0]+dp[adj.first][j][1]+adj.second*2);
            }
        }
        subtree[nod]+=subtree[adj.first];
    }
}
int main ()
{
    memset (dp, 0x3f, sizeof (dp));
    cin >> n >> k >> x;
    for (int i=1;i<n;i++)
    {
        int x, y, w;
        cin >> x >> y >> w;
        vec[x].push_back ({y, w});
        vec[y].push_back ({x, w});
    }
    dfs (x);
    cout << min (dp[x][k][0], dp[x][k][1]);
    return 0;
}

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