Submission #764967

#	Time	Username	Problem	Language	Result	Execution time	Memory
764967		drdilyor	Parkovi (COCI22_parkovi)	C++17	110 / 110	1365 ms	40964 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int inf = 1e9;
constexpr ll infl = 1e18;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, k;
    cin >> n >> k;
    vector<vector<pair<int,int>>> adj(n);
    for( int i = 0; i < n-1; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        a--;b--;
        adj[a].emplace_back(b, w);
        adj[b].emplace_back(a, w);
    }

    int root = 0;
    for (; root < n; root++)
        if (adj[root].size() == 1) break;

    vector<int> built;
    auto check = [&](ll maxd)->bool{
        vector<pair<ll,ll>> memo(n, {-1, -1});
        built.assign(n, 0);
        int parks = 0;
        auto dfs = [&](auto& dfs, int i, int p=-1)->pair<ll,ll> {
            if (memo[i].first !=-1) return memo[i];
            ll close_build = infl;
            ll far = -infl;
            for (auto [e, w] : adj[i]) {
                if (e == p) continue;
                auto [c, f] = dfs(dfs, e, i);
                if (f + w > maxd) {
                    parks++;
                    built[e] = 1;
                    close_build = min(close_build, (ll)w);
                } else close_build = min(close_build, c + w);
            }
            for (auto [e, w] : adj[i]) {
                if (e == p) continue;
                if (built[e]) continue;
                auto [c, f] = dfs(dfs, e, i);
                if (f + w + close_build <= maxd) continue;
                far = max(far, f + w);
            }
            if (close_build > maxd) far = max(far, 0ll);
            //cout << "[maxd,i,close_build,far,parks]=" << maxd << ' ' << i << ',' << close_build << ' ' << far << ',' << parks << endl;
            return memo[i] = {close_build, far};
        };
        auto [c, f] = dfs(dfs, root);
        if (f >= 0) {
            built[root] = 1;
            parks++;
        }
        return parks <= k;
    };

    ll l = 0, r = infl;
    while (l < r-1) {
        ll mid = (l+r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    check(r);
    cout << r << '\n';
    vector<int> parks;
    for (int i = 0; i < n; i++)
        if (built[i]) parks.push_back(i);
    for (int i = 0; i < n; i++)
        if ((int)parks.size() < k  && !built[i])
            parks.push_back(i);
    for (int i : parks) cout << i+1 << ' ';
    cout << '\n';
}

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