Submission #1246733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246733		vht2025	Parkovi (COCI22_parkovi)	C++20	0 / 110	288 ms	33520 KiB

Main

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

const long long INF = 1e18;
int n, k;
vector<pair<int, long long>> adj[200005];
vector<int> parks;

int dfs(int u, int p, long long R, vector<int>& parkAt) {
    int need = 0; // 0: không cần phủ, 1: cần phủ tiếp tục
    long long maxChild = -INF; // khoảng cách xa nhất chưa được phủ từ nhánh con

    for (auto [v, w] : adj[u]) {
        if (v == p) continue;
        int childRes = dfs(v, u, R, parkAt);
        if (childRes != -INF) maxChild = max(maxChild, childRes + w);
    }

    if (maxChild == -INF) maxChild = 0; // là lá

    if (maxChild >= R) {
        parkAt[u] = 1;
        parks.push_back(u);
        return -INF; // reset lại, đỉnh này đã được phủ
    } else {
        return maxChild;
    }
}

// Kiểm tra với bán kính R cần tối thiểu bao nhiêu parks
bool check(long long R) {
    parks.clear();
    vector<int> parkAt(n + 1, 0);
    int res = dfs(1, 0, R, parkAt);
    if (res >= R) { // Nếu từ root về chưa được phủ thì phải đặt thêm 1 công viên
        parks.push_back(1);
    }
    return parks.size() <= k;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i < n; ++i) {
        int a, b;
        long long w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }

    long long l = 0, r = 1e14, ans = 0;
    while (l <= r) {
        long long mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    // In lại phương án
    check(ans);
    cout << ans << '\n';
    for (int i = 0; i < k; ++i) {
        cout << parks[i] << " ";
    }
    cout << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int dfs(int, int, long long int, std::vector<int>&)':
Main.cpp:24:16: warning: overflow in conversion from 'long long int' to 'int' changes value from '-1000000000000000000' to '1486618624' [-Woverflow]
   24 |         return -INF; // reset lại, đỉnh này đã được phủ
      |                ^~~~

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