Submission #537068

#	Time	Username	Problem	Language	Result	Execution time	Memory
537068		phathnv	Parkovi (COCI22_parkovi)	C++11	110 / 110	1889 ms	46580 KiB

Main

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

const int N = 2e5 + 10;
const long long INF = 1e18;

int n, k;
vector<array<int, 2>> adj[N];
bool choose[N];

array<long long, 2> Dfs(int u, int p, long long r) {
    array<long long, 2> res = {-INF, -INF};
    vector<long long> a = {0};
    for (auto [v, c] : adj[u]) {
        if (v == p) {
            continue;
        }
        auto val = Dfs(v, u, r);
        res[1] = max(res[1], val[1] - c);
        if (val[0] + c > r) {
            choose[v] = true;
            res[1] = max(res[1], r - c);
        } else {
            a.push_back(val[0] + c);
        }
    }
    for (auto d : a) {
        if (d > res[1]) {
            res[0] = max(res[0], d);
        }
    }
    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});
    }
    long long l = 0, r = 1e15, ans = -1;
    while (l <= r) {
        long long mid = (l + r) >> 1;
        fill(choose + 1, choose + 1 + n, false);
        if (Dfs(1, -1, mid)[0] >= 0) {
            choose[1] = true;
        }
        int cnt = accumulate(choose + 1, choose + 1 + n, 0);
        if (cnt <= k) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << ans << '\n';
    fill(choose + 1, choose + 1 + n, false);
    if (Dfs(1, -1, ans)[0] >= 0) {
        choose[1] = true;
    }
    int cnt = accumulate(choose + 1, choose + 1 + n, 0);
    for (int i = 1; i <= n; ++i) {
        if (!choose[i] && cnt < k) {
            ++cnt;
            choose[i] = true;
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (choose[i]) {
            cout << i << ' ';
        }
    }
    cout << '\n';
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'std::array<long long int, 2> Dfs(int, int, long long 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]) {
      |               ^

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