Submission #1186327

#TimeUsernameProblemLanguageResultExecution timeMemory
1186327dostsParkovi (COCI22_parkovi)C++17
0 / 110
161 ms61768 KiB
#include <bits/stdc++.h> #define int long long #define pii pair<int,int> #define vi vector<int> #define ff first #define ss second #define all(x) x.begin(),x.end() #define sp << " " << using namespace std; const int N = 2e5+10,MOD = 998244353,inf = 2e12; int n,k; vector<pii> edges[N]; int up[N][20]; vi d(N); vi leaves; void dfs(int node,int p,int der = 0) { if (node > 1 && edges[node].size() == 1) leaves.push_back(node); up[node][0] = p; d[node] = der; for (int i = 1;i<20;i++) up[node][i] = up[up[node][i-1]][i-1]; for (auto it : edges[node]) { if (it.ff == p) continue; dfs(it.ff,node,der+it.ss); } } vi active(N,1),usedd(N,0); vi anss; int find(int node,int k) { int cur = node; for (int i = 19;i>=0;i--) { if (d[node]-d[up[cur][i]] <= k && active[up[cur][i]]) cur = up[cur][i]; } return cur; } bool check(int dep,bool construct = 0) { active.assign(n+1,1); int used = 0; priority_queue<pii> pq; for (auto it : leaves) { int gogo = find(it,dep); pq.push({d[gogo],gogo}); } while (!pq.empty()) { int f = pq.top().ss; pq.pop(); if (!active[f]) continue; if (construct) anss.push_back(f),usedd[f] = 1; used++; queue<pii> q; q.push({f,0}); active[f] = 0; while (!q.empty()) { int tp = q.front().ff,c = q.front().ss; q.pop(); for (auto it : edges[tp]) { if (it.ss+c > dep) continue; if (!active[it.ff]) continue; active[it.ff] = 0; q.push({it.ff,c+it.ss}); } } int gogo = find(f,dep); if (d[f]-d[up[gogo][0]] > dep) pq.push({d[up[gogo][0]],up[gogo][0]}); } if (construct) { for (int i=1;i<=n;i++) { if (!usedd[i] && anss.size() < k) anss.push_back(i); } } return used <= k; } void solve() { cin >> n >> k; for (int i=1;i<n;i++) { int a,b,w; cin >> a >> b >> w; edges[a].push_back({b,w}); edges[b].push_back({a,w}); } dfs(1,1); int l = 0; int r = 1e15; while (l<=r) { int m = (l+r) >> 1; if (check(m)) r = m-1; else l = m+1; } cout << l << '\n'; check(l,1); sort(all(anss)); for (auto it : anss) cout << it << ' '; cout << '\n'; } signed main() { ios_base::sync_with_stdio(0);cin.tie(0); #ifdef Dodi freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int t = 1; //cin >> t; while (t --> 0) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...