제출 #1279928

#제출 시각아이디문제언어결과실행 시간메모리
1279928MisterReaperJoker (BOI20_joker)C++20
0 / 100
115 ms11796 KiB
// File joker.cpp created on 16.10.2025 at 11:22:41
#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;
    }

    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]);
    }
    lst[mid] = p;
    bip = hisbip;
    dsu.roll(histim);

    for (int i = lstr; 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);

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

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...