Submission #867758

#TimeUsernameProblemLanguageResultExecution timeMemory
867758epicci23Parkovi (COCI22_parkovi)C++17
40 / 110
3098 ms68432 KiB
#include "bits/stdc++.h" using namespace std; #define pb push_back #define endl "\n" #define int long long #pragma GCC optimize ("O3") #define sz(x) ((int)(x).size()) #define all(x) (x).begin(),(x).end() constexpr int N = 2e5 + 5; constexpr int INF = 1e18; int n,k; vector<array<int,2>> v[N]; bool ok=1; int vis[N]; int dp[N]; int depth[N]; multiset<int> s[N]; int ck; inline void dfs(int c,int p,int d){ if(!ok) return; depth[c]=d; s[c].clear(); s[c].insert(d); for(array<int,2> x:v[c]){ int u=x[0],co=x[1]; if(u==p) continue; dfs(u,c,d+co); dp[c]=min(dp[c],dp[u]); if(sz(s[c])<sz(s[u])) swap(s[c],s[u]); for(int y:s[u]) s[c].insert(y); } while(!s[c].empty()){ if(*s[c].begin() <= ck + 2*d - dp[c]) s[c].erase(s[c].find(*s[c].begin())); else break; } if(s[c].empty()) return; int u = *s[c].rbegin(); if(u>ck+d){ ok=0; return; } if(c==1){ vis[c]=1; dp[c]=d; s[c].clear(); return; } if(u-depth[p]>ck){ vis[c]=1; dp[c]=d; s[c].clear(); return; } } inline bool check(int x){ ok=1; fill(dp,dp+N,INF); fill(vis,vis+N,0); ck=x; dfs(1,0,0); if(s[1].empty() && ok && count(vis,vis+N,1)<=k) return 1; return 0; } void solve(){ cin >> n >> k; for(int i=1;i<n;i++){ int a,b,c; cin >> a >> b >> c; v[a].pb({b,c}); v[b].pb({a,c}); } int l=0,r=(int)1e15; while(l<r){ int m=(l+r)/2; if(check(m)) r=m; else l=m+1; } cout << l << endl; check(l); vector<int> ans; for(int i=1;i<=n;i++) if(vis[i]) ans.pb(i); for(int i=1;i<=n;i++) if(!vis[i] && sz(ans)<k) ans.pb(i); for(int x:ans) cout << x << " "; cout << endl; } int32_t main(){ cin.tie(0); ios::sync_with_stdio(0); int t=1;//cin >> t; while(t--) solve(); 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...