Submission #1049642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049642		shiomusubi496	Joker (BOI20_joker)	C++17	14 / 100	2090 ms	20848 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 {
    vector<int> par;
    vector<pair<int, int>> history;

public:
    UndoableUF(int n) : par(n, -1) {}
    int find(int x) { return par[x] < 0 ? x : find(par[x]); }
    bool merge(int x, int y) {
        x = find(x), y = find(y);
        history.emplace_back(x, par[x]);
        history.emplace_back(y, par[y]);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    void undo() {
        auto [x, px] = history.back(); history.pop_back();
        auto [y, py] = history.back(); history.pop_back();
        par[x] = px;
        par[y] = py;
    }
    void snapshot() { history.clear(); }
    void rollback() {
        while (!history.empty()) undo();
    }
};

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;
    }
    rep (_, Q) {
        UndoableUF uf(2 * N);
        int l, r; cin >> l >> r;
        --l;
        rep (i, M) {
            if (l <= i && i < r) continue;
            uf.merge(A[i].first, A[i].second + N);
            uf.merge(A[i].first + N, A[i].second);
        }
        bool f = false;
        rep (i, N) {
            if (uf.same(i, i + N)) f = true;
        }
        if (f) puts("YES");
        else puts("NO");
    }
}

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