Submission #825827

#TimeUsernameProblemLanguageResultExecution timeMemory
825827karriganParkovi (COCI22_parkovi)C++14
10 / 110
1220 ms39780 KiB
#include<bits/stdc++.h> using namespace std; #define all(fl) fl.begin(),fl.end() #define pb push_back #define fi first #define se second #define for1(i,j,k) for(int i=j;i<=k;i++) #define for2(i,j,k) for(int i=j;i>=k;i--) #define for3(i,j,k,l) for(int i=j;i<=k;i+=l) #define lb lower_bound #define ub upper_bound #define sz(a) (int)a.size() #define pii pair<int,int> #define pli pair<long long,int> #define pil pair<int,long long> #define gcd __gcd #define lcm(x,y) x*y/__gcd(x,y) const int maxn=2e5+9; const long long inf=1e15; vector<pil>a[maxn]; int n,k; struct ver{ long long maxdis; int num; long long mindis; ver (){ maxdis=0; num=0; mindis=inf; } }b[maxn]; vector<int>take; void dfs(int u,int par,long long mid){ //cerr<<u<<'\n'; if (sz(a[u])==1&&a[u][0].fi==par){ //cerr<<u<<'\n'; for (auto v:a[u]){ if (v.se>mid){ b[u].mindis=0; b[u].maxdis=-1; //cerr<<u<<'\n'; take.pb(u); b[u].num=1; } else { b[u].maxdis=v.se; } } return; } for (auto v:a[u]){ if (v.fi==par)continue; dfs(v.fi,u,mid); b[u].maxdis=max(b[u].maxdis,b[v.fi].maxdis); b[u].num+=b[v.fi].num; b[u].mindis=min(b[u].mindis,b[v.fi].mindis+v.se); } if (b[u].mindis+b[u].maxdis<=mid){ b[u].maxdis=-1; } //if (u==8)cout<<b[u].mindis<<" "<<b[u].maxdis<<'\n'; for (auto v:a[u]){ if (v.fi==par){ if (b[u].maxdis==-1){ continue; } if (b[u].maxdis+v.se>mid){ b[u].num++; //cerr<<u<<'\n'; take.pb(u); b[u].mindis=0; b[u].maxdis=-1; } else { b[u].maxdis+=v.se; } } } if (u==1){ if (b[u].maxdis!=-1){ b[u].num++; take.pb(u); //cerr<<u<<'\n'; } } } bool check(long long mid){ take.clear(); for1(i,1,n){ b[i]=ver(); } //cerr<<b[8].num<<'\n'; dfs(1,0,mid); if (b[1].num>k)return false; return true; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); //freopen("KTREE.INP","r",stdin); //freopen("KTREE.OUT","w",stdout); cin>>n>>k; for1(i,1,n-1){ int u,v; long long w; cin>>u>>v>>w; a[u].pb({v,w}); a[v].pb({u,w}); } long long l=0,r=2e14,ans=2e14; while (l<=r){ long long mid=(l+r)/2; if (check(mid)){ r=mid-1; ans=mid; } else l=mid+1; } cout<<ans<<'\n'; check(ans); for (auto v:take)cout<<v<<" "; //cout<<check(7); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...