제출 #394293

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
394293		KoD	Joker (BOI20_joker)	C++17	0 / 100	239 ms	8792 KiB

Joker

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

struct DSU {
    Vec<int> par;
    DSU(const int n): par(n, -1) { }
    int find(const int u) {
        return par[u] < 0 ? u : par[u] = find(par[u]);
    }
    void merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (par[x] > par[y]) {
            std::swap(x, y);
        }
        par[x] += par[y];
        par[y] = x;
    }
};

int main() {
    int N, M, Q;
    std::cin >> N >> M >> Q;
    Vec<int> A(M), B(M);
    for (int i = 0; i < M; ++i) {
        std::cin >> A[i] >> B[i];
        A[i] -= 1;
        B[i] -= 1;
    }
    Vec<int> L(Q), R(Q);
    for (int i = 0; i < Q; ++i) {
        std::cin >> L[i] >> R[i];
        L[i] -= 1;
        R[i] -= 1;
    }
    DSU dsu(2 * N);
    int border = -1;
    for (int i = M - 1; i >= 0; --i) {
        dsu.merge(A[i], B[i] + N);
        dsu.merge(A[i] + N, B[i]);
        if (dsu.find(A[i]) == dsu.find(A[i] + N) or dsu.find(B[i]) == dsu.find(B[i] + N)) {
            border = i;
        }
    }
    for (int i = 0; i < Q; ++i) {
        if (R[i] < border) {
            std::cout << "YES\n";
        }
        else {
            std::cout << "NO\n";
        }
    }
    return 0;
}

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