제출 #1125413

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125413		ardadut	Museum (CEOI17_museum)	C++20	0 / 100	163 ms	10296 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);

    for(ll i = 1 ; i <= n ; i++){
        cout << "i: " << i << endl;
        for(auto it : dp[i][0]){
            cout << it << " ";
        }
        cout << endl;
        for(auto it : dp[i][1]){
            cout << it << " ";
        }
        cout << endl << endl;
    }

    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: 0 / 20
• Subtask 2: 0 / 25
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20