#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);
operations.clear();
is_bipartite = true;
}
template <bool PATH_COMPRESSION>
i64 find(i64 idx) const {
if (parent[idx] < 0)
return idx;
else if (PATH_COMPRESSION) {
int p = find(parent[idx]);
edge_parity[idx] = edge_parity[idx] ^ edge_parity[parent[idx]];
return parent[idx] = p;
}
return find(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");
}
}
Compilation message
Joker.cpp: In member function 'i64 UnionFind::find(i64) const':
Joker.cpp:44:37: error: no matching function for call to 'UnionFind::find(const value_type&) const'
44 | int p = find(parent[idx]);
| ^
Joker.cpp:40:9: note: candidate: 'template<bool PATH_COMPRESSION> i64 UnionFind::find(i64) const'
40 | i64 find(i64 idx) const {
| ^~~~
Joker.cpp:40:9: note: template argument deduction/substitution failed:
Joker.cpp:44:37: note: couldn't deduce template parameter 'PATH_COMPRESSION'
44 | int p = find(parent[idx]);
| ^
Joker.cpp:48:36: error: no matching function for call to 'UnionFind::find(const value_type&) const'
48 | return find(parent[idx]);
| ^
Joker.cpp:40:9: note: candidate: 'template<bool PATH_COMPRESSION> i64 UnionFind::find(i64) const'
40 | i64 find(i64 idx) const {
| ^~~~
Joker.cpp:40:9: note: template argument deduction/substitution failed:
Joker.cpp:48:36: note: couldn't deduce template parameter 'PATH_COMPRESSION'
48 | return find(parent[idx]);
| ^
Joker.cpp: In instantiation of 'i64 UnionFind::find(i64) const [with bool PATH_COMPRESSION = true; i64 = int]':
Joker.cpp:59:72: required from 'std::pair<int, bool> UnionFind::both(i64) [with bool PATH_COMPRESSION = true; i64 = int]'
Joker.cpp:63:47: required from 'bool UnionFind::lag_fagforening(i64, i64) [with bool PATH_COMPRESSION = true; i64 = int]'
Joker.cpp:158:70: required from here
Joker.cpp:45:30: error: lvalue required as left operand of assignment
45 | edge_parity[idx] = edge_parity[idx] ^ edge_parity[parent[idx]];
Joker.cpp:46:32: error: assignment of read-only location '((const UnionFind*)this)->UnionFind::parent.std::vector<int>::operator[](((std::vector<int>::size_type)idx))'
46 | return parent[idx] = p;
Joker.cpp: In instantiation of 'i64 UnionFind::find(i64) const [with bool PATH_COMPRESSION = false; i64 = int]':
Joker.cpp:59:72: required from 'std::pair<int, bool> UnionFind::both(i64) [with bool PATH_COMPRESSION = false; i64 = int]'
Joker.cpp:63:47: required from 'bool UnionFind::lag_fagforening(i64, i64) [with bool PATH_COMPRESSION = false; i64 = int]'
Joker.cpp:168:75: required from here
Joker.cpp:45:30: error: lvalue required as left operand of assignment
45 | edge_parity[idx] = edge_parity[idx] ^ edge_parity[parent[idx]];
Joker.cpp:46:32: error: assignment of read-only location '((const UnionFind*)this)->UnionFind::parent.std::vector<int>::operator[](((std::vector<int>::size_type)idx))'
46 | return parent[idx] = p;
