Submission #1246735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246735		vht2025	Parkovi (COCI22_parkovi)	C++20	0 / 110	170 ms	27392 KiB

Main

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

const int N = 200005;
int n, k;
vector<pair<int, int>> adj[N];
int park[N];

int dfs(int u, int p, int R, int &cnt) {
    int maxDist = 0; // Khoảng cách xa nhất từ u xuống lá chưa được phủ
    for (auto [v, w] : adj[u]) {
        if (v == p) continue;
        int distChild = dfs(v, u, R, cnt);
        if (distChild + w > R) {
            // Cần đặt công viên tại v
            cnt++;
            park[v] = 1;
        } else {
            maxDist = max(maxDist, distChild + w);
        }
    }
    return maxDist;
}

bool valid(int R) {
    memset(park, 0, sizeof(park));
    int cnt = 0;
    int rootDist = dfs(1, 0, R, cnt);
    if (rootDist > R) { // Nếu gốc cũng cần đặt công viên
        cnt++;
        park[1] = 1;
    }
    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].push_back({v, w});
        adj[v].push_back({u, w});
    }

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

    valid(ans); // Tìm lại các vị trí công viên
    vector<int> res;
    for (int i = 1; i <= n; ++i) {
        if (park[i]) res.push_back(i);
    }

    // Đảm bảo đủ k công viên (có thể thêm tự do nếu thiếu)
    while ((int)res.size() < k) res.push_back(1); // thêm tự do ở gốc chẳng hạn

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

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:45:20: warning: overflow in conversion from 'double' to 'int' changes value from '2.0e+14' to '2147483647' [-Woverflow]
   45 |     int l = 0, r = 2e14, ans = 0;
      |                    ^~~~

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