Submission #1226475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226475		totoro	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	1456 ms	354472 KiB

bitaro

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

const size_t SQRT = 500;

std::vector<std::pair<int, int>> merge_sqrt(std::vector<std::pair<int, int>>& a, std::vector<std::pair<int, int>>& b, std::vector<int>& seenby) {
    int key = std::random_device()();

    assert(a.size() <= SQRT + 1);
    assert(b.size() <= SQRT + 1);

    std::vector<std::pair<int, int>> res;
    res.reserve(SQRT + 1);
    int ap, bp;  // pointers to current elements to consider
    ap = bp = 0;
    while (res.size() < SQRT + 1) {
        if (ap < a.size() && seenby[a[ap].second] == key) {
            ++ap;
        } else if (bp < b.size() && seenby[b[bp].second] == key) {
            ++bp;
        } else if (ap == a.size()) {
            if (bp == b.size()) return res;
            seenby[b[bp].second] = key;
            res.push_back(b[bp++]);
        } else if (bp == b.size()) {
            seenby[a[ap].second] = key;
            res.push_back(a[ap++]);
        } else if (a[ap] > b[bp]) {
            seenby[a[ap].second] = key;
            res.push_back(a[ap++]);
        } else {
            seenby[b[bp].second] = key;
            res.push_back(b[bp++]);
        }
    }
    return res;
}

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> mergerseen(n);
    auto precalc = [&](int node) -> void {
        furthest_ancestors[node] = {{-1, node}};
        for (int to : upadj[node]) {
            furthest_ancestors[node] = merge_sqrt(furthest_ancestors[node], furthest_ancestors[to], mergerseen);
        }
        for (auto& [dist, index] : furthest_ancestors[node]) {
            ++dist;
        }
    };
    for (int i = 0; i < n; ++i) precalc(i);

    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;
            int max = -1;
            for (int i = partytown; i >= 0; --i) {
                int maxx = -1e9;
                for (int to : downadj[i]) {
                    maxx = std::max(maxx, distance[to]);
                }
                if (i != partytown) {
                    distance[i] = maxx + 1;
                }
                if (!is_removed[i]) {
                    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: 0 / 7
• Subtask 3: 0 / 86