Submission #1049735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049735		shiomusubi496	Joker (BOI20_joker)	C++17	100 / 100	1923 ms	21184 KiB

Joker

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)

using namespace std;

using ll = long long;

template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }

class UndoableUF {
    bool flag = true;
    vector<int> par, wei;
    vector<tuple<int, int, int, bool>> history;

public:
    UndoableUF(int n_) : par(n_, -1), wei(n_, 0) {}
    int find(int x) { return par[x] < 0 ? x : find(par[x]); }
    bool same(int x, int y) { return find(x) == find(y); }
    int weight(int x) { return par[x] < 0 ? wei[x] : wei[x] ^ weight(par[x]); }
    pair<int, int> weifin(int x) {
        if (par[x] < 0) return {x, 0};
        auto [r, w] = weifin(par[x]);
        return {r, w ^ wei[x]};
    }
    bool merge(int x, int y) {
        auto [xr, xw] = weifin(x);
        auto [yr, yw] = weifin(y);
        x = xr, y = yr;
        int w = xw ^ yw;
        if (x == y) {
            history.emplace_back(-1, -1, -1, flag);
            history.emplace_back(-1, -1, -1, flag);
            if (w == 0) flag = false;
            return false;
        }
        history.emplace_back(x, par[x], wei[x], flag);
        history.emplace_back(y, par[y], wei[y], flag);
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        wei[y] = 1 ^ w;
        return true;
    }
    int find2(int x) {
        if (par[x] < 0) return x;
        int r = find2(par[x]);
        // history.emplace_back(x, par[x], wei[x], flag);
        wei[x] ^= wei[par[x]];
        return par[x] = r;
    }
    bool same2(int x, int y) { return find2(x) == find2(y); }
    bool merge2(int x, int y) {
        int xr = find2(x), yr = find2(y);
        int w = wei[x] ^ wei[y];
        x = xr, y = yr;
        // history.emplace_back(x, par[x], wei[x], flag);
        // history.emplace_back(y, par[y], wei[y], flag);
        if (x == y) {
            if (w == 0) flag = false;
            return false;
        }
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        wei[y] = 1 ^ w;
        return true;
    }
    void undo() {
        auto [x, px, wx, _] = history.back(); history.pop_back();
        auto [y, py, wy, f] = history.back(); history.pop_back();
        if (x == -1) {
            flag = f;
        }
        else {
            par[x] = px;
            par[y] = py;
            wei[x] = wx;
            wei[y] = wy;
        }
    }
    void snapshot() { history.clear(); }
    void rollback() {
        while (!history.empty()) {
            auto [x, px, wx, f] = history.back(); history.pop_back();
            if (x == -1) flag = f;
            else {
                par[x] = px;
                wei[x] = wx;
            }
        }
    }
    bool is_bip() { return flag; }
};

int main() {
    int N, M, Q; cin >> N >> M >> Q;
    vector<pair<int, int>> A(M);
    rep (i, M) {
        cin >> A[i].first >> A[i].second;
        --A[i].first, --A[i].second;
    }
    vector<array<int, 3>> B(Q);
    rep (i, Q) {
        cin >> B[i][0] >> B[i][1];
        --B[i][0];
        B[i][2] = i;
    }
    static constexpr int block = 500;
    sort(all(B), [&](auto a, auto b) {
        if (a[0] / block != b[0] / block) return a[0] < b[0];
        return a[1] > b[1];
    });
    vector<bool> ans(Q);
    int curl = block, curr = M;
    UndoableUF uf(N);
    bool f = false;
    for (auto [l, r, k] : B) {
        if (f) {
            ans[k] = false;
            continue;
        }
        while (curl <= l) {
            uf.rollback();
            rep2 (i, curl - block, curl) {
                if (i >= M) break;
                uf.merge2(A[i].first, A[i].second);
            }
            uf.snapshot();
            if (!uf.is_bip()) {
                ans[k] = false;
                f = true;
                break;
            }
            curl += block;
            curr = M;
        }
        if (f) continue;
        assert(curr >= r);
        rrep2 (i, r, curr) {
            uf.merge(A[i].first, A[i].second);
        }
        curr = r;
        rep2 (i, curl - block, l) {
            uf.merge(A[i].first, A[i].second);
        }
        ans[k] = uf.is_bip();
        rep2 (i, curl - block, l) uf.undo();
    }
    rep (i, Q) puts(ans[i] ? "NO" : "YES");
}

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