Submission #1210429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210429		ammahmed004	Museum (CEOI17_museum)	C++20	100 / 100	654 ms	706732 KiB

museum

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define FAST ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
#define ll int
#define ld long double
//#define int long long
#define endl "\n"
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define pb push_back
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
const int MOD = 1e9+7  ;
//const int MOD = 998244353  ;
const int N = 1e5+5  ;
const ll INF = 1e9 ;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;


void solve() {
    ll n,k,x;cin>>n>>k>>x;
    vector<pair<ll,ll>> g[n+1];
    for(int i=1;i<n;i++){
        ll u,v,c;cin>>u>>v>>c;
        g[u].pb({v,c});
        g[v].pb({u,c});
    }
    //0 temchi w tarjaach   1 temchi w tarjaa
    vector<vector<array<ll,2>>> dp(n+1,vector<array<ll,2>>(k+1,{INF,INF}));
    vector<ll> childs(n+1,1);
    function<void(int,int)> dfs=[&](int v,int p){
        dp[v][1]=dp[v][0]={0,0};
        for(auto [child,cost] : g[v]){
            if(child == p)continue;
            dfs(child,v);
            vector<array<ll,2>> temp(k+1,{INF,INF});
            for(int i=0;i<=min(k,childs[v]);i++){
                temp[i]=dp[v][i];
            }
            for(int i=0;i<=min(k-1,childs[child]);i++){
                temp[i+1][0]=min(temp[i+1][0],dp[child][i][0]+cost);
                temp[i+1][1]=min(temp[i+1][1],dp[child][i][1]+cost*2);
            }
            for(int i=1;i<=min(k,childs[v]);i++){
                for(int j=0;j<=min(k,childs[child]) && j+i<=k;j++){
                    ll sum=i+j;
                    ll c0=min(dp[v][i][1]+dp[child][j][0]+cost,dp[child][j][1]+cost*2+dp[v][i][0]);
                    temp[sum][0]=min(temp[sum][0],c0);
                    temp[sum][1]=min(temp[sum][1],dp[child][j][1]+cost*2+dp[v][i][1]);
                }
            }
            childs[v]+=childs[child];
            for(int i=0;i<=min(k,childs[v]);i++){
                dp[v][i]=temp[i];
            }
        }
    };
    dfs(x,0);
    cout<<dp[x][k][0]<<endl;
}

signed main() {
    FAST;
    
    ll t=1;
    //cin>>t;
    while(t--) solve();
    
}

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