Submission #1246757

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246757		vht2025	Parkovi (COCI22_parkovi)	C++20	110 / 110	467 ms	31812 KiB

Main

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

const int N = 200005;

vector<pair<int, int>> adj[N];
bool flag[N], marked[N];
int n, k, cnt;
long long mid;

// DFS trả khoảng cách chính xác như code AC của bạn
long long dfs(int u, int p) {
    if (adj[u].size() == 1 && u != 0) return 0;

    long long mi = LLONG_MAX, ma = LLONG_MIN;
    for (auto [v, w] : adj[u]) {
        if (v == p) continue;
        long long dist = dfs(v, u);

        if (dist == 0 && flag[v]) {
            mi = min(mi, 0LL);
            ma = max(ma, 0LL);
            continue;
        }

        if (dist < 0 && dist + w <= 0)
            flag[u] = 1;

        if (dist < 0 && dist + w > 0)
            dist = 0;
        else
            dist += w;

        if (dist > mid) {
            cnt++;
            marked[v] = 1;
            flag[v] = 1;
            dist = min(-mid + w, 0LL);
            if (-mid + w <= 0) flag[u] = 1;
        }

        ma = max(ma, dist);
        mi = min(mi, dist);
    }

    if (-mi >= ma) return mi;
    return ma;
}

// Check bán kính mid hợp lệ
bool check(long long R) {
    mid = R;
    cnt = 0;
    memset(flag, 0, sizeof(flag));
    memset(marked, 0, sizeof(marked));

    if (dfs(0, -1) > 0 || !flag[0]) {
        marked[0] = 1;
        cnt++;
    }

    return cnt <= k;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k;
    for (int i = 1, u, v, w; i < n; i++) {
        cin >> u >> v >> w;
        u--; v--;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    long long l = 0, r = (1LL << 60), res = r;
    while (l <= r) {
        long long m = (l + r) / 2;
        if (check(m)) {
            res = m;
            r = m - 1;
        } else l = m + 1;
    }

    // Tìm lại vị trí các node đặt công viên
    check(res);
    vector<int> ans;
    for (int i = 0; i < n; ++i)
        if (marked[i]) ans.push_back(i+1);

    for (int i = 0; ans.size() < k && i < n; ++i)
        if (!marked[i]) ans.push_back(i+1);

    cout << res << "\n";
    for (int x : ans) cout << x << " ";
    cout << "\n";
}

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