Submission #451981

#	Time	Username	Problem	Language	Result	Execution time	Memory
451981		palilo	Race (IOI11_race)	C++17	43 / 100	290 ms	27120 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[]) {
    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<pair<int, int>> dists;
    vector<int> sz(n), dist(n);
    vector<bool> erased(n);
    int 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 {
        if (dist[u] > k) return;
        dists.emplace_back(dist[u], edges);
        for (const auto& [w, v] : adj[u]) {
            if (v != p && !erased[v]) {
                dist[v] = dist[u] + w;
                self(v, u, edges + 1);
            }
        }
    });
    int ans = INT_MAX, tick = 0;
    vector<pair<int, int>> table(k);
    y_combinator([&](auto self, int u) -> void {
        s = dfs_sz(u, -1);
        u = dfs_ct(u, -1);
        erased[u] = true;
        --tick;
        for (const auto& [w, v] : adj[u]) {
            if (erased[v]) continue;
            dists.clear();
            dist[v] = w;
            dfs(v, u, 1);
            for (const auto& [d1, e1] : dists) {
                if (d1 == k) {
                    chmin(ans, e1);
                } else {
                    const auto d2 = k - d1;
                    if (table[d2].first == tick) {
                        chmin(ans, e1 + table[d2].second);
                    }
                }
            }
            for (const auto& [d, e] : dists) {
                chmin(table[d], pair(tick, e));
            }
        }
        for (const auto& [w, v] : adj[u]) {
            if (!erased[v]) {
                self(v);
            }
        }
    })(0);
    return ans == INT_MAX ? -1 : ans;
}

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