제출 #1256332

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256332		iamhereforfun	Museum (CEOI17_museum)	C++20	20 / 100	47 ms	9920 KiB

museum

// Starcraft 2 enjoyer + luv kd //

#include <bits/stdc++.h>

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 1e4 + 5;
const int M = 4e5 + 5;
const int S = 640;
const int O = 2e5 + 5;
const int K = 15;
const int LG = 21;
const int P = 37;
const long long INF = 1e18 + 5;
const int MOD = 1e9 + 7;
const int nx[] = {0, 1, 0, -1}, ny[] = {1, 0, -1, 0};

int n, k, st, sz[N];
vector<long long> dp1[N];
vector<pair<long long, long long>> dp2[N];
vector<pair<int, int>> adj[N];

void dfs(int c, int p)
{
    sz[c] = 1;
    dp1[c].push_back(0);
    dp2[c].push_back({0, 0});
    dp1[c].push_back(INF);
    dp2[c].push_back({INF, 0});
    dp1[c][0] = 0;
    dp2[c][0] = {0, 0};
    for (auto &[i, w] : adj[c])
    {
        if (i == p)
            continue;
        dfs(i, c);
        for(int x = 0; x < sz[i]; x++)
        {
            dp1[c].push_back(INF);
            dp2[c].push_back({INF, 0});
        }
        for (int x = sz[c]; x >= 0; x--)
        {
            for (int y = sz[i]; y >= 0; y--)
            {
                if (x + y <= k)
                {
                    dp1[c][x + y] = min(dp1[c][x + y], dp1[c][x] + dp1[i][y] + 2*w);
                    if(dp2[c][x + y].first - dp2[c][x + y].second > dp2[c][x].first + dp1[i][y] - dp2[c][x].second + 2*w)
                    {
                        dp2[c][x + y] = {dp2[c][x].first + dp1[i][y] + 2*w, dp2[c][x].second};
                    }
                    if(dp2[c][x + y].first - dp2[c][x + y].second > dp1[c][x] + dp2[i][y].first - dp2[i][y].second + w)
                    {
                        dp2[c][x + y] = {dp2[i][y].first + dp1[c][x] + 2*w, dp2[i][y].second + w};
                    }
                }
            }
        }
        sz[c] += sz[i];
    }
    for (int x = sz[c]; x >= 1; x--)
    {
        dp1[c][x] = min(dp1[c][x - 1], dp1[c][x]);
        dp2[c][x] = min(dp2[c][x - 1], dp2[c][x]);
    }
}

void solve()
{
    cin >> n >> k >> st;
    for (int x = 0; x < n - 1; x++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    dfs(st, 0);
    cout << dp2[st][k].first - dp2[st][k].second;
}

signed main()
{
    // freopen("CP.INP", "r", stdin);
    // freopen("CP.OUT", "w", stdout);
    // freopen("art2.in", "r", stdin);
    // freopen("art2.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}

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