Submission #1263262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263262		DangKhoizzzz	Museum (CEOI17_museum)	C++20	0 / 100	453 ms	784460 KiB

museum

#include<bits/stdc++.h>
#define pii pair <int , int>
#define fi first
#define se second
#define arr3 array <int , 3>

using namespace std;

const int maxn = 1e4 + 7;
const int INF = 1e9;
const int mod = 1e9 + 7;

int n , k , x , dp[2][maxn][maxn], sz[maxn];
vector <pii> g[maxn];

void dfs(int u , int p)
{
    sz[u] = 1;
    dp[0][u][1] = dp[1][u][1] = 0;

    for(auto [v , w]: g[u])
    {
        if(v == p) continue;
        dfs(v , u);

        for(int a = sz[u]; a >= 1; a--)
        {
            for(int b = sz[v]; b >= 1; b--)
            {
                dp[0][u][a+b] = min(dp[0][u][a+b] , dp[0][u][a] + dp[0][v][b] + w*2);
                dp[1][u][a+b] = min(dp[1][u][a+b] , dp[0][u][a] + dp[1][v][b] + w);
            }
        }
        sz[u] += sz[v];
    }
}

void solve()
{
    cin >> n >> k >> x;
    for(int i = 1; i < n; i++)
    {
        int u , v , w; 
        cin >> u >> v >> w;
        g[u].push_back({v , w});
        g[v].push_back({u , w});
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++) dp[1][i][j] = dp[0][i][j] = INF;
    }
    dfs(x , x);
    cout << dp[1][x][k] << '\n';
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    solve();
    return 0;
}
   

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