Submission #889725

#TimeUsernameProblemLanguageResultExecution timeMemory
889725The_SamuraiParkovi (COCI22_parkovi)C++17
30 / 110
3074 ms30720 KiB
// I stand with PALESTINE //#pragma GCC optimize("Ofast,O3") //#pragma GCC target("avx,avx2") #include "bits/stdc++.h" using namespace std; using ll = long long; const int N = 2e5 + 5; vector<vector<pair<int, int>>> g(N); vector<ll> height(N); vector<int> par(N); void dfs(int u) { for (auto [v, w]: g[u]) { if (par[u] == v) continue; par[v] = u; height[v] = height[u] + w; dfs(v); } } void solve() { int n, k; cin >> n >> k; for (int i = 1; i < n; i++) { int u, v, w; cin >> u >> v >> w; g[u].emplace_back(v, w); g[v].emplace_back(u, w); } dfs(1); vector<bool> marked, copy; vector<pair<ll, int>> vec(n); for (int i = 1; i <= n; i++) vec[i - 1] = make_pair(height[i], i); sort(vec.rbegin(), vec.rend()); // for (int i = 1; i <= n; i++) cout << height[i] << ' '; // cout << endl; // for (int i = 0; i < n; i++) cout << vec[i].second << ' '; // cout << endl; auto check = [&](ll m) -> bool { vector<bool> vis(n + 1); marked.assign(n + 1, false); int need = 0; for (auto [d, u]: vec) { if (vis[u]) continue; need++; int root = u; while (root != 1 and height[u] - height[par[root]] <= m) root = par[root]; queue<tuple<ll, int, int>> q; q.emplace(0, root, 0); vis[root] = marked[root] = true; while (!q.empty()) { auto [d, v, p] = q.front(); q.pop(); for (auto [vv, w]: g[v]) { if (vv != p and d + w <= m and !vis[vv]) { vis[vv] = true; q.emplace(d + w, vv, v); } } } } // cout << m << ' ' << need << ' ' << count(marked.begin(), marked.end(), true) << endl; return need <= k; }; ll lx = 0, rx = 1e18, best = -1; while (lx <= rx) { ll mid = (lx + rx) >> 1; if (check(mid)) { best = mid; copy = marked; rx = mid - 1; } else { lx = mid + 1; } } cout << best << '\n'; vector<int> ans; for (int i = 1; i <= n; i++) if (copy[i]) ans.emplace_back(i); for (int i = 1; i <= n; i++) { if (!copy[i] and ans.size() < k) ans.emplace_back(i); } for (int x: ans) cout << x << ' '; } int main() { cin.tie(0)->sync_with_stdio(false); #ifdef sunnatov freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int q = 1; // cin >> q; while (q--) { solve(); cout << '\n'; } }

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:84:37: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |         if (!copy[i] and ans.size() < k) ans.emplace_back(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...