Submission #1126858

#TimeUsernameProblemLanguageResultExecution timeMemory
1126858Dreamy_lovesperParkovi (COCI22_parkovi)C++17
10 / 110
76 ms29508 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...