Submission #1125415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125415		ardadut	Museum (CEOI17_museum)	C++20	100 / 100	512 ms	402304 KiB

museum

#include <bits/stdc++.h>
    
#define ll long long
#define pb push_back
#define endl "\n"
#define vec vector<ll>
#define vecvec vector<vector<ll>>
    
using namespace std;
    
/*#define FileName ""
string Ghhhh = ".in";
string Ghhhhh = ".out";
ifstream Girdi(FileName + Ghhhh);
ofstream Cikti(FileName + Ghhhhh);
#define cin Girdi
#define cout Cikti*/

const ll INF = 1e15;
ll n,k,x;
vector<vector<pair<ll,ll>>> adj;
vector<vector<vector<ll>>> dp;
map<pair<ll,ll>,ll> mapp;

inline vector<ll> comp(vector<ll> vec1, vector<ll> vec2){
    vector<ll> ans(vec1.size());
    for(ll i = 0 ; i < vec1.size() ; i++){
        ans[i] = min(vec1[i],vec2[i]);
    }
    return ans;
}

inline vector<ll> total_min(vector<ll> a, vector<ll> b, ll cost,bool type){
    vector<ll> combined(a.size() + b.size() - 1, INF);
    combined[0] = 0;
    for(ll i = 1 ; i < a.size() ; i++){
        for(ll j = 0 ; j < b.size() ; j++){
            if(j == 0){
                combined[i+j] = min(combined[i+j],a[i]);
            }else{
                combined[i+j] = min(combined[i+j], a[i] + b[j] + (type ? cost * 2 : cost));
            }
            
        }
    }
    return combined;
}

inline void process(ll room, ll prev_room){

    dp[room][0] = {0,0};
    dp[room][1] = {0,0};

    for(auto go : adj[room]){
        if(prev_room == go.first) continue;
        process(go.first,room);
        vector<ll> vec1 = total_min(dp[room][1],dp[go.first][0],go.second,0);
        vector<ll> vec2 = total_min(dp[room][0],dp[go.first][1],go.second,1);
        dp[room][0] = comp(vec1,vec2);
        dp[room][1] = total_min(dp[room][1],dp[go.first][1],go.second,1);
    }

}

inline void solve(){

    cin >> n >> k >> x;
    adj.resize(n+1);
    dp.resize(n+1,vector<vector<ll>>(2));

    for(ll i = 1 ; i < n ; i++){
        ll a,b,w;
        cin >> a >> b >> w;
        adj[a].pb({b,w});
        adj[b].pb({a,w});
    }

    process(x,-1);

    cout << dp[x][0][k] << endl;

}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    
}

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