제출 #1126844

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126844		Dreamy_lovesper	Parkovi (COCI22_parkovi)	C++17	10 / 110	59 ms	1844 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define LIFESUCKS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define pll pair<ll, ll>
#define mll map<ll, ll>
#define vll vector<ll>
#define pb push_back
#define fi first
#define se second
#define all(c) c.begin(),c.end()
#define debug cout<<"I Love You\n";
#define Bitc(x, j) ((x >> j) & 1)
#define fu(i,a,b) for ( ll i = a; i <= b; i++ )
#define fd(i,b,a) for ( ll i = b; i >= a; i-- )

const ll Mod = 1e9 + 7;
const ll inf = (1ll << 31);
const ll lnf = (1ll << 60);

template <class X, class Y>
    bool minimize (X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize (X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }

#define mxn 20'007
ll n, k;
vector<pll> graph[mxn];

namespace Love1 {
    bool check () {
        return ( n <= 20 );
    }

    struct Edge {
        ll d, u;
        bool operator < ( const Edge& other ) const {
            return other.d > d;
        }
    };

    ll f[27];

    void DreamyLove () {
        
        ll sad = lnf;
        ll gf;
        fu ( msk, 1, (1 << n) - 1 ) {
            if ( __builtin_popcount(msk) != k ) continue;
            ll cr = -lnf;
            priority_queue<Edge> Q;
            fu ( i, 1, n ) f[i] = lnf;
            fu ( i, 0, n - 1 ) if ( Bitc(msk, i)) Q.push({0, i + 1}), f[i + 1] = 0;
            while ( !Q.empty()) {
                ll u = Q.top().u, d = Q.top().d;
                Q.pop();
                if ( d > f[u] ) continue;
                for ( pll& it: graph[u]){
                    ll v = it.fi, w = it.se;
                    if ( f[v] <= f[u] + w ) continue;
                    f[v] = f[u] + w;
                    Q.push({ f[v], v });
                }
            }
            fu ( i, 1, n ) maximize(cr, f[i]);
            if( minimize(sad, cr)) gf = msk;
        }    
        cout << sad << '\n';
        fu ( j, 0, n - 1 ) if ( Bitc( gf, j)) cout << j + 1 << ' ';

        //
    }
} // namespace Love1


void lovesper(const ll TestCase){
    cin >> n >> k;
    fu ( i, 2, n ) {
        ll u, v, w; cin >> u >> v >> w;
        graph[u].pb({v, w});
        graph[v].pb({u, w});
    }

    if ( Love1::check()) {
        Love1::DreamyLove();
        return;
    }

}

signed main(){
    LIFESUCKS
    #define name "lovesper"
    // freopen(name".inp", "r", stdin);
    // freopen(name".out", "w", stdout);

    ll test=1;
//    cin >> test;
    for (int i = 1; i <= test; i++){
        lovesper(i);
        if ( i < test ) cout << '\n';
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60