Submission #825959

#TimeUsernameProblemLanguageResultExecution timeMemory
825959fdnfksdParkovi (COCI22_parkovi)C++14
110 / 110
1373 ms38372 KiB
#include <bits/stdc++.h> #define taskname "cargroup" using namespace std; #define int long long typedef long long ll; typedef pair<int,int> pli; typedef unsigned long long ull; #define fi first #define se second #define pb push_back #define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); const ll maxN=2e5+10; // a la thg chon gan nhat // b la thg ko thoa man xa nhat ll a[maxN],b[maxN]; const ll inf=1e15; vector<pli>g[maxN]; #define fi first #define se second ll cnt=0; vector<ll>trace; bool in[maxN]; void dfs(ll u,ll p,ll mid) { a[u]=inf; b[u]=0; for(auto vv:g[u]) { int v=vv.fi; int w=vv.se; if(v==p) continue; dfs(v,u,mid); } for(auto vv:g[u]) { int v=vv.fi; int w=vv.se; if(v==p) continue; if(b[v]!=-1&&b[v]+w>mid) { trace.pb(v); in[v]=true; cnt++; a[v]=0; a[u]=min(a[u],w); b[v]=-1; } else { if(b[v]!=-1) b[u]=max(b[u],b[v]+w); a[u]=min(a[u],a[v]+w); } } if(a[u]+b[u]<=mid) { b[u]=-1; } if(u==1&&b[1]!=-1) { cnt++; trace.pb(1); in[1]=true; } } ll k,n; bool check(ll mid) { trace.clear(); for(int i=1;i<=n;i++) in[i]=false; cnt=0; dfs(1,0,mid); return cnt<=k; } //ll n; void solve() { cin >> n >> k; for(int i=1;i<n;i++) { ll u,v,w; cin >> u >> v >> w; g[u].pb({v,w}); g[v].pb({u,w}); } ll low=0,high=3e14; while(low<=high) { ll mid=low+high>>1; if(check(mid)) high=mid-1; else low=mid+1; } cout << low<<'\n'; check(low); for(int i=1;i<=n;i++) { if(in[i]==false&&trace.size()<k) trace.pb(i),in[i]=true; } for(auto zz:trace) cout << zz<<' '; } signed main() { faster // freopen(taskname".INP","r",stdin); // freopen(taskname".OUT","w",stdout); solve(); return 0; }

Compilation message (stderr)

Main.cpp: In function 'void dfs(ll, ll, ll)':
Main.cpp:31:13: warning: unused variable 'w' [-Wunused-variable]
   31 |         int w=vv.se;
      |             ^
Main.cpp: In function 'void solve()':
Main.cpp:89:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |         ll mid=low+high>>1;
      |                ~~~^~~~~
Main.cpp:97:38: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   97 |         if(in[i]==false&&trace.size()<k) trace.pb(i),in[i]=true;
      |                          ~~~~~~~~~~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...