Submission #1217047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217047		dreamoon	Race (IOI11_race)	C++20	9 / 100	131 ms	9972 KiB

race

#include <bits/stdc++.h>
#define SZ(x) static_cast<int>((x).size())
using namespace std;
using ll = long long;

int best_path(int N, int K, int H[][2], int L[]) {
    /* ---------- 1. 建樹 ---------- */
    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});
    }

    /* ---------- 2. flatten + 重兒標記 ---------- */
    vector<int> tin(N), tout(N), heavyPar(N, -1), flatSteps(N);
    vector<ll> flatDepth(N);
    int timer = 0;

    auto dfs = [&](auto &&self, int u, int p, ll dSum, int dCnt) -> void {
        // 進入節點 u
        tin[u] = timer;
        flatDepth[timer] = dSum;
        flatSteps[timer] = dCnt;
        ++timer;

        // 找最大子樹 (= 重兒)
        int bestSize = 0, heavyChild = -1;
        for (auto [v, w] : adj[u])
            if (v != p) {
                int before = timer;
                self(self, v, u, dSum + w, dCnt + 1);
                int sub = timer - before;
                if (sub > bestSize) {
                    bestSize = sub;
                    heavyChild = v;
                }
            }
        if (heavyChild != -1) heavyPar[heavyChild] = u;

        tout[u] = timer; // 子樹區間 [tin, tout)
    };
    dfs(dfs, 0, -1, 0LL, 0);

    /* ---------- 3. heavy-light + 小併大 ---------- */
    const int INF = 1e9;
    int answer = INF;

    for (int leaf = 0; leaf < N; ++leaf) {
        if (tin[leaf] + 1 < tout[leaf]) continue; // 非葉子

        unordered_map<ll, int> best; // 距離 → 最少邊數
        auto add = [&](int idx) {
            ll d = flatDepth[idx];
            int s = flatSteps[idx];
            if (!best.count(d)) best[d] = s;
            else best[d] = min(best[d], s);
        };
        auto relax = [&](int idx, int lcaIdx) {
            ll need = K + 2 * flatDepth[lcaIdx] - flatDepth[idx];
            if (best.count(need))
                answer = min(answer,
                             flatSteps[idx] + best[need] - 2 * flatSteps[lcaIdx]);
        };

        add(tin[leaf]); // 把葉子本身先加入
        for (int u = leaf; heavyPar[u] != -1; u = heavyPar[u]) {
            int p = heavyPar[u];

            // 處理父節點 p 的所有「輕兒」子樹
            for (auto [child, _] : adj[p])
                if (child != heavyPar[p] && child != u) {
                    for (int idx = tin[child]; idx < tout[child]; ++idx)
                        relax(idx, tin[p]);
                    for (int idx = tin[child]; idx < tout[child]; ++idx)
                        add(idx);
                }

            // 處理父節點本身
            relax(tin[p], tin[p]);
            add(tin[p]);
        }
    }

    return (answer == INF ? -1 : answer);
}

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