Submission #521553

#	Time	Username	Problem	Language	Result	Execution time	Memory
521553		Cyanmond	Race (IOI11_race)	C++17	100 / 100	350 ms	85276 KiB

race

#line 1 "paper.cpp"
#include <bits/stdc++.h>

#line 3 "library2/utility/infty.hpp"

template <typename T, T Div = 2> constexpr T infty = std::numeric_limits<T>::max() / Div;
#line 3 "library2/utility/len.hpp"

template <class Container> int len(const Container&c){
    return static_cast<int>(std::size(c));
}
#line 2 "library2/utility/rec_lambda.hpp"

template <class F> class RecursiveLambda {
    F f;

  public:
    explicit constexpr RecursiveLambda(F &&f_) : f(std::forward<F>(f_)) {}
    template <class... Args> constexpr auto operator()(Args &&...args) const {
        return f(*this, std::forward<Args>(args)...);
    }
};

template <class F> constexpr decltype(auto) rec_lambda(F &&f) {
    return RecursiveLambda<F>(std::forward<F>(f));
}
#line 3 "library2/utility/rep.hpp"

class Range {
    struct Iterator {
        int itr;
        constexpr Iterator(const int pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept {
            ++itr;
        }
        constexpr bool operator!=(const Iterator &other) const noexcept {
            return itr != other.itr;
        }
        constexpr int operator*() const noexcept {
            return itr;
        }
    };
    const Iterator first, last;

  public:
    explicit constexpr Range(const int f, const int l) noexcept
        : first(f), last(std::max(f, l)) {}
    constexpr Iterator begin() const noexcept {
        return first;
    }
    constexpr Iterator end() const noexcept {
        return last;
    }
};

constexpr Range rep(const int l, const int r) noexcept {
    return Range(l, r);
}
constexpr Range rep(const int n) noexcept {
    return Range(0, n);
}
#line 2 "library2/utility/setmax.hpp"

template <typename T> bool setmax(T &lhs, const T &rhs) {
    if (lhs < rhs) {
        lhs = rhs;
        return true;
    }
    return false;
}
#line 2 "library2/utility/setmin.hpp"

template <typename T> bool setmin(T& lhs, const T& rhs) {
    if (lhs > rhs) {
        lhs = rhs;
        return true;
    }
    return false;
}
#line 9 "paper.cpp"

#include "race.h"

int N;
int K;
struct Edge {
    int to;
    int cost;
};
std::vector<std::vector<Edge>> Tree;

struct DpData {
    std::map<int, int> d;
    int adj;
    int depth;
    // real key : d.key + adj
    // real value : depth - d.value

    int size() const {
        return len(d);
    }
};

void merge(DpData &a, DpData &b) {
    assert(a.size() >= b.size());
    for (const auto &[key, value] : b.d) {
        const int r = key + b.adj - a.adj;
        if (a.d.find(r) == a.d.end()) {
            a.d[r] = a.depth - (b.depth - value);
        } else {
            setmax(a.d[r], a.depth - (b.depth - value));
        }
    }
}

int calc_dp() {
    int answer = infty<int>;

    auto dfs = rec_lambda([&](auto &&f, const int v, const int p) -> DpData {
        if (v != 0 and len(Tree[v]) == 1) {
            DpData ret;
            ret.adj = 0;
            ret.depth = 0;
            ret.d[0] = 0;
            return ret;
        }

        const int c = len(Tree[v]);
        std::vector<DpData> children(c);

        auto collect = [&]() {
            int count = 0;
            for (const auto [to, cost] : Tree[v]) {
                if (to == p) {
                    children[count].adj = -1;
                } else {
                    children[count] = f(to, v);
                    children[count].adj += cost;
                    ++children[count].depth;
                }
                ++count;
            }
            int base = (int)(std::max_element(children.begin(), children.end(),
                                              [](const DpData &a, const DpData &b) {
                                                  return a.size() < b.size();
                                              }) -
                             children.begin());
            return base;
        };

        int base = collect();
        for (const int i : rep(c)) {
            if (i == base) {
                continue;
            }
            if (children[i].adj == -1) {
                continue;
            }
            for (const auto &[key, value] : children[i].d) {
                const int r = K - (key + children[i].adj + children[base].adj);
                if (children[base].d.find(r) != children[base].d.end()) {
                    setmin(answer, (children[i].depth - value) +
                                       (children[base].depth - children[base].d[r]));
                }
            }
            merge(children[base], children[i]);
        }

        children[base].d[-children[base].adj] = children[base].depth;
        const int r = K - children[base].adj;
        if (children[base].d.find(r) != children[base].d.end()) {
            setmin(answer, children[base].depth - children[base].d[r]);
        }
        return std::move(children[base]);
    });

    dfs(0, N);
    return answer == infty<int> ? -1 : answer;
}

int best_path(int n, int k, int H[][2], int L[]) {
    N = n;
    K = k;
    Tree.resize(N);
    for (const int i : rep(N - 1)) {
        Tree[H[i][0]].push_back({H[i][1], L[i]});
        Tree[H[i][1]].push_back({H[i][0], L[i]});
    }
    return calc_dp();
}

/*
int main() {
    int n, k;
    std::cin >> n >> k;
    int H[20][2];
    int L[20];
    for (const int i : rep(n - 1)) {
        int a, b, l;
        std::cin >> a >> b >> l;
        H[i][0] = a, H[i][1] = b;
        L[i] = l;
    }
    std::cout << best_path(n, k, H, L) << std::endl;
}
*/

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