Submission #1125386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125386		ardadut	Museum (CEOI17_museum)	C++20	0 / 100	102 ms	4236 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<ll>> adj;
vector<vector<ll>> dp;
map<pair<ll,ll>,ll> mapp;
vector<bool> vis;

inline vector<ll> total_min(vector<ll> a, vector<ll> b, ll cost){
    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] + b[j]);
            }else{
                combined[i+j] = min(combined[i+j],min(a[i] + 2 * (b[j] + cost), 2 * a[i] + b[j] + cost));
            }
        }
    }
    return combined;
}

inline void process(ll room){

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

    for(auto go : adj[room]){
        if(vis[go]) continue;
        ll cost;
        if(go > room){
            swap(go,room);
            cost = mapp[{go,room}];
            swap(go,room);
        }else cost = mapp[{go,room}];

        process(go);
        dp[room] = total_min(dp[room],dp[go],cost);
    }

}

inline void solve(){

    cin >> n >> k >> x;
    adj.resize(n+1);
    dp.resize(n+1);
    vis.resize(n+1,0);

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

    process(x);

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

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

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