Submission #515842

#	Time	Username	Problem	Language	Result	Execution time	Memory
515842		tabr	Race (IOI11_race)	C++17	100 / 100	568 ms	88824 KiB

race

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

template <class F>
struct y_combinator_result {
    F f;

    template <class T>
    explicit y_combinator_result(T &&f_) : f(std::forward<T>(f_)) {}

    template <class... Args>
    decltype(auto) operator()(Args &&...args) {
        return f(std::ref(*this), std::forward<Args>(args)...);
    }
};

template <class F>
decltype(auto) y_combinator(F &&f) {
    return y_combinator_result<std::decay_t<F>>(std::forward<F>(f));
}

int best_path(int n, int k, int h[][2], int l[]) {
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; i++) {
        g[h[i][0]].emplace_back(i);
        g[h[i][1]].emplace_back(i);
    }
    int ans = n;
    vector<int> depth(n);
    vector<long long> dist(n);
    vector<map<long long, int>> a(n);
    y_combinator([&](auto dfs, int v, int p) -> void {
        vector<int> c;
        for (int id : g[v]) {
            int to = v ^ h[id][0] ^ h[id][1];
            if (to == p) {
                continue;
            }
            c.emplace_back(to);
            depth[to] = depth[v] + 1;
            dist[to] = dist[v] + l[id];
            dfs(to, v);
            long long t = dist[v] + k;
            if (a[to].count(t)) {
                ans = min(ans, a[to][t] - depth[v]);
            }
        }
        if (c.empty()) {
            a[v][dist[v]] = depth[v];
            return;
        }
        sort(c.begin(), c.end(), [&](int i, int j) {
            return a[i].size() > a[j].size();
        });
        swap(a[v], a[c[0]]);
        a[v][dist[v]] = depth[v];
        for (int i = 1; i < (int) c.size(); i++) {
            for (auto q : a[c[i]]) {
                long long t = 2 * dist[v] - q.first + k;
                if (a[v].count(t)) {
                    ans = min(ans, a[v][t] + q.second - 2 * depth[v]);
                }
            }
            for (auto q : a[c[i]]) {
                if (!a[v].count(q.first)) {
                    a[v][q.first] = n;
                }
                a[v][q.first] = min(a[v][q.first], q.second);
            }
        }
    })(0, -1);
    if (ans == n) {
        ans = -1;
    }
    return ans;
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    return 0;
}
#endif

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