Submission #403679

#	Time	Username	Problem	Language	Result	Execution time	Memory
403679		KoD	Collapse (JOI18_collapse)	C++17	100 / 100	3572 ms	15836 KiB

collapse

#include <bits/stdc++.h>
#include "collapse.h"

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

class rep {
    struct Iter {
        usize itr;
        constexpr Iter(const usize pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { ++itr; }
        constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
        constexpr usize operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr rep(const usize first, const usize last) noexcept : first(first), last(std::max(first, last)) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

class RollbackUnionFind {
    std::vector<usize> data;
    std::stack<std::pair<usize, usize>> history;

  public:
    explicit RollbackUnionFind(const usize size = 0) : data(size, -1), history() {}

    usize size() const { return data.size(); }

    usize leader(usize u) const {
        assert(u < size());
        while (data[u] < size()) u = data[u];
        return u;
    }

    usize size(const usize u) const {
        assert(u < size());
        return -data[leader(u)];
    }

    std::pair<usize, bool> merge(usize u, usize v) {
        assert(u < size());
        assert(v < size());
        u = leader(u);
        v = leader(v);
        if (u == v) return std::make_pair(u, false);
        if (data[u] > data[v]) std::swap(u, v);
        history.emplace(u, data[u]);
        history.emplace(v, data[v]);
        data[u] += data[v];
        data[v] = u;
        return std::make_pair(u, true);
    }

    bool same(const usize u, const usize v) const {
        assert(u < size());
        assert(v < size());
        return leader(u) == leader(v);
    }

    void rollback(const usize steps) {
        assert(2 * steps <= history.size());
        for (usize i = 2 * steps; i > 0; --i) {
            const auto [k, x] = history.top();
            history.pop();
            data[k] = x;
        }
    }
};

template <class T> using Vec = std::vector<T>;

constexpr usize BSIZE = 400;

Vec<int> calc(const usize N, Vec<int> T, Vec<int> X, Vec<int> Y, Vec<int> W, Vec<int> P) {
    const auto C = T.size();
    const auto Q = W.size();
    Vec<std::pair<int, int>> edge;
    edge.reserve(C);
    for (const auto i : rep(0, C)) {
        if (X[i] > Y[i]) {
            std::swap(X[i], Y[i]);
        }
        edge.emplace_back(Y[i], X[i]);
    }
    std::sort(edge.begin(), edge.end());
    edge.erase(std::unique(edge.begin(), edge.end()), edge.end());
    Vec<usize> eid(C);
    for (const auto i : rep(0, C)) {
        eid[i] = std::lower_bound(edge.begin(), edge.end(), std::make_pair(Y[i], X[i])) - edge.begin();
    }
    const auto Blocks = (C + BSIZE - 1) / BSIZE;
    Vec<Vec<usize>> qid(Blocks);
    for (const auto i : rep(0, Q)) {
        qid[W[i] / BSIZE].push_back(i);
    }
    Vec<int> ret(Q);
    for (const auto block : rep(0, Blocks)) {
        const auto low = BSIZE * block;
        const auto high = std::min(C, low + BSIZE);
        auto& qs = qid[block];
        std::sort(qs.begin(), qs.end(), [&](const usize i, const usize j) { return P[i] < P[j]; });
        Vec<char> usage(edge.size()), changes(edge.size());
        for (const auto i : rep(0, low)) {
            usage[eid[i]] ^= 1;
        }
        for (const auto i : rep(low, high)) {
            changes[eid[i]] = true;
        }
        Vec<usize> naive;
        for (const auto i : rep(0, edge.size())) {
            if (changes[i]) {
                naive.push_back(i);
            }
        }
        RollbackUnionFind dsu(N);
        usize comps = N, seen = 0;
        for (const auto i : qs) {
            while (seen < edge.size() and edge[seen].first <= P[i]) {
                if (!changes[seen] and usage[seen]) {
                    comps -= dsu.merge(edge[seen].first, edge[seen].second).second;
                }
                seen += 1;
            }
            const auto memo = comps;
            for (const auto j : rep(low, W[i] + 1)) {
                usage[eid[j]] ^= 1;
            }
            for (const auto e : naive) {
                if (usage[e] and edge[e].first <= P[i]) {
                    comps -= dsu.merge(edge[e].first, edge[e].second).second;
                }
            }
            for (const auto j : rep(low, W[i] + 1)) {
                usage[eid[j]] ^= 1;
            }
            ret[i] = comps;
            dsu.rollback(memo - comps);
            comps = memo;
        }
    }
    return ret;
}

Vec<int> simulateCollapse(int N, Vec<int> T, Vec<int> X, Vec<int> Y, Vec<int> W, Vec<int> P) {
    const auto C = T.size();
    const auto Q = W.size();
    auto ret = calc(N, T, X, Y, W, P);
    for (const auto i : rep(0, C)) {
        X[i] = N - X[i] - 1;
        Y[i] = N - Y[i] - 1;
    }
    for (const auto i : rep(0, Q)) {
        P[i] = N - P[i] - 2;
    }
    const auto tmp = calc(N, T, X, Y, W, P);
    for (const auto i : rep(0, Q)) {
        ret[i] += tmp[i];
        ret[i] -= N;
    }
    return ret;
}

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35