제출 #394301

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
394301		KoD	Joker (BOI20_joker)	C++17	39 / 100	276 ms	9136 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;
    }
    if (M <= 2000 and Q <= 2000) {
        for (int i = 0; i < Q; ++i) {
            DSU dsu(2 * N);
            for (int j = 0; j < L[i]; ++j) {
                dsu.merge(A[j], B[j] + N);
                dsu.merge(A[j] + N, B[j]);
            }
            for (int j = M - 1; j > R[i]; --j) {
                dsu.merge(A[j], B[j] + N);
                dsu.merge(A[j] + N, B[j]);
            } 
            bool ok = false;
            for (int i = 0; i < N; ++i) {
                if (dsu.find(i) == dsu.find(i + N)) {
                    ok = true;
                    break;
                }
            }
            if (ok) {
                std::cout << "YES\n";
            }
            else {
                std::cout << "NO\n";
            }
        }
        return 0;
    }
    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;
            break;
        }
    }
    for (int i = 0; i < Q; ++i) {
        if (R[i] < border) {
            std::cout << "YES\n";
        }
        else {
            std::cout << "NO\n";
        }
    }
    return 0;
}

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