oj.uz

Submission #765493

# Submission time Handle Problem Language Result Execution time Memory
765493 2023-06-24T15:12:10 Z jakobrs Joker (BOI20_joker) C++17
25 / 100
 1361 ms 10280 KB 
#include <algorithm>
#include <iostream>
#include <vector>

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

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(entire(parent), -1);
        std::fill(entire(edge_parity), false);
        operations.clear();
        is_bipartite = true;
    }

    template <bool PATH_COMPRESSION>
    i64 find(i64 idx) {
        if (parent[idx] < 0)
            return idx;
        else if (PATH_COMPRESSION) {
            int p = find<PATH_COMPRESSION>(parent[idx]);
            edge_parity[idx] = edge_parity[idx] ^ edge_parity[parent[idx]];
            return parent[idx] = p;
        }
            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) { return {find<PATH_COMPRESSION>(idx), parity(idx)}; }

    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;

        is_bipartite = bpt;
    }
};

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

#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 = 450;  // root(200'000);

    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++;

        for (i64 x = 0; x < start; x++) {
            dsu.lag_fagforening<true>(edges[x].first, edges[x].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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 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 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 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 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 938 ms 9816 KB Output is correct
4 Correct 1004 ms 10280 KB Output is correct
5 Correct 999 ms 10184 KB Output is correct
6 Correct 1100 ms 9920 KB Output is correct
7 Correct 1115 ms 9864 KB Output is correct
8 Correct 1108 ms 9660 KB Output is correct
9 Correct 1296 ms 9920 KB Output is correct
10 Correct 1312 ms 10276 KB Output is correct
11 Correct 1261 ms 9816 KB Output is correct
12 Correct 1156 ms 10204 KB Output is correct
13 Correct 962 ms 9544 KB Output is correct
14 Correct 1098 ms 9660 KB Output is correct
15 Correct 1361 ms 10076 KB Output is correct
16 Correct 1342 ms 10272 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 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 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 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 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 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 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -