Submission #1217074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217074		dreamoon	Race (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // cc_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>> adj[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;
    ++timerIdx;

    int bestSize = 0, heavyChild = -1;
    for (auto [v, w] : adj[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) adj[i].clear();
    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});
    }

    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; // 非葉子

        // -------- 改用 cc_hash_table --------
        cc_hash_table<ll, int, chash> mp;

        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]);
        };
        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]);
        };

        int x = leaf;
        add(tin[x]); // 先加入葉子
        while (parent[x] != -1) {
            int p = parent[x];

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

            // 處理父節點本身
            relax(tin[p], tin[p]);
            add(tin[p]);
            x = p;
        }
    }
    return ans == INF ? -1 : ans;
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:94:33: error: 'y' was not declared in this scope
   94 |                 if (edgeCnt[tin[y]] > edgeCnt[tin[p]] && child != x) {
      |                                 ^