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 <bits/stdc++.h>
using namespace std;
const int N = 200'000 + 10;
int n, m, q;
struct Edge {
int u, v;
friend istream& operator >> (istream& is, auto& rhs) {
return is >> rhs.u >> rhs.v;
}
} edge[N];
struct DSU {
int id[N], co[N], cnt;
vector<tuple<int, int, int, int, int, int>> undo;
bool mk[N];
int root(int u) { return id[u] < 0 ? u : root(id[u]); }
bool chk(int u) { return id[u] < 0 ? mk[u] : mk[u] ^ chk(id[u]); }
inline int color(int u) { return chk(u); }
inline void add(int u, int v) {
int oU = u, oV = v;
u = root(u); v = root(v);
if (u == v) {
undo.emplace_back(0, 0, 0, 0, 0, cnt);
cnt += color(oU) == color(oV);
return;
}
if (id[u] > id[v]) swap(u, v);
undo.emplace_back(u, id[u], v, id[v], mk[v], cnt);
if (color(oU) == color(oV)) mk[v] ^= 1;
id[u] += id[v];
id[v] = u;
}
inline void rollBack() {
auto [u, idU, v, idV, mkV, pCnt] = undo.back(); undo.pop_back();
id[u] = idU;
id[v] = idV;
mk[v] = mkV;
cnt = pCnt;
}
} T;
int f[N];
void dnc(int l, int r, int lt, int rt) {
if (l > r) return;
int mid = l + r >> 1;
auto& ret = f[mid];
for (int i = l; i < mid; ++i) T.add(edge[i].u, edge[i].v);
for (int i = rt; i >= max(mid + 1, lt); --i) T.add(edge[i].u, edge[i].v);
for (int i = max(mid + 1, lt); i <= rt; ++i) {
const auto& [u, v] = edge[i];
if (T.cnt) ret = i - 1;
T.rollBack();
} if (T.cnt) ret = rt;
int nxtr = (!ret ? max(mid, lt) : ret),
nxtl = (!ret ? mid : ret);
T.add(edge[mid].u, edge[mid].v);
dnc(mid + 1, r, nxtr, rt);
for (int i = l; i <= mid; ++i) T.rollBack();
for (int i = rt; i > nxtl; --i) T.add(edge[i].u, edge[i].v);
dnc(l, mid - 1, lt, nxtl);
for (int i = rt; i > nxtl; --i) T.rollBack();
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> q;
for (int i = 1; i <= m; ++i) cin >> edge[i];
memset(T.id, -1, sizeof T.id);
T.cnt = 0;
dnc(1, m, 1, m);
while (q--) {
int l, r; cin >> l >> r;
cout << (r <= f[l] ? "YES" : "NO") << "\n";
}
}
Compilation message (stderr)
Joker.cpp:9:45: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
9 | friend istream& operator >> (istream& is, auto& rhs) {
| ^~~~
Joker.cpp: In function 'void dnc(int, int, int, int)':
Joker.cpp:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
52 | int mid = l + r >> 1;
| ~~^~~
Joker.cpp:59:17: warning: unused structured binding declaration [-Wunused-variable]
59 | const auto& [u, v] = edge[i];
| ^~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |