Submission #1126858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126858		Dreamy_lovesper	Parkovi (COCI22_parkovi)	C++17	10 / 110	76 ms	29508 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 200'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

namespace Love3 {
    bool check () {
        fu ( i, 1, n ) {
            if ( (i == 1 || i == n) && ( graph[i].size() == 1 )) continue;
            if ( graph[i].size() != 2 ) return 0;
        }
        return 1;
    }

    ll g[mxn], pref[mxn], suf[mxn];

    void dfs ( ll u, ll p ) {
        for ( pll& it: graph[u] ) {
            ll v = it.fi, w = it.se;
            if ( v == p ) continue;
            pref[v] = pref[u] + w;
            dfs ( v, u );
            suf[u] = suf[v] + w;
        }
    }
    void DreamyLove () {
        
        ll sad = lnf, gf = 1;
        dfs(1, 0);
        // fu ( i, 1, n ) cout << i << "  " << pref[i] << ' ' << suf[i] << '\n';
        fu ( i, 1, n ) if( minimize(sad, max(pref[i], suf[i]))) gf = i;

        cout << sad << '\n' << gf;

        //
    }
} // namespace Love3

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;
    }

    if ( Love3::check()) {
        Love3::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