Submission #537550

#TimeUsernameProblemLanguageResultExecution timeMemory
537550topovikParkovi (COCI22_parkovi)C++14
0 / 110
872 ms58116 KiB
#include <bits/stdc++.h> #define pb push_back #define f first #define s second using namespace std; typedef long long ll; typedef long double ld; const ll N = 1e6 + 100; const ll M = 1e3 + 10; const ll oo = 1e18 + 7; vector <pair<ll, ll> > a[N]; ll n, k; ll mx_ds; ll kol; pair<ll, ll> dp[N]; set <ll> ans; bool g = 0; pair<ll, ll> Rec(ll x, ll y) { vector <pair<ll, ll> > vc; ll up = 0; for (auto i : a[x]) if (i.f != y) vc.pb(Rec(i.f, x)); else up = i.s; sort(vc.begin(), vc.end()); ll mx = 0; ll mn = (vc.size() > 0 ? vc[0].f : oo); for (auto i : vc) if (mn + i.s > mx_ds) mx = max(mx, i.s); if (mx + up > mx_ds && (mx != 0 || mn > mx_ds)) { if (g) ans.insert(x); kol++; mx = 0; mn = 0; } if (x == 0 && (mx != 0 || mn > mx_ds)) { if (g) ans.insert(x); kol++; return {0, 0}; } mx += up; if (mx == up && mn <= mx_ds) mx = 0; mn += up; if (mn > mx_ds) mx = oo; return {mn, mx}; } bool Check(ll x) { mx_ds = x; kol = 0; Rec(0, 0); return kol <= k; } int main() { ios_base::sync_with_stdio(0); iostream::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; for (ll i = 0; i < n - 1; i++) { ll x, y, z; cin >> x >> y >> z; a[--x].pb({--y, z}); a[y].pb({x, z}); } ll l = 0, r = oo; while (l < r) { ll mdl = (l + r) >> 1; if (Check(mdl)) r = mdl; else l = mdl + 1; } cout << l << endl; g = 1; Check(l); int i = 0; while (ans.size() < k) ans.insert(i++); for (auto i : ans) cout << i + 1 << " "; } /* 5 1 1 2 3 2 3 4 3 4 5 4 5 6 */

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:91:23: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   91 |     while (ans.size() < k) ans.insert(i++);
      |            ~~~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...