Submission #452019

#	Time	Username	Problem	Language	Result	Execution time	Memory
452019		palilo	Race (IOI11_race)	C++17	0 / 100	1 ms	204 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

namespace std {
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template <class Fun>
class y_combinator_result {
    Fun fun_;

public:
    template <class T>
    explicit y_combinator_result(T&& fun) : fun_(std::forward<T>(fun)) {}

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

template <class Fun>
decltype(auto) y_combinator(Fun&& fun) {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
}; // namespace std

template <class T>
bool chmin(T& _old, T _new) { return _old > _new && (_old = _new, true); }
template <class T>
bool chmax(T& _old, T _new) { return _old < _new && (_old = _new, true); }

int best_path(int n, int k, int e[][2], int w[]) {
    constexpr int INF = 0x3f3f3f3f;
    vector<vector<pair<int, int>>> adj(n);
    for (int i = 0; i < n - 1; ++i) {
        adj[e[i][0]].emplace_back(w[i], e[i][1]);
        adj[e[i][1]].emplace_back(w[i], e[i][0]);
    }
    vector<int> sz(n), dist(n), best(k + 1, INF), checked;
    vector<bool> erased(n);
    vector<pair<int, int>> dists;
    int ans = INF, s;
    auto dfs_sz = y_combinator([&](auto self, int u, int p) -> int {
        sz[u] = 1;
        for (const auto& [w, v] : adj[u]) {
            if (v != p && !erased[v]) {
                sz[u] += self(v, u);
            }
        }
        return sz[u];
    });
    auto dfs_ct = y_combinator([&](auto self, int u, int p) -> int {
        for (const auto& [w, v] : adj[u]) {
            if (v != p && !erased[v] && sz[v] > s / 2) {
                return self(v, u);
            }
        }
        return u;
    });
    auto dfs = y_combinator([&](auto self, int u, int p, int edges) -> void {
        dists.emplace_back(dist[u], edges);
        checked.emplace_back(dist[u]);
        chmin(ans, edges + best[k - dist[u]]);
        for (const auto& [w, v] : adj[u]) {
            if (v != p && !erased[v] && dist[u] + w <= k) {
                dist[v] = dist[u] + w;
                self(v, u, edges + 1);
            }
        }
    });
    y_combinator([&](auto self, int u) -> void {
        s = dfs_sz(u, -1);
        u = dfs_ct(u, -1);
        erased[u] = true;
        for (const auto [w, v] : adj[u]) {
            if (erased[v] || w > k) continue;
            dist[v] = w;
            dfs(v, u, 1);
            for (const auto& [d, e] : dists) {
                chmin(best[e], d);
            }
            chmin(ans, best[k]);
            dists.clear();
        }
        for (const auto& x : checked) {
            best[x] = INF;
        }
        checked.clear();
        for (const auto& [w, v] : adj[u]) {
            if (!erased[v]) {
                self(v);
            }
        }
    })(0);
    return ans == INF ? -1 : ans;
}

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