Submission #521579

#	Time	Username	Problem	Language	Result	Execution time	Memory
521579		Cyanmond	Dreaming (IOI13_dreaming)	C++17	100 / 100	132 ms	37580 KiB

dreaming

#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 3 "library2/utility/revrep.hpp"

class ReversedRange {
    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 ReversedRange(const int f, const int l) noexcept
        : first(l - 1), last(std::min(f, l) - 1) {}
    constexpr Iterator begin() const noexcept {
        return first;
    }
    constexpr Iterator end() const noexcept {
        return last;
    }
};

constexpr ReversedRange revrep(const int l, const int r) noexcept {
    return ReversedRange(l, r);
}
constexpr ReversedRange revrep(const int n) noexcept {
    return ReversedRange(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 10 "paper.cpp"

#include "dreaming.h"

struct Edge {
    int to;
    int cost;
};

int N, M, L;
int C;
std::vector<int> A, B, T;
std::vector<std::vector<Edge>> forest;

std::vector<int> components_radius, components_diameter;

void decompose() {
    std::vector<bool> used(N);
    std::vector<std::vector<int>> depths(N);
    auto dfs =
        rec_lambda([&](auto &&f, const int v, const int p, std::vector<int> &vertices) -> int {
            vertices.push_back(v);
            used[v] = true;
            const int c = len(forest[v]);
            if (c == 0) {
                return 0;
            }
            depths[v].resize(c);
            for (const int i : rep(c)) {
                if (forest[v][i].to == p) {
                    depths[v][i] = 0;
                } else {
                    depths[v][i] = f(forest[v][i].to, v, vertices) + forest[v][i].cost;
                }
            }
            return *std::max_element(depths[v].begin(), depths[v].end());
        });

    std::vector<int> parent_depth(N);
    auto reroot = rec_lambda([&](auto &&f, const int v, const int p, const int d) -> void {
        parent_depth[v] = d;
        const int c = len(forest[v]);
        if (c == 0) {
            return;
        }
        std::vector<int> l_max(c + 1), r_max(c + 1);
        for (const int i : rep(c)) {
            l_max[i + 1] = std::max(l_max[i], depths[v][i]);
        }
        for (const int i : revrep(c)) {
            r_max[i] = std::max(r_max[i + 1], depths[v][i]);
        }
        for (const int i : rep(c)) {
            if (forest[v][i].to == p) {
                continue;
            }
            f(forest[v][i].to, v, std::max({d, l_max[i], r_max[i + 1]}) + forest[v][i].cost);
        }
    });

    for (const int i : rep(N)) {
        if (used[i]) {
            continue;
        }
        std::vector<int> vertices;
        dfs(i, N, vertices);
        reroot(i, N, 0);

        auto get_radius = [&]() {
            if (len(vertices) == 1) {
                return 0;
            }
            int res = infty<int>;
            for (const int v : vertices) {
                setmin(res, std::max(parent_depth[v],
                                     *std::max_element(depths[v].begin(), depths[v].end())));
            }
            return res;
        };

        auto get_diameter = [&]() {
            if (len(vertices) == 1) {
                return 0;
            }
            int res = -infty<int>;
            for (const int v : vertices) {
                setmax(res, std::max(parent_depth[v],
                                     *std::max_element(depths[v].begin(), depths[v].end())));
            }
            return res;
        };

        components_radius.push_back(get_radius());
        components_diameter.push_back(get_diameter());
    }
    C = len(components_radius);
}

int solve() {
    decompose();
    const int max_diameter =
        *std::max_element(components_diameter.begin(), components_diameter.end());
    if (C == 1) {
        return max_diameter;
    }
    if (C == 2) {
        return std::max(components_radius[0] + components_radius[1] + L, max_diameter);
    }

    const int max_radius = *std::max_element(components_radius.begin(), components_radius.end());

    auto find_second = [&]() {
        components_radius.erase(
            std::max_element(components_radius.begin(), components_radius.end()));
        return *std::max_element(components_radius.begin(), components_radius.end());
    };

    auto find_third = [&]() {
        // find_second is used
        components_radius.erase(
            std::max_element(components_radius.begin(), components_radius.end()));
        return *std::max_element(components_radius.begin(), components_radius.end());
    };

    const int second_radius = find_second();
    const int third_radius = find_third();
    return std::max(
        {max_diameter, max_radius + second_radius + L, second_radius + third_radius + 2 * L});
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    N = n;
    M = m;
    L = l;
    A.resize(M);
    B.resize(M);
    T.resize(M);
    forest.resize(N);
    for (const int i : rep(M)) {
        A[i] = a[i];
        B[i] = b[i];
        T[i] = t[i];
        forest[A[i]].push_back({B[i], T[i]});
        forest[B[i]].push_back({A[i], T[i]});
    }

    return solve();
}

/*
int main() {
    int n, m, l;
    int a[20], b[20], t[20];
    std::cin >> n >> m >> l;
    for (const int i : rep(m)) {
        std::cin >> a[i] >> b[i] >> t[i];
    }
    std::cout << travelTime(n, m, l, a, b, t) << std::endl;
}
*/

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23