제출 #522585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
522585		Cyanmond	즐거운 행로 (APIO20_fun)	C++17	26 / 100	15 ms	460 KiB

fun

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

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

using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
#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 8 "paper.cpp"

int hoursRequired(int X, int Y);

int attractionsBehind(int X, int Y);

std::vector<int> createFunTour(int N, int Q) {
    if (N <= 500) {
        std::vector<std::vector<int>> Tree(N);
        for (const int i : rep(N)) {
            for (const int j : rep(i + 1, N)) {
                if (hoursRequired(i, j) == 1) {
                    Tree[i].push_back(j);
                    Tree[j].push_back(i);
                }
            }
        }
        auto dfs =
            rec_lambda([&](auto &&f, const int v, const int p, std::vector<int> &dist) -> void {
                for (const int t : Tree[v]) {
                    if (t == p) {
                        continue;
                    }
                    dist[t] = dist[v] + 1;
                    f(t, v, dist);
                }
            });

        auto find_diameterpoint = [&]() {
            std::vector<int> dist1(N), dist2(N);
            dfs(0, N, dist1);
            const auto max_idx =
                (int)(std::max_element(dist1.begin(), dist1.end()) - dist1.begin());
            dfs(max_idx, N, dist2);
            return std::make_pair(
                max_idx, (int)(std::max_element(dist2.begin(), dist2.end()) - dist2.begin()));
        };

        const auto [a, b] = find_diameterpoint();
        std::vector<bool> used(N);
        used[a] = used[b] = true;
        std::vector<int> ret(N);
        ret[0] = a, ret[1] = b;
        int last = b;
        for (const int i : rep(N - 2)) {
            std::vector<int> dist(N);
            dfs(last, N, dist);
            int max = 0, max_idx = 0;
            for (const int j : rep(N)) {
                if (not used[j]) {
                    if (setmax(max, dist[j])) {
                        max_idx = j;
                    }
                }
            }
            used[max_idx] = true;
            ret[i + 2] = max_idx;
            last = max_idx;
        }
        return ret;
    } else {
        // subtask 2
        std::vector<std::vector<int>> Tree(N);
        for (const int i : rep(1, N)) {
            Tree[i].push_back((i - 1) / 2);
            Tree[(i - 1) / 2].push_back(i);
        }

        auto find_centroid = [&]() {
            std::vector<int> subtree(N);
            int ret = 0;
            auto dfs = rec_lambda([&](auto &&f, const int v, const int p) -> void {
                subtree[v] = false;
                bool is_centroid = true;
                for (const int t : Tree[v]) {
                    if (t == p) {
                        continue;
                    }
                    f(t, v);
                    if (subtree[t] > N / 2) {
                        is_centroid = false;
                    }
                    subtree[v] += subtree[t];
                }
                if (N - subtree[v] > N / 2) {
                    is_centroid = false;
                }
                if (is_centroid) {
                    ret = v;
                }
            });
            dfs(0, N);
            return ret;
        };

        const int centroid = find_centroid();

        std::vector<int> answer(N);
        std::vector<std::vector<std::pair<int, int>>> memo(3);
        int count = 0;
        for (const int f : Tree[0]) {
            int idx = count++;
            auto dfs = rec_lambda([&](auto &&func, const int v, const int p, const int d) -> void {
                memo[idx].push_back({d, v});
                for (const int t : Tree[v]) {
                    if (t == p) {
                        continue;
                    }
                    func(t, v, d + 1);
                }
            });
            dfs(f, N, 1);
        }

        const int min_idx =
            (int)(std::min_element(memo.begin(), memo.end(),
                             [&](const auto a, const auto b) {
            return len(a) < len(b); }) -
            memo.begin());
        memo[min_idx].push_back({0, centroid});
        std::sort(memo[0].begin(), memo[0].end());
        std::sort(memo[1].begin(), memo[1].end());
        std::sort(memo[2].begin(), memo[2].end());

        auto max_p = [&](int bad) {
            int max = -1, max_idx = -1;
            for (const int i : rep(3)) {
                if (i == bad) {
                    continue;
                }
                if (memo[i].empty()) {
                    continue;
                }
                if (setmax(max, memo[i].back().first)) {
                    max_idx = i;
                }
            }
            return max_idx;
        };

        int f = max_p(3);
        answer[0] = memo[f].back().second;
        for ([[maybe_unused]] const int i : rep(N - 1)) {
            memo[f].pop_back();
            const int q = max_p(f);
            if (q != -1) {
                f = q;
                answer[i + 1] = memo[f].back().second;
            } else {
                assert(true);
            }
        }

        return answer;
    }
}

/*
static void wrongAnswer(std::string message) {
    printf("WA: %s\n", message.c_str());
    exit(0);
}

namespace tree_helper {

static int N;
static int logN;
static std::vector<std::vector<int>> parent;
static std::vector<int> depth;
static std::vector<int> subtree_size;

static void dfs(const std::vector<std::vector<int>> &adj_list, int current_node, int parent_node) {
    parent[0][current_node] = parent_node;
    subtree_size[current_node] = 1;
    for (int i = 0; i < static_cast<int>(adj_list[current_node].size()); ++i) {
        const int next_node = adj_list[current_node][i];
        if (next_node != parent_node) {
            depth[next_node] = depth[current_node] + 1;
            dfs(adj_list, next_node, current_node);
            subtree_size[current_node] += subtree_size[next_node];
        }
    }
}

static void initializeTree(const std::vector<std::vector<int>> &adj_list) {
    N = static_cast<int>(adj_list.size());

    depth = std::vector<int>(N, 0);
    subtree_size = std::vector<int>(N, 0);
    for (logN = 0; (1 << logN) < N; ++logN) {
    }
    parent = std::vector<std::vector<int>>(logN, std::vector<int>(N, 0));

    dfs(adj_list, 0, 0);
    for (int i = 1; i < logN; ++i) {
        for (int j = 0; j < N; ++j) {
            parent[i][j] = parent[i - 1][parent[i - 1][j]];
        }
    }
}

static int getLowestCommonAncestor(int X, int Y) {
    if (depth[X] < depth[Y]) {
        std::swap(X, Y);
    }
    for (int i = logN - 1; i >= 0; --i) {
        if (depth[parent[i][X]] >= depth[Y]) {
            X = parent[i][X];
        }
    }
    if (X == Y) {
        return X;
    }
    for (int i = logN - 1; i >= 0; --i) {
        if (parent[i][X] != parent[i][Y]) {
            X = parent[i][X];
            Y = parent[i][Y];
        }
    }
    return parent[0][X];
}

static int getDistance(int X, int Y) {
    return depth[X] + depth[Y] - 2 * depth[getLowestCommonAncestor(X, Y)];
}

static int attractionsBehind(int X, int Y) {
    if (X == Y) {
        return N;
    }
    for (int i = logN - 1; i >= 0; --i) {
        if (depth[parent[i][X]] > depth[Y]) {
            X = parent[i][X];
        }
    }
    if (Y == parent[0][X]) {
        return N - subtree_size[X];
    }
    return subtree_size[Y];
}

static void checkFunTour(const std::vector<int> &fun_tour) {
    if (static_cast<int>(fun_tour.size()) != N) {
        wrongAnswer("Invalid size");
    }

    std::vector<bool> visited_attractions(N, false);
    for (int i = 0; i < N; ++i) {
        if (fun_tour[i] < 0 || fun_tour[i] >= N) {
            wrongAnswer("Invalid index");
        }
        if (visited_attractions[fun_tour[i]]) {
            wrongAnswer("Repeated index");
        }
        visited_attractions[fun_tour[i]] = true;
    }

    int last_travel_time = getDistance(fun_tour[0], fun_tour[1]);
    for (int i = 2; i < N; ++i) {
        int travel_time = getDistance(fun_tour[i - 1], fun_tour[i]);
        if (travel_time > last_travel_time) {
            wrongAnswer("Tour is not fun");
        }
        last_travel_time = travel_time;
    }
}

} // namespace tree_helper

static int N, Q;

int hoursRequired(int X, int Y) {
    if (--Q < 0) {
        wrongAnswer("Too many queries");
    }
    if (X < 0 || X >= N || Y < 0 || Y >= N) {
        wrongAnswer("Invalid index");
    }
    return tree_helper::getDistance(X, Y);
}

int attractionsBehind(int X, int Y) {
    if (--Q < 0) {
        wrongAnswer("Too many queries");
    }
    if (X < 0 || X >= N || Y < 0 || Y >= N) {
        wrongAnswer("Invalid index");
    }
    return tree_helper::attractionsBehind(X, Y);
}

int main() {
    assert(2 == scanf("%d %d", &N, &Q));

    std::vector<std::vector<int>> adj_list(N);
    for (int i = 0; i < N - 1; ++i) {
        int A, B;
        assert(2 == scanf("%d %d", &A, &B));
        adj_list[A].push_back(B);
        adj_list[B].push_back(A);
    }
    tree_helper::initializeTree(adj_list);

    std::vector<int> fun_tour = createFunTour(N, Q);
    tree_helper::checkFunTour(fun_tour);

    for (int i = 0; i < N; ++i) {
        printf("%d%c", fun_tour[i], " \n"[i == N - 1]);
    }
    return 0;
}
*/

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34