제출 #1246756

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246756		vht2025	Parkovi (COCI22_parkovi)	C++20	0 / 110	330 ms	29876 KiB

Main

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

const int N = 200005;
vector<pair<int, int>> adj[N];
int n, k, cnt;
bool placed[N];  // Đánh dấu node đặt công viên

// Hàm DFS trả khoảng cách xa nhất từ node u xuống lá chưa được phủ
long long dfs(int u, int par, long long mid) {
    long long maxDist = 0;
    for (auto [v, w] : adj[u]) {
        if (v == par) continue;
        long long childDist = dfs(v, u, mid);

        // Nếu nhánh con vượt quá mid, phải đặt công viên tại v
        if (childDist + w > mid) {
            placed[v] = true;
            cnt++;
        } else {
            // Cập nhật khoảng cách lớn nhất chưa được phủ
            maxDist = max(maxDist, childDist + w);
        }
    }
    return placed[u] ? 0 : maxDist;
}

// Kiểm tra bán kính mid hợp lệ hay không?
bool check(long long mid) {
    memset(placed, 0, sizeof(placed));
    cnt = 0;

    long long rootDist = dfs(1, 0, mid);
    // Node gốc chưa được phủ thì phải đặt thêm công viên
    if (rootDist > mid) {
        placed[1] = true;
        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;
        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 mid = (l + r) / 2;
        if (check(mid)) {
            res = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    // Chạy lại lần nữa để xác định các node đặt công viên
    check(res);

    vector<int> parks;
    for (int i = 1; i <= n; ++i) {
        if (placed[i]) parks.push_back(i);
    }

    // Nếu thiếu thì thêm tự do (theo yêu cầu của đề)
    for (int i = 1; parks.size() < k && i <= n; ++i) {
        if (!placed[i]) parks.push_back(i);
    }

    // Output
    cout << res << '\n';
    for (int i = 0; i < k; ++i)
        cout << parks[i] << " ";
    cout << '\n';
}

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