Submission #1105122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105122		AverageAmogusEnjoyer	Museum (CEOI17_museum)	C++17	100 / 100	859 ms	784960 KiB

museum

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }

mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());

int rng() {
    return abs((int)mrand());
}

// Current challenge: finish CSES problemset!!

const int nax = 10000 + 5, inf = 5e8;
int dp[nax][nax];
int dp2[nax][nax];
vector<pair<int,int>> adj[nax];
int n,k,start_node;
int sz[nax];

void dfs(int x,int p) {
    sz[x] = 1;
    for (int i=1;i<=n;i++)
        dp[x][i] = dp2[x][i] = inf;
    dp[x][1] = 0;
    dp2[x][1] = 0;
    for (auto &[y,c]: adj[x]) if (y != p) {
        dfs(y,x);
        for (int total = sz[x] + sz[y]; total >= 1; total--) {
            for (int other = min(sz[y],total); other >= 0 && total - other <= sz[x]; other--) {
                int me = total - other;
                cmin(dp[x][total],dp[x][me] + dp[y][other] + 2 * c);
                cmin(dp2[x][total],dp[x][me] + dp2[y][other] + c);
                cmin(dp2[x][total],dp2[x][me] + dp[y][other] + 2 * c);
            }
        }
        sz[x] += sz[y];
    }
}

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr);

    cin >> n >> k >> start_node;
    --start_node;
    for (int i=1,a,b,c;i<n;i++) {
        cin >> a >> b >> c;
        --a,--b;
        adj[a].emplace_back(b,c);
        adj[b].emplace_back(a,c);
    }
    dfs(start_node,-1);
    // for (int i=0;i<n;i++) {
    //     cout << "node " << i + 1 << endl;
    //     for (int j=1;j<=sz[i];j++)
    //         cout << "taking " << j << " nodes : " << dp[i][j] << endl;
    // }
    cout << dp2[start_node][k] << "\n";
}

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