| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 767471 | jakobrs | Joker (BOI20_joker) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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() {}
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);
template <>
std::pair<i64, bool> both<true>(i64 idx) {
return {find<true>(idx), parity(idx)};
}
template <>
std::pair<i64, bool> both<false>(i64 idx) {
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++;
i64 w = m;
for (i64 i = l; i < r; i++) {
for (i64 o = queries[i].r; o < w; o++)
dsu.lag_fagforening<false>(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();
}
for (i64 x = w; x < m; x++) dsu.tvungen_lønnsnemnd();
for (i64 y = start; y < start + root_m && y < m; y++)
dsu.lag_fagforening<true>(edges[y].first, edges[y].second);
}
for (auto x : answers) {
std::cout << (x ? "NO\n" : "YES\n");
}
}