oj.uz

Submission #521553

# Submission time Handle Problem Language Result Execution time Memory
521553 2022-02-02T11:39:40 Z Cyanmond Race (IOI11_race) C++17
100 / 100
 350 ms 85276 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 0 ms 332 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 0 ms 332 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1 ms 332 KB Output is correct
32 Correct 1 ms 332 KB Output is correct
33 Correct 2 ms 332 KB Output is correct
34 Correct 1 ms 460 KB Output is correct
35 Correct 1 ms 460 KB Output is correct
36 Correct 1 ms 460 KB Output is correct
37 Correct 1 ms 460 KB Output is correct
38 Correct 1 ms 460 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 0 ms 332 KB Output is correct
19 Correct 81 ms 7556 KB Output is correct
20 Correct 74 ms 7548 KB Output is correct
21 Correct 73 ms 7492 KB Output is correct
22 Correct 80 ms 7668 KB Output is correct
23 Correct 102 ms 7844 KB Output is correct
24 Correct 80 ms 7740 KB Output is correct
25 Correct 76 ms 25376 KB Output is correct
26 Correct 57 ms 42716 KB Output is correct
27 Correct 159 ms 22976 KB Output is correct
28 Correct 200 ms 85276 KB Output is correct
29 Correct 207 ms 81036 KB Output is correct
30 Correct 157 ms 22908 KB Output is correct
31 Correct 154 ms 22808 KB Output is correct
32 Correct 165 ms 22980 KB Output is correct
33 Correct 154 ms 17720 KB Output is correct
34 Correct 253 ms 28020 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 0 ms 332 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1 ms 332 KB Output is correct
32 Correct 1 ms 332 KB Output is correct
33 Correct 2 ms 332 KB Output is correct
34 Correct 1 ms 460 KB Output is correct
35 Correct 1 ms 460 KB Output is correct
36 Correct 1 ms 460 KB Output is correct
37 Correct 1 ms 460 KB Output is correct
38 Correct 1 ms 460 KB Output is correct
39 Correct 81 ms 7556 KB Output is correct
40 Correct 74 ms 7548 KB Output is correct
41 Correct 73 ms 7492 KB Output is correct
42 Correct 80 ms 7668 KB Output is correct
43 Correct 102 ms 7844 KB Output is correct
44 Correct 80 ms 7740 KB Output is correct
45 Correct 76 ms 25376 KB Output is correct
46 Correct 57 ms 42716 KB Output is correct
47 Correct 159 ms 22976 KB Output is correct
48 Correct 200 ms 85276 KB Output is correct
49 Correct 207 ms 81036 KB Output is correct
50 Correct 157 ms 22908 KB Output is correct
51 Correct 154 ms 22808 KB Output is correct
52 Correct 165 ms 22980 KB Output is correct
53 Correct 154 ms 17720 KB Output is correct
54 Correct 253 ms 28020 KB Output is correct
55 Correct 12 ms 1476 KB Output is correct
56 Correct 6 ms 1076 KB Output is correct
57 Correct 49 ms 9084 KB Output is correct
58 Correct 49 ms 18976 KB Output is correct
59 Correct 72 ms 42692 KB Output is correct
60 Correct 187 ms 82528 KB Output is correct
61 Correct 179 ms 25488 KB Output is correct
62 Correct 150 ms 22820 KB Output is correct
63 Correct 218 ms 22952 KB Output is correct
64 Correct 340 ms 24656 KB Output is correct
65 Correct 350 ms 28920 KB Output is correct
66 Correct 209 ms 71244 KB Output is correct
67 Correct 135 ms 38704 KB Output is correct
68 Correct 240 ms 31400 KB Output is correct
69 Correct 244 ms 31676 KB Output is correct
70 Correct 227 ms 30148 KB Output is correct