Submission #1175150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175150		bangan	Combo (IOI18_combo)	C++20	Compilation error	0 ms	0 KiB

combo

#include "race.h"
#include <bits/stdc++.h>

using i64 = long long;
using i2 = std::array<int, 2>;

int best_path(int N, int K, int H[][2], int L[]) {
    std::vector<std::vector<i2>> adj(N);
    for (int i = 0; i < N - 1; i++) {
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }

    std::vector<int> sz(N, 1), imp(N, -1), h(N);
    std::vector<i64> d(N);
    auto prep = [&](auto self, int v, int f) -> void {
        for (auto [u, w] : adj[v]) {
            if (u != f) {
                h[u] = h[v] + 1;
                d[u] = d[v] + w;
                self(self, u, v);
                sz[v] += sz[u];
                if (imp[v] == -1 || sz[imp[v]] < sz[u]) {
                    imp[v] = u;
                }
            }
        }
    };
    prep(prep, 0, 0);

    std::vector<i64> t = d;
    std::sort(t.begin(), t.end());
    t.erase(std::unique(t.begin(), t.end()), t.end());

    std::map<i64, int> key;
    for (int i = 0; i < t.size(); i++) {
        key[t[i]] = i;
    }

    auto cmp = [&h](int i, int j) {
        return h[i] < h[j];
    };
    std::vector per((int) t.size(), std::set<int, decltype(cmp)> (cmp));

    int ans = N;
    auto add = [&](auto self, int v, int f) -> void {
        per[key[d[v]]].insert(v);
        for (auto [u, w] : adj[v]) {
            if (u != f) {
                self(self, u, v);
            }
        }
    };
    auto rem = [&](auto self, int v, int f) -> void {
        per[key[d[v]]].erase(v);
        for (auto [u, w] : adj[v]) {
            if (u != f) {
                self(self, u, v);
            }
        }
    };
    auto calc = [&](auto self, int v, int f, int r) -> void {
        i64 req = K + 2 * d[r] - d[v];
        if (key.contains(req) && !per[key[req]].empty()) {
            int u = *per[key[req]].begin();
            ans = std::min(ans, h[v] + h[u] - 2 * h[r]);
        }

        for (auto [u, w] : adj[v]) {
            if (u != f) {
                self(self, u, v, r);
            }
        }
    };
    auto sep = [&](int v) {
        i64 req = K + d[v];
        if (key.count(req) && !per[key[req]].empty()) {
            int u = *per[key[req]].begin();
            ans = std::min(ans, h[u] - h[v]);
        }
        per[key[d[v]]].insert(v);
    };

    auto dfs = [&](auto self, int v, int f) -> void {
        for (auto [u, w] : adj[v]) {
            if (u != f && u != imp[v]) {
                self(self, u, v);
                rem(rem, u, v);
            }
        }
        if (imp[v] != -1) {
            self(self, imp[v], v);
        }

        for (auto [u, w] : adj[v]) {
            if (u != f && u != imp[v]) {
                calc(calc, u, v, v);
                add(add, u, v);
            }
        }

        sep(v);
    };
    dfs(dfs, 0, 0);

    if (ans == N) {
        return -1;
    } else {
        return ans;
    }
}

Compilation message (stderr)

combo.cpp:1:10: fatal error: race.h: No such file or directory
    1 | #include "race.h"
      |          ^~~~~~~~
compilation terminated.