oj.uz

Submission #767507

# Submission time Handle Problem Language Result Execution time Memory
767507 2023-06-26T19:48:07 Z jakobrs Joker (BOI20_joker) C++17
71 / 100
 2000 ms 10368 KB 
#include <algorithm>
#include <iostream>
#include <vector>

using i64 = int32_t;

struct Operation {
    i64 l1, parent_l1, r1, parent_r1;
    bool is_bipartite;
};

constexpr i64 root(i64 n) {
    i64 i = 0;
    for (; i * i <= n; i++)
        ;
    return i - 1;
}

class UnionFind {
    std::vector<i64> parent;
    std::vector<bool> edge_parity;

    std::vector<Operation> operations;

   public:
    bool is_bipartite = true;

    UnionFind(size_t sz)
        : parent(sz, -1), edge_parity(sz, false), operations() {}

    void clear() {
        std::fill(parent.begin(), parent.end(), -1);
        std::fill(edge_parity.begin(), edge_parity.end(), false);
        operations.clear();
        is_bipartite = true;
    }

    template <bool PATH_COMPRESSION>
    i64 find(i64 idx) {
        if (parent[idx] < 0)
            return idx;
        else if constexpr (PATH_COMPRESSION) {
            i64 root = find<PATH_COMPRESSION>(parent[idx]);
            edge_parity[idx] = edge_parity[idx] ^ edge_parity[parent[idx]];
            return parent[idx] = root;
        } else
            return find<PATH_COMPRESSION>(parent[idx]);
    }

    bool parity(i64 idx) {
        if (parent[idx] < 0)
            return false;
        else
            return parity(parent[idx]) ^ edge_parity[idx];
    }

    template <bool PATH_COMPRESSION>
    std::pair<i64, bool> both(i64 idx) {
        if constexpr (PATH_COMPRESSION) {
            return {find<true>(idx), parity(idx)};
        } else {
            // in this case there's an easy iterative version
            bool parity = false;

            while (parent[idx] >= 0) {
                parity = parity ^ edge_parity[idx];
                idx = parent[idx];
            }

            return {idx, parity};
        }
    }

    template <bool PATH_COMPRESSION>
    bool lag_fagforening(i64 l, i64 r) {
        auto [l1, lp] = both<PATH_COMPRESSION>(l);
        auto [r1, rp] = both<PATH_COMPRESSION>(r);

        operations.push_back({
            .l1 = l1,
            .parent_l1 = parent[l1],
            .r1 = r1,
            .parent_r1 = parent[r1],
            .is_bipartite = is_bipartite,
        });

        if (l1 == r1) {
            return !(is_bipartite &= lp != rp);
        } else {
            if (-parent[l1] < -parent[r1]) {
                std::swap(l1, r1);
                std::swap(lp, rp);
            }

            parent[l1] += parent[r1];
            parent[r1] = l1;

            edge_parity[r1] = 1 ^ lp ^ rp;

            return false;
        }
    }

    void tvungen_lønnsnemnd() {
        auto [l1, parent_l1, r1, parent_r1, bpt] = operations.back();
        operations.pop_back();

        parent[l1] = parent_l1;
        parent[r1] = parent_r1;

        edge_parity[l1] = edge_parity[r1] = false;

        is_bipartite = bpt;
    }
};

struct {
    template <typename T>
    operator T() const {
        T x;
        std::cin >> x;
        return x;
    }
} in;

#define entire(v) std::begin(v), std::end(v)

#pragma GCC diagnostic ignored "-Wreturn-type"

template <class T, class U>
struct SwapComparator {
    void operator()(std::pair<T, U> const &lhs, std::pair<T, U> const &rhs) {
        return std::tie(lhs.second, lhs.first) <
               std::tie(rhs.second, rhs.first);
    }
};

main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    i64 n, m, q;
    std::cin >> n >> m >> q;

    std::vector<std::pair<i64, i64>> edges(m);
    for (i64 i = 0; i < m; i++) {
        edges[i] = {(i64)in - 1, (i64)in - 1};
    }

    UnionFind dsu(n);

    static constexpr i64 root_m = 1024;

    struct Query {
        i64 l, r, i;
    };

    std::vector<Query> queries(q);
    for (i64 i = 0; i < q; i++) queries[i] = {(i64)in - 1, (i64)in, i};

    std::sort(entire(queries), [](auto &&lhs, auto &&rhs) {
        return std::pair<i64, i64>{lhs.l / root_m, -lhs.r} <
               std::pair<i64, i64>{rhs.l / root_m, -rhs.r};
    });

    std::vector<bool> answers(q);

    i64 l = 0;
    i64 r = 0;

    for (i64 start = 0; start < m; start += root_m) {
        l = r;
        while (r < q && queries[r].l < start + root_m) r++;

        if (l == r) continue;

        for (i64 y = 0; y < start; y++) {
            dsu.lag_fagforening<true>(edges[y].first, edges[y].second);
        }

        i64 w = m;
        for (i64 i = l; i < r; i++) {
            for (i64 o = queries[i].r; o < w; o++)
                dsu.lag_fagforening<true>(edges[o].first, edges[o].second);
            w = queries[i].r;

            for (i64 g = start; g < queries[i].l; g++)
                dsu.lag_fagforening<false>(edges[g].first, edges[g].second);

            answers[queries[i].i] = dsu.is_bipartite;

            for (i64 g = start; g < queries[i].l; g++) dsu.tvungen_lønnsnemnd();
        }

        dsu.clear();
    }

    for (auto x : answers) {
        std::cout << (x ? "NO\n" : "YES\n");
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 224 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 380 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 224 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 380 KB Output is correct
29 Correct 14 ms 340 KB Output is correct
30 Correct 19 ms 340 KB Output is correct
31 Correct 21 ms 404 KB Output is correct
32 Correct 18 ms 340 KB Output is correct
33 Correct 17 ms 428 KB Output is correct
34 Correct 16 ms 448 KB Output is correct
35 Correct 16 ms 452 KB Output is correct
36 Correct 16 ms 444 KB Output is correct
37 Correct 15 ms 452 KB Output is correct
38 Correct 15 ms 448 KB Output is correct
39 Correct 19 ms 436 KB Output is correct
40 Correct 21 ms 444 KB Output is correct
41 Correct 21 ms 440 KB Output is correct
42 Correct 16 ms 440 KB Output is correct
43 Correct 18 ms 440 KB Output is correct
44 Correct 17 ms 440 KB Output is correct
45 Correct 18 ms 340 KB Output is correct
46 Correct 18 ms 340 KB Output is correct
47 Correct 17 ms 340 KB Output is correct
48 Correct 17 ms 340 KB Output is correct
49 Correct 16 ms 340 KB Output is correct
50 Correct 15 ms 448 KB Output is correct
51 Correct 17 ms 340 KB Output is correct
52 Correct 16 ms 340 KB Output is correct
53 Correct 20 ms 340 KB Output is correct
54 Correct 16 ms 448 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 70 ms 9880 KB Output is correct
4 Correct 88 ms 10328 KB Output is correct
5 Correct 70 ms 10172 KB Output is correct
6 Correct 67 ms 9920 KB Output is correct
7 Correct 68 ms 9872 KB Output is correct
8 Correct 67 ms 9700 KB Output is correct
9 Correct 71 ms 9868 KB Output is correct
10 Correct 67 ms 10312 KB Output is correct
11 Correct 67 ms 9868 KB Output is correct
12 Correct 86 ms 10200 KB Output is correct
13 Correct 66 ms 9548 KB Output is correct
14 Correct 73 ms 9704 KB Output is correct
15 Correct 68 ms 10036 KB Output is correct
16 Correct 70 ms 10284 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 224 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 380 KB Output is correct
29 Correct 70 ms 9880 KB Output is correct
30 Correct 88 ms 10328 KB Output is correct
31 Correct 70 ms 10172 KB Output is correct
32 Correct 67 ms 9920 KB Output is correct
33 Correct 68 ms 9872 KB Output is correct
34 Correct 67 ms 9700 KB Output is correct
35 Correct 71 ms 9868 KB Output is correct
36 Correct 67 ms 10312 KB Output is correct
37 Correct 67 ms 9868 KB Output is correct
38 Correct 86 ms 10200 KB Output is correct
39 Correct 66 ms 9548 KB Output is correct
40 Correct 73 ms 9704 KB Output is correct
41 Correct 68 ms 10036 KB Output is correct
42 Correct 70 ms 10284 KB Output is correct
43 Correct 388 ms 9852 KB Output is correct
44 Correct 334 ms 10312 KB Output is correct
45 Correct 342 ms 10276 KB Output is correct
46 Correct 374 ms 9868 KB Output is correct
47 Correct 466 ms 9876 KB Output is correct
48 Correct 414 ms 9856 KB Output is correct
49 Correct 419 ms 10324 KB Output is correct
50 Correct 430 ms 9812 KB Output is correct
51 Correct 392 ms 10032 KB Output is correct
52 Correct 380 ms 10244 KB Output is correct
53 Correct 432 ms 9556 KB Output is correct
54 Correct 508 ms 9832 KB Output is correct
55 Correct 393 ms 10088 KB Output is correct
56 Correct 424 ms 10368 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 224 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 380 KB Output is correct
29 Correct 14 ms 340 KB Output is correct
30 Correct 19 ms 340 KB Output is correct
31 Correct 21 ms 404 KB Output is correct
32 Correct 18 ms 340 KB Output is correct
33 Correct 17 ms 428 KB Output is correct
34 Correct 16 ms 448 KB Output is correct
35 Correct 16 ms 452 KB Output is correct
36 Correct 16 ms 444 KB Output is correct
37 Correct 15 ms 452 KB Output is correct
38 Correct 15 ms 448 KB Output is correct
39 Correct 19 ms 436 KB Output is correct
40 Correct 21 ms 444 KB Output is correct
41 Correct 21 ms 440 KB Output is correct
42 Correct 16 ms 440 KB Output is correct
43 Correct 18 ms 440 KB Output is correct
44 Correct 17 ms 440 KB Output is correct
45 Correct 18 ms 340 KB Output is correct
46 Correct 18 ms 340 KB Output is correct
47 Correct 17 ms 340 KB Output is correct
48 Correct 17 ms 340 KB Output is correct
49 Correct 16 ms 340 KB Output is correct
50 Correct 15 ms 448 KB Output is correct
51 Correct 17 ms 340 KB Output is correct
52 Correct 16 ms 340 KB Output is correct
53 Correct 20 ms 340 KB Output is correct
54 Correct 16 ms 448 KB Output is correct
55 Correct 680 ms 7536 KB Output is correct
56 Correct 891 ms 7892 KB Output is correct
57 Correct 814 ms 7896 KB Output is correct
58 Correct 920 ms 7480 KB Output is correct
59 Correct 1118 ms 7492 KB Output is correct
60 Correct 1337 ms 7744 KB Output is correct
61 Correct 933 ms 7492 KB Output is correct
62 Correct 1026 ms 7876 KB Output is correct
63 Correct 770 ms 7236 KB Output is correct
64 Correct 1088 ms 7612 KB Output is correct
65 Correct 1096 ms 7804 KB Output is correct

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 224 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 380 KB Output is correct
29 Correct 14 ms 340 KB Output is correct
30 Correct 19 ms 340 KB Output is correct
31 Correct 21 ms 404 KB Output is correct
32 Correct 18 ms 340 KB Output is correct
33 Correct 17 ms 428 KB Output is correct
34 Correct 16 ms 448 KB Output is correct
35 Correct 16 ms 452 KB Output is correct
36 Correct 16 ms 444 KB Output is correct
37 Correct 15 ms 452 KB Output is correct
38 Correct 15 ms 448 KB Output is correct
39 Correct 19 ms 436 KB Output is correct
40 Correct 21 ms 444 KB Output is correct
41 Correct 21 ms 440 KB Output is correct
42 Correct 16 ms 440 KB Output is correct
43 Correct 18 ms 440 KB Output is correct
44 Correct 17 ms 440 KB Output is correct
45 Correct 18 ms 340 KB Output is correct
46 Correct 18 ms 340 KB Output is correct
47 Correct 17 ms 340 KB Output is correct
48 Correct 17 ms 340 KB Output is correct
49 Correct 16 ms 340 KB Output is correct
50 Correct 15 ms 448 KB Output is correct
51 Correct 17 ms 340 KB Output is correct
52 Correct 16 ms 340 KB Output is correct
53 Correct 20 ms 340 KB Output is correct
54 Correct 16 ms 448 KB Output is correct
55 Correct 70 ms 9880 KB Output is correct
56 Correct 88 ms 10328 KB Output is correct
57 Correct 70 ms 10172 KB Output is correct
58 Correct 67 ms 9920 KB Output is correct
59 Correct 68 ms 9872 KB Output is correct
60 Correct 67 ms 9700 KB Output is correct
61 Correct 71 ms 9868 KB Output is correct
62 Correct 67 ms 10312 KB Output is correct
63 Correct 67 ms 9868 KB Output is correct
64 Correct 86 ms 10200 KB Output is correct
65 Correct 66 ms 9548 KB Output is correct
66 Correct 73 ms 9704 KB Output is correct
67 Correct 68 ms 10036 KB Output is correct
68 Correct 70 ms 10284 KB Output is correct
69 Correct 388 ms 9852 KB Output is correct
70 Correct 334 ms 10312 KB Output is correct
71 Correct 342 ms 10276 KB Output is correct
72 Correct 374 ms 9868 KB Output is correct
73 Correct 466 ms 9876 KB Output is correct
74 Correct 414 ms 9856 KB Output is correct
75 Correct 419 ms 10324 KB Output is correct
76 Correct 430 ms 9812 KB Output is correct
77 Correct 392 ms 10032 KB Output is correct
78 Correct 380 ms 10244 KB Output is correct
79 Correct 432 ms 9556 KB Output is correct
80 Correct 508 ms 9832 KB Output is correct
81 Correct 393 ms 10088 KB Output is correct
82 Correct 424 ms 10368 KB Output is correct
83 Correct 680 ms 7536 KB Output is correct
84 Correct 891 ms 7892 KB Output is correct
85 Correct 814 ms 7896 KB Output is correct
86 Correct 920 ms 7480 KB Output is correct
87 Correct 1118 ms 7492 KB Output is correct
88 Correct 1337 ms 7744 KB Output is correct
89 Correct 933 ms 7492 KB Output is correct
90 Correct 1026 ms 7876 KB Output is correct
91 Correct 770 ms 7236 KB Output is correct
92 Correct 1088 ms 7612 KB Output is correct
93 Correct 1096 ms 7804 KB Output is correct
94 Execution timed out 2061 ms 9920 KB Time limit exceeded
95 Halted 0 ms 0 KB -