Submission #889723

#	Time	Username	Problem	Language	Result	Execution time	Memory
889723		The_Samurai	Parkovi (COCI22_parkovi)	C++17	50 / 110	3054 ms	34508 KiB

Main

// 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) {
                        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);
      |                          ~~~~~~~~~~~^~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 0 / 60