제출 #526731

#제출 시각아이디문제언어결과실행 시간메모리
526731chicken337Parkovi (COCI22_parkovi)C++17
0 / 110
428 ms41992 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int MAXN = 200005; int n, K, cur_val, put[MAXN], actual[MAXN]; vector<pair<int, int>> adj[MAXN]; pair<int, bool> dfs(int x, int par){ int mx = 0, d_par = 0, c = 0, has = 0; for(auto& [nxt, wt] : adj[x]){ if(nxt == par){ d_par = wt; continue; } pair<int, bool> res = dfs(nxt, x); if(res.second) c = min(c, res.first), has = 1; else mx = max(mx, res.first); } if(has && mx + c <= 0){ // cout << x << " returning " << (c + d_par > 0 ? d_par : c + d_par) << ' ' << (c+d_par <= 0) << endl; return {(c + d_par > 0 ? d_par : c + d_par), c+d_par <= 0}; } if(mx + d_par > cur_val){ put[x] = 1; // cout << x << " putting and returning " << (d_par - cur_val > 0 ? d_par : d_par - cur_val) << ' ' << 1 << endl; return {d_par - cur_val > 0 ? d_par : d_par - cur_val, 1}; } // cout << x << " returning " << d_par + mx << " 0" << endl; return {d_par + mx, 0}; } bool check(int val){ // cout << "CHECKING " << val << endl; memset(put, 0, sizeof put); int cnt = 0; cur_val = val; dfs(0, -1); for(int i = 0; i < n; i ++) cnt += put[i]; return cnt <= K; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n >> K; for(int i = 1; i < n; i ++){ int a, b, w; cin >> a >> b >> w; adj[a-1].emplace_back(b-1, w); adj[b-1].emplace_back(a-1, w); } int l = 0, r = 1e18, ans = -1; while(l <= r){ int m = (l + r) >> 1; if(check(m)){ ans = m; r = m-1; for(int i = 0; i < n; i ++) actual[i] = put[i]; } else l = m+1; } cout << ans << '\n'; set<int> numbers; int num_taken = 0; for(int i = 0; i < n; i ++) numbers.insert(i); for(int i = 0; i < n; i ++) if(actual[i]){ cout << i+1 << ' '; numbers.erase(i); num_taken ++; } while(num_taken < K){ cout << *numbers.begin()+1 << ' '; numbers.erase(numbers.begin()); num_taken ++; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...