제출 #949067

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
949067		y_combinator	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	983 ms	414396 KiB

bitaro

#include <algorithm>
#include <array>
#include <cmath>
#include <ios>
#include <iostream>
#include <vector>

using Town = std::array<int, 2>;

auto solve() {

    auto m = 0;
    auto n = 0;
    auto q = 0;

    std::cin >> n >> m >> q;

    auto adj = std::vector<std::vector<int>>(n);

    for (auto i = 0; i < m; ++i) {
        auto e = 0;
        auto s = 0;
        std::cin >> s >> e;
        --s;
        --e;
        adj[e].push_back(s);
    }

    auto in_c = std::vector<bool>(n);
    auto mx_lens = std::vector<int>(n);
    auto lens = std::vector<std::vector<Town>>(n);
    auto root = static_cast<int>(std::sqrt(n)) + 1;

    while (root * root > n) {
        --root;
    }

    for (auto i = 0; i < n; ++i) {
        auto towns = std::vector<int>();
        for (auto x : adj[i]) {
            for (const auto& [town, len] : lens[x]) {
                if (mx_lens[town] == 0) {
                    towns.push_back(town);
                }
                mx_lens[town] = std::max(mx_lens[town], len + 1);
            }
        }
        if (static_cast<int>(std::size(towns)) >= root) {
            std::nth_element(
                std::begin(towns), std::begin(towns) + root - 1, std::end(towns),
                [&](int town_1, int town_2) {
                    return mx_lens[town_1] > mx_lens[town_2];
                }
            );
            for (auto j = 0; j < root; ++j) {
                lens[i].push_back(Town({towns[j], mx_lens[towns[j]]}));
            }
        } else {
            for (auto x : towns) {
                lens[i].push_back(Town({x, mx_lens[x]}));
            }
            lens[i].push_back(Town({i, 0}));
        }
        for (auto x : towns) {
            mx_lens[x] = 0;
        }
    }

    for (auto i = 0; i < q; ++i) {
        auto t = 0;
        auto y = 0;
        std::cin >> t >> y;
        --t;
        auto c = std::vector<int>(y);
        for (auto& x : c) {
            std::cin >> x;
            --x;
            in_c[x] = true;
        }
        auto mx_canals = -1;
        if (y < root) {
            for (const auto& [town, len] : lens[t]) {
                if (!in_c[town]) {
                    mx_canals = std::max(mx_canals, len);
                }
            }
        } else {
            auto dp = std::vector<int>(t + 1, -(n + 1));
            dp[t] = 0;
            for (auto j = t; j >= 0; --j) {
                for (auto x : adj[j]) {
                    dp[x] = std::max(dp[x], dp[j] + 1);
                }
                if (!in_c[j]) {
                    mx_canals = std::max(mx_canals, dp[j]);
                }
            }
        }
        std::cout << mx_canals << '\n';
        for (auto x : c) {
            in_c[x] = false;
        }
    }

}

auto main() -> int {

    std::cin.tie(nullptr);

    std::ios_base::sync_with_stdio(false);

    solve();

    return 0;

}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86