Submission #1224550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224550		totoro	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	2098 ms	220660 KiB

bitaro

#include <iostream>
#include <queue>
#include <set>
#include <utility>
#include <vector>

const size_t SQRT = 200;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, q;
    std::cin >> n >> m >> q;
    std::vector<std::vector<int>> upadj(n), downadj(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        --u, --v;
        upadj[v].push_back(u);
        downadj[u].push_back(v);
    }
    std::vector<std::vector<std::pair<int, int>>> furthest_ancestors(n);  // (dist, index)

    std::vector<int> dfsupseen(n);
    auto dfsup = [&](int node, auto dfs) -> void {
        if (!furthest_ancestors[node].empty()) return;

        std::priority_queue<std::pair<int, int>> q;
        q.emplace(0, node);
        for (int to : upadj[node]) {
            dfs(to, dfs);
            for (auto [dist, far] : furthest_ancestors[to]) {
                q.emplace(dist + 1, far);
            }
        }
        while (!q.empty()) {
            auto el = q.top();
            q.pop();
            if (furthest_ancestors[node].size() >= SQRT + 1) break;
            if (dfsupseen[el.second]) continue;
            dfsupseen[el.second] = true;
            furthest_ancestors[node].push_back(el);
        }
        for (auto [dist, far] : furthest_ancestors[node]) {
            dfsupseen[far] = false;
        }
    };
    for (int i = 0; i < n; ++i) dfsup(i, dfsup);

    std::vector<int> is_removed(n);
    while (q--) {
        int partytown, removed;
        std::cin >> partytown >> removed;
        --partytown;
        std::vector<int> which_removed(removed);
        for (int& i : which_removed) std::cin >> i, --i;
        for (int i : which_removed) is_removed[i] = true;
        if (removed > SQRT) {
            // solve in one big dfs
            std::vector<int> distance(n, -1);
            distance[partytown] = 0;
            auto dfsdown = [&](int node, auto dfs) -> void {
                if (distance[node] != -1) return;
                int max = -1e9;
                for (int to : downadj[node]) {
                    dfs(to, dfs);
                    max = std::max(max, distance[to]);
                }
                distance[node] = max + 1;
            };
            int max = -1;
            for (int i = 0; i < n; ++i) {
                if (is_removed[i]) continue;
                dfsdown(i, dfsdown);
                max = std::max(max, distance[i]);
            }
            std::cout << max << '\n';
        } else {
            // use preprocess
            int ans = -1;
            for (auto [dist, node] : furthest_ancestors[partytown]) {
                if (is_removed[node]) continue;
                ans = dist;
                break;
            }
            std::cout << ans << '\n';
        }
        for (int i : which_removed) is_removed[i] = false;
    }
}

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