Submission #533553

#TimeUsernameProblemLanguageResultExecution timeMemory
533553SlavitaParkovi (COCI22_parkovi)C++14
0 / 110
3091 ms26968 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; 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; 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}); } ve ansv; int ans = llbig; if (k == 1){ for (int i = 1; i <= n; i++) d[i] = llbig; for (int i = 1; i <= n; i++){ longest = 0; dfs2(i, 0, -1); if (longest < ans){ ans = longest; ansv.resize(0); ansv.pb(i); } } }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...