Submission #536836

#	Time	Username	Problem	Language	Result	Execution time	Memory
536836		phathnv	Parkovi (COCI22_parkovi)	C++11	30 / 110	3088 ms	36904 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

int n, k;
long long dist[N];
array<int, 2> par[N];
vector<array<int, 2>> adj[N];
vector<int> ord;
bool mark[N];

void Dfs1(int u, int p) {
    for (auto [v, c] : adj[u]) {
        if (v == p) {
            continue;
        }
        dist[v] = dist[u] + c;
        par[v] = {u, c};
        Dfs1(v, u);
    }
}

void Dfs2(int u, long long rem) {
    if (mark[u] || rem < 0) {
        return;
    }
    mark[u] = true;
    for (auto [v, c] : adj[u]) {
        Dfs2(v, rem - c);
    }
}

vector<int> calc(long long r) {
    fill(mark + 1, mark + 1 + n, false);
    vector<int> res;
    for (auto u : ord) {
        if (mark[u]) {
            continue;
        }
        long long rem = r;
        while (par[u][0] && rem >= par[u][1]) {
            rem -= par[u][1];
            u = par[u][0];
        }
        res.push_back(u);
        Dfs2(u, r);
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i < n; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }
    Dfs1(1, -1);
    ord.resize(n);
    iota(ord.begin(), ord.end(), 1);
    sort(ord.begin(), ord.end(), [&](int u, int v){
            return dist[u] > dist[v];
         });
    long long l = 0, r = 1e15, ans = -1;
    while (l <= r) {
        long long mid = (l + r) >> 1;
        int cnt = calc(mid).size();
        if (cnt <= k) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << ans << '\n';
    vector<int> tmp = calc(ans);
    fill(mark + 1, mark + 1 + n, false);
    for (auto u : tmp) {
        mark[u] = true;
    }
    for (int i = 1; i <= n; ++i) {
        if (!mark[i] && (int)tmp.size() < k) {
            tmp.push_back(i);
        }
    }
    sort(tmp.begin(), tmp.end());
    for (int x : tmp) {
        cout << x << ' ';
    }
    cout << '\n';
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void Dfs1(int, int)':
Main.cpp:14:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |     for (auto [v, c] : adj[u]) {
      |               ^
Main.cpp: In function 'void Dfs2(int, long long int)':
Main.cpp:29:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |     for (auto [v, c] : adj[u]) {
      |               ^

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