Submission #394296

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
394296	2021-04-26T11:03:38 Z	KoD	Joker (BOI20_joker)	C++17	25 / 100	245 ms	9708 KB

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;
            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
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Incorrect	1 ms	204 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Incorrect	1 ms	204 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	245 ms	4828 KB	Output is correct
4	Correct	222 ms	9068 KB	Output is correct
5	Correct	232 ms	9664 KB	Output is correct
6	Correct	229 ms	8764 KB	Output is correct
7	Correct	238 ms	8772 KB	Output is correct
8	Correct	211 ms	8004 KB	Output is correct
9	Correct	204 ms	8244 KB	Output is correct
10	Correct	213 ms	9284 KB	Output is correct
11	Correct	229 ms	8680 KB	Output is correct
12	Correct	230 ms	9564 KB	Output is correct
13	Correct	219 ms	7992 KB	Output is correct
14	Correct	235 ms	8476 KB	Output is correct
15	Correct	242 ms	9264 KB	Output is correct
16	Correct	235 ms	9708 KB	Output is correct