Submission #1217072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217072		dreamoon	Race (IOI11_race)	C++20	100 / 100	173 ms	52392 KiB

race

#include <algorithm>
#include <iostream>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>   // gp_hash_table
#define SZ(x) static_cast<int>((x).size())
using namespace std;
using namespace __gnu_pbds;

using ll = long long;
const int INF  = 1e9;
const int MAXN = 200'001;

/* -------- 自訂雜湊 (split-mix64) -------- */
struct chash {
    size_t operator()(ll x) const {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return static_cast<size_t>(x ^ (x >> 31));
    }
};

/* -------- 全域陣列 -------- */
vector<pair<int,int>> e[MAXN];

int parent  [MAXN];
int tin     [MAXN], tout[MAXN], timerIdx;
ll  depth   [MAXN];
int edgeCnt [MAXN];

/* -------- DFS：flatten + 找重兒 -------- */
void dfs(int u, int p)
{
    tin[u] = timerIdx++;
    int bestSize = 0, heavyChild = -1;

    for (auto [v,w] : e[u]) if (v != p) {
        depth[timerIdx]   = depth[tin[u]] + w;
        edgeCnt[timerIdx] = edgeCnt[tin[u]] + 1;

        dfs(v, u);

        int sub = tout[v] - tin[v];
        if (sub > bestSize) { bestSize = sub; heavyChild = v; }
    }
    if (heavyChild != -1) parent[heavyChild] = u;
    tout[u] = timerIdx;
}

/* -------- 主解 -------- */
int best_path(int N, int K, int H[][2], int L[])
{
    /* 建樹 */
    for (int i = 0; i < N; ++i) e[i].clear();
    for (int i = 0; i < N - 1; ++i) {
        int u = H[i][0], v = H[i][1], w = L[i];
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }

    fill(parent, parent+N, -1);
    timerIdx = 0;
    dfs(0, -1);

    int ans = INF;

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

        int x = leaf;
        gp_hash_table<ll,int,chash> mp;                 // ← 改用 gp_hash_table

        auto relax = [&](int idx, int lcaIdx) {
            ll need = K + 2*depth[lcaIdx] - depth[idx];
            auto it = mp.find(need);
            if (it != mp.end())
                ans = min(ans,
                          edgeCnt[idx] + it->second - 2*edgeCnt[lcaIdx]);
        };
        auto add = [&](int idx) {
            ll d = depth[idx];
            auto it = mp.find(d);
            if (it == mp.end()) mp[d] = edgeCnt[idx];
            else it->second = min(it->second, edgeCnt[idx]);
        };

        add(tin[x]);
        while (parent[x] != -1) {
            int p = parent[x];

            for (auto [y,_] : e[p]) {
                if (edgeCnt[tin[y]] < edgeCnt[tin[p]] || y == x) continue;
                for (int i = tin[y]; i < tout[y]; ++i) relax(i, tin[p]);
                for (int i = tin[y]; i < tout[y]; ++i) add(i);
            }
            relax(tin[p], tin[p]);
            add  (tin[p]);
            x = p;
        }
    }
    return ans == INF ? -1 : ans;
}

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