Submission #1286536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286536		harryleee	Race (IOI11_race)	C++20	100 / 100	715 ms	49448 KiB

race

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

// Chữ ký: H là mảng (N-1) x 2, L là mảng (N-1).
// Trả về minimum number of highways, hoặc -1 nếu không tồn tại.
int best_path(int N, int K, int H[][2], int L[]) {
    if (N <= 1) return -1;
    int n = N;
    int k = K;

    vector<vector<pair<int,int>>> adj(n);
    for (int i = 0; i < n - 1; ++i) {
        int u = H[i][0], v = H[i][1], w = L[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    vector<int> cnt(n, 0);
    vector<char> del(n, 0);
    int ans = INT_MAX;

    // DFS để đếm kích thước subtree
    function<void(int,int)> dfs_cnt = [&](int u, int p) {
        cnt[u] = 1;
        for (auto &e : adj[u]) {
            int v = e.first;
            if (v == p || del[v]) continue;
            dfs_cnt(v, u);
            cnt[u] += cnt[v];
        }
    };

    // Tìm centroid của cây có root u, kích thước sz = cnt[root]
    function<int(int,int,int)> find_centroid = [&](int u, int p, int sz) -> int {
        for (auto &e : adj[u]) {
            int v = e.first;
            if (v == p || del[v]) continue;
            if (cnt[v] > sz / 2) return find_centroid(v, u, sz);
        }
        return u;
    };

    // DFS thu thập (distance, number_of_highways) từ một nhánh
    function<void(int,int,int,int,vector<pair<int,int>>&)> dfs_solve =
        [&](int u, int p, int dist, int highways, vector<pair<int,int>> &vec) {
            if (dist > k) return; // không cần tiếp tục
            vec.push_back({dist, highways});
            for (auto &e : adj[u]) {
                int v = e.first, w = e.second;
                if (v == p || del[v]) continue;
                dfs_solve(v, u, dist + w, highways + 1, vec);
            }
        };

    // Hàm đệ quy centroid-decomposition
    function<void(int)> solve = [&](int start) {
        dfs_cnt(start, -1);
        int centroid = find_centroid(start, -1, cnt[start]);
        del[centroid] = 1;

        // mp lưu map: distance -> min highways để đạt distance từ centroid qua các nhánh đã xử lý
        unordered_map<int,int> mp;
        mp.reserve(256);
        mp[0] = 0; // từ centroid đến chính nó: distance 0, highways 0

        for (auto &e : adj[centroid]) {
            int v = e.first, w = e.second;
            if (del[v]) continue;
            vector<pair<int,int>> vec;
            dfs_solve(v, centroid, w, 1, vec);

            // 1) kiểm tra kết hợp vec với các khoảng đã lưu trong mp (không dùng vec hiện tại để tránh ghép trong cùng 1 nhánh)
            for (auto &pr : vec) {
                int dis = pr.first, num = pr.second;
                auto it = mp.find(k - dis);
                if (it != mp.end()) {
                    ans = min(ans, it->second + num);
                }
            }

            // 2) cập nhật mp bằng vec (sau khi kiểm tra)
            for (auto &pr : vec) {
                int dis = pr.first, num = pr.second;
                auto it = mp.find(dis);
                if (it == mp.end()) mp[dis] = num;
                else if (num < it->second) it->second = num;
            }
        }

        // tiếp tục với các thành phần con
        for (auto &e : adj[centroid]) {
            int v = e.first;
            if (!del[v]) solve(v);
        }
    };

    solve(0);
    if (ans == INT_MAX) return -1;
    return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57