Submission #788738

#TimeUsernameProblemLanguageResultExecution timeMemory
788738hafoParkovi (COCI22_parkovi)C++14
110 / 110
938 ms35288 KiB
#include <bits/stdc++.h> #define ll long long #define ull unsigned ll #define pb push_back #define pa pair<int, int> #define pall pair<ll, int> #define fi first #define se second #define TASK "test" #define Size(x) (int) x.size() #define all(x) x.begin(), x.end() using namespace std; template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;} template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;} const int MOD = 1e9 + 7; const int LOG = 20; const int maxn = 2e5 + 7; const ll oo = 1e18 + 69; int n, k, u, v, w, cnt = 0; vector<pa> g[maxn]; bool placed[maxn]; ll dist[maxn], reach[maxn]; void dfs(int u, int par, ll lim) { dist[u] = oo; reach[u] = 0; for(auto e:g[u]) { int v = e.fi, w = e.se; if(v == par) continue; dfs(v, u, lim); if(reach[v] + min(1LL * w, dist[v]) <= lim) { placed[v] = 0; if(reach[v] + dist[v] > lim) { maxi(reach[u], reach[v] + w); } mini(dist[u], dist[v] + w); } else { placed[v] = 1; cnt++; mini(dist[u], w); } } } bool check(ll lim) { cnt = 0; dfs(1, 0, lim); if(reach[1] + dist[1] <= lim) placed[1] = 0; else { placed[1] = 1; cnt++; } return cnt <= k; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); //freopen(TASK".inp", "r", stdin); //freopen(TASK".out", "w", stdout); cin>>n>>k; for(int i = 1; i < n; i++) { cin>>u>>v>>w; g[u].pb({v, w}); g[v].pb({u, w}); } ll l = 0, r = 1e15, mid, res; while(l <= r) { mid = l + r >> 1; if(check(mid)) { res = mid; r = mid - 1; } else l = mid + 1; } cout<<res<<"\n"; vector<int> ans; check(res); for(int i = 1; i <= n; i++) if(placed[i]) ans.pb(i); for(int i = 1; i <= n; i++) if(Size(ans) < k && !placed[i]) ans.pb(i); for(auto i:ans) cout<<i<<" "; return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:77:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |         mid = l + r >> 1;
      |               ~~^~~
Main.cpp:86:10: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   86 |     check(res);
      |     ~~~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...