Submission #536849

#	Time	Username	Problem	Language	Result	Execution time	Memory
536849		phathnv	Parkovi (COCI22_parkovi)	C++11	50 / 110	3083 ms	33356 KiB

Main

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

const int N = 2e5 + 10;

int n, k;
long long dist[N], maxRem[N];
array<int, 2> par[N];
vector<array<int, 2>> adj[N];
vector<int> ord;
bool mark[N], choose[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, int p, long long rem) {
    if (rem <= maxRem[u]) {
        return;
    }
    maxRem[u] = rem;
    mark[u] = true;
    for (auto [v, c] : adj[u]) {
        if (v == p) {
            continue;
        }
        Dfs2(v, u, rem - c);
    }
}

int calc(long long r) {
    fill(mark + 1, mark + 1 + n, false);
    fill(choose + 1, choose + 1 + n, false);
    fill(maxRem + 1, maxRem + 1 + n, -1);
    int res = 0;
    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;
        choose[u] = true;
        Dfs2(u, -1, 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);
        if (cnt <= k) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << ans << '\n';
    int cnt = calc(ans);
    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 '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, int, long long int)':
Main.cpp:30:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |     for (auto [v, c] : adj[u]) {
      |               ^

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