Submission #394735

#	Time	Username	Problem	Language	Result	Execution time	Memory
394735		KoD	Joker (BOI20_joker)	C++17	100 / 100	1064 ms	27380 KiB

Joker

#include <bits/stdc++.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; }
};

template <class F> struct RecLambda : private F {
    template <class G>
    explicit constexpr RecLambda(G&& g) : F(std::forward<G>(g)) {}
    template <class... Args>
    constexpr decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

template <class G> explicit RecLambda(G&&) -> RecLambda<std::decay_t<G>>;

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

  public:
    explicit UnionFindRollback(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>;

void BOI20_joker_main() {
    usize N, M, Q;
    std::cin >> N >> M >> Q;
    Vec<usize> A(M), B(M);
    for (const auto i : rep(0, M)) {
        std::cin >> A[i] >> B[i];
        A[i] -= 1;
        B[i] -= 1;
    }
    Vec<usize> last(M);
    UnionFindRollback dsu(2 * N);
    Vec<bool> bip;
    bip.push_back(true);
    const auto add_edge = [&](const usize e) {
        if (dsu.merge(A[e], B[e] + N).second) {
            bip.push_back(bip.back() and !dsu.same(A[e], A[e] + N) and
                          !dsu.same(B[e], B[e] + N));
        }
        if (dsu.merge(A[e] + N, B[e]).second) {
            bip.push_back(bip.back() and !dsu.same(A[e], A[e] + N) and
                          !dsu.same(B[e], B[e] + N));
        }
    };
    const auto back_until = [&](const usize time) {
        dsu.rollback(bip.size() - time);
        bip.resize(time);
    };
    RecLambda([&](auto&& dfs, const usize il, const usize ir, const usize jl,
                  const usize jr) -> void {
        if (!bip.back()) {
            std::fill(last.begin() + il, last.begin() + ir + 1, jr);
            return;
        }
        const auto im = (il + ir) / 2;
        {
            const auto time = bip.size();
            for (const auto i : rep(il, im)) {
                add_edge(i);
            }
            last[im] = jr;
            while (bip.back() and last[im] > im) {
                last[im] -= 1;
                add_edge(last[im]);
            }
            back_until(time);
        }
        if (il < im) {
            const auto time = bip.size();
            for (const auto i : rep(last[im], jr)) {
                add_edge(i);
            }
            dfs(il, im - 1, jl, last[im]);
            back_until(time);
        }
        if (im < ir) {
            const auto time = bip.size();
            for (const auto i : rep(il, im + 1)) {
                add_edge(i);
            }
            dfs(im + 1, ir, last[im], jr);
            back_until(time);
        }
    })(0, M - 1, 0, M);
    while (Q--) {
        usize l, r;
        std::cin >> l >> r;
        l -= 1;
        std::cout << (r <= last[l] ? "YES" : "NO") << '\n';
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    BOI20_joker_main();
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 25 / 25
• Subtask 4: 10 / 10
• Subtask 5: 22 / 22
• Subtask 6: 29 / 29