제출 #1279956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279956		MisterReaper	Joker (BOI20_joker)	C++20	100 / 100	352 ms	22088 KiB

Joker

// File joker.cpp created on 16.10.2025 at 11:22:41
// 11:39-13:13 break
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int max_N = int(2E5) + 5;

struct DSU {
    std::vector<int> f, siz;
    std::vector<std::pair<int&, int>> stk;
    void init(int n) {
        f.assign(n, 0);
        siz.assign(n, 1);
        std::iota(f.begin(), f.end(), 0);
    }
    int get(int x) {
        while (x != f[x]) {
            x = f[x];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = get(a), b = get(b);
        if (a == b) {
            return false;
        } else if (siz[a] > siz[b]) {
            std::swap(a, b);
        }
        stk.emplace_back(f[a], a);
        stk.emplace_back(siz[b], siz[b]);
        f[a] = b;
        siz[b] += siz[a];
        return true;
    }
    bool same(int a, int b) {
        return get(a) == get(b);
    }
    int size(int x) {
        return siz[get(x)];
    }
    int snap() {
        return int(stk.size());
    }
    void roll(int tim) {
        while (int(stk.size()) > tim) {
            stk.back().first = stk.back().second;
            stk.pop_back();
        }
    }
} dsu;

bool bip = true;
void unite(int a, int b) {
    dsu.unite(2 * a, 2 * b + 1);
    dsu.unite(2 * a + 1, 2 * b);
    if (dsu.same(2 * a, 2 * a + 1)) {
        bip = false;
    }
    if (dsu.same(2 * b, 2 * b + 1)) {
        bip = false;
    }
}

int N, M, Q;
int E[max_N][2];

int lst[max_N];

void dnq(int l, int r, int lstl, int lstr) {
    if (l > r) {
        return;
    }

    debug(l, r, lstl, lstr, bip);

    int histim = dsu.snap();
    bool hisbip = bip;
    int mid = (l + r) >> 1;
    for (int i = l; i < mid; ++i) {
        unite(E[i][0], E[i][1]);
    }
    int p = lstr;
    while (bip && p > mid) {
        --p;
        unite(E[p][0], E[p][1]);
    }
    debug(mid, p);
    lst[mid] = p;
    bip = hisbip;
    dsu.roll(histim);

    for (int i = lstr - 1; i >= p; --i) {
        unite(E[i][0], E[i][1]);
    }
    dnq(l, mid - 1, lstl, p);
    bip = hisbip;
    dsu.roll(histim);

    for (int i = l; i <= mid; ++i) {
        unite(E[i][0], E[i][1]);
    }
    dnq(mid + 1, r, std::max(mid + 1, p), lstr);
    bip = hisbip;
    dsu.roll(histim);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> N >> M >> Q;

    for (int i = 0; i < M; ++i) {
        std::cin >> E[i][0] >> E[i][1];
        --E[i][0], --E[i][1];
    }

    dsu.init(2 * N);

    dnq(0, M - 1, 0, M);

    #ifdef LOCAL
        for (int i = 0; i < M; ++i) {
            bip = true;
            dsu.roll(0);
            for (int j = 0; j < i; ++j) {
                unite(E[j][0], E[j][1]);
            }
            int p = M;
            while (bip && p > i) {
                --p;
                unite(E[p][0], E[p][1]);
            }
            debug(i, lst[i], p);
            assert(lst[i] == p);
        }
    #endif

    while (Q--) {
        int L, R;
        std::cin >> L >> R;
        --L, --R;
        std::cout << (lst[L] <= R ? "NO" : "YES") << '\n';
    }

    return 0;
}

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