Submission #533578

#TimeUsernameProblemLanguageResultExecution timeMemory
533578SlavitaParkovi (COCI22_parkovi)C++14
10 / 110
281 ms20240 KiB
#include <bits/stdc++.h> /*#pragma optimize("O3") #pragma GCC optimize("-O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("fast-math")*/ //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> #define ve vector<int> #define pb push_back #define mp make_pair #define fi first #define se second #define pi pair<int,int> #define all(v) v.begin(),v.end() #define si(v) (int)v.size() #define en '\n' #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> #define ordered_muiltiset tree<int, null_type,less_equal<>, rb_tree_tag,tree_order_statistics_node_update> #define int long long using namespace std; //using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; const int N = 2e5 + 228; const int big = 1e9 + 228; const ll llbig = 1e18 + 228; //ordered_set os; // os.order_of_key(4), (*os.find_by_order(5)) int n, m, ans, k, q, d[N], longest, allsm, pr[N]; ve ansv; vector<pair<int, int>> g[N]; void dfs(int v, int dist, int pr){ if (dist <= d[v]){ d[v] = dist; }else return; for (int i = 0; i < si(g[v]); i++){ int u = g[v][i].fi; int cost = g[v][i].se; if (u == pr) continue; dfs(u, dist + cost, v); } } void dfs2(int v, int dist, int pr){ longest = max(longest, dist); for (int i = 0; i < si(g[v]); i++){ int u = g[v][i].fi; int cost = g[v][i].se; if (u == pr) continue; dfs(u, dist + cost, v); } } bool getbit(int mask, int bit){ bit--; return (mask & (1 << bit)) == (1 << bit); } #undef int int main(){ #define int long long iostream::sync_with_stdio(false); cin.tie(0); ios_base::sync_with_stdio(false); cout.tie(0); //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); cin >> n >> k; vector<pair<int, pair<int, int>>> reb; for (int i = 1; i <= n - 1; i++){ int a, b, d; cin >> a >> b >> d; g[a].pb({b, d}); g[b].pb({a, d}); if (a > b) swap(a, b); reb.pb({a, {b, d}}); allsm += d; } ans = llbig; if (n > 20){ sort(all(reb)); for (int i = 1; i <= n; i++){ pr[i] = pr[i - 1] + reb[i - 1].se.se; } int ans = llbig, ansv; for (int i = 1; i <= n - 1; i++){ int what = max(pr[n - 1] - pr[i - 1], pr[i - 1]); if (ans > what){ ans = what; ansv = i; } } cout << ans << en << ansv; }else{ for (int mask = 1; mask <= (1 << n); mask++){ ve v; for (int i = 1; i <= n; i++){ if (getbit(mask, i)){ v.pb(i); } } if (si(v) != k) continue; for (int i = 1; i <= n; i++) d[i] = llbig; for (int i = 0; i < si(v); i++){ dfs(v[i], 0, -1); } int mx = -llbig; for (int i = 1; i <= n; i++){ mx = max(mx, d[i]); } if (mx < ans){ ans = mx; ansv = v; } } } cout << ans << en; for (int i = 0; i < si(ansv); i++){ cout << ansv[i] << ' '; } 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...