제출 #1263243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1263243		DangKhoizzzz	Museum (CEOI17_museum)	C++20	100 / 100	465 ms	551148 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] , f[2][maxn][maxn] , sz[maxn];
vector <pii> g[maxn];

void dfs(int u , int p)
{
    sz[u] = 1;
    for(auto [v , w]: g[u])
    {
        if(v != p) dfs(v , u);
    }
    int id = 0;
    f[0][0][0] = f[1][0][0] = f[0][0][1] = f[1][0][1] = 0;
    for(auto [v , w]: g[u])
    {
        if(v == p) continue;
        id++;
        for(int i = sz[u]+1; i <= sz[u] + sz[v]; i++) f[0][id][i] = f[1][id][i] = INF;
        for(int i = 0; i <= sz[u]; i++) 
        {
            f[0][id][i] = f[0][id-1][i];
            f[1][id][i] = f[1][id-1][i];
        }
        f[0][id][0] = f[1][id][0] = 0;
        for(int a = 1; a <= sz[u]; a++)
        {
            for(int b = 0; b <= sz[v]; b++)
            {
                f[0][id][a+b] = min(f[0][id][a+b] , f[0][id-1][a] + dp[0][v][b] + w*2);
                f[1][id][a+b] = min(f[1][id][a+b] , f[0][id-1][a] + dp[1][v][b] + w);
                f[1][id][a+b] = min(f[1][id][a+b] , f[1][id-1][a] + dp[0][v][b] + w*2);
            }
        }
        sz[u] += sz[v];
    }
    for(int i = 0; i <= sz[u]; i++)
    {
        dp[0][u][i] = f[0][id][i];
        dp[1][u][i] = f[1][id][i];
    }
}

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});
    }
    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: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 35 / 35
• Subtask 4: 20 / 20