Submission #561949

#	Time	Username	Problem	Language	Result	Execution time	Memory
561949		four_specks	Race (IOI11_race)	C++17	100 / 100	319 ms	69820 KiB

race

#include "race.h"

#include <bits/stdc++.h>

using namespace std;

namespace
{
    template <typename Fun>
    struct YCombinator
    {
        template <typename T>
        YCombinator(T &&_fun) : fun(forward<T>(_fun)) {}

        template <typename... Args>
        decltype(auto) operator()(Args &&...args) { return fun(ref(*this), forward<Args>(args)...); }

    private:
        Fun fun;
    };

    template <typename T>
    YCombinator(T &&) -> YCombinator<decay_t<T>>;

    template <typename T>
    bool ckmin(T &lhs, const T &rhs) { return rhs < lhs ? lhs = rhs, 1 : 0; }

    template <typename T>
    bool ckmax(T &lhs, const T &rhs) { return rhs > lhs ? lhs = rhs, 1 : 0; }

} // namespace

int best_path(int N, int K, int H[][2], int L[])
{
    vector<vector<pair<int, int>>> adj(N);
    for (int i = 0; i < N - 1; i++)
        adj[H[i][0]].emplace_back(H[i][1], L[i]),
        adj[H[i][1]].emplace_back(H[i][0], L[i]);

    int res = INT_MAX;

    YCombinator(
    [&](auto self, int u, int p) -> map<int, int>
    {
        map<int, int> mp;
        mp[0] = 0;
        for (auto [v, w] : adj[u])
        {
            if (v != p)
            {
                map<int, int> mp1 = self(v, u);
                mp1[mp1.begin()->first - w] = mp1.begin()->second - 1;
                if ((int)mp.size() < (int)mp1.size())
                    swap(mp, mp1);
                for (auto [x, d] : mp1)
                {
                    if (auto it = mp.find(K - x + mp1.begin()->first + mp.begin()->first); it != mp.end())
                        ckmin(res, d - mp1.begin()->second + it->second - mp.begin()->second);
                }
                for (auto [x, d] : mp1)
                    ckmin(mp.emplace(x - mp1.begin()->first + mp.begin()->first, INT_MAX).first->second, d - mp1.begin()->second + mp.begin()->second);
            }
        }

        return mp;
    })(0, -1);

    return (res != INT_MAX ? res : -1);
}

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