#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
using namespace std;
using ll = long long;
template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }
class UndoableUF {
bool flag = true;
vector<int> par, wei;
vector<tuple<int, int, int, bool>> history;
public:
UndoableUF(int n_) : par(n_, -1), wei(n_, 0) {}
int find(int x) {
if (par[x] < 0) return x;
int r = find(par[x]);
wei[x] ^= wei[par[x]];
return r;
}
bool same(int x, int y) { return find(x) == find(y); }
bool merge(int x, int y) {
int xr = find(x), yr = find(y);
int w = wei[x] ^ wei[y];
x = xr, y = yr;
history.emplace_back(x, par[x], wei[x], flag);
history.emplace_back(y, par[y], wei[y], flag);
if (x == y) {
if (w == 0) flag = false;
return false;
}
if (par[x] > par[y]) swap(x, y);
par[x] += par[y];
par[y] = x;
wei[y] = 1 ^ w;
return true;
}
int find2(int x) {
if (par[x] < 0) return x;
// history.emplace_back(x, par[x], wei[x], flag);
return par[x] = find2(par[x]);
}
bool same2(int x, int y) { return find2(x) == find2(y); }
bool merge2(int x, int y) {
int xr = find2(x), yr = find2(y);
int w = wei[x] ^ wei[y];
x = xr, y = yr;
// history.emplace_back(x, par[x], wei[x], flag);
// history.emplace_back(y, par[y], wei[y], flag);
if (x == y) {
if (w == 0) flag = false;
return false;
}
if (par[x] > par[y]) swap(x, y);
par[x] += par[y];
par[y] = x;
wei[y] = 1 ^ w;
return true;
}
void undo() {
auto [x, px, wx, _] = history.back(); history.pop_back();
auto [y, py, wy, f] = history.back(); history.pop_back();
par[x] = px;
par[y] = py;
wei[x] = wx;
wei[y] = wy;
flag = f;
}
void snapshot() { history.clear(); }
void rollback() {
while (!history.empty()) {
auto [x, px, wx, f] = history.back(); history.pop_back();
par[x] = px;
wei[x] = wx;
flag = f;
}
}
bool is_bip() { return flag; }
};
int main() {
int N, M, Q; cin >> N >> M >> Q;
vector<pair<int, int>> A(M);
rep (i, M) {
cin >> A[i].first >> A[i].second;
--A[i].first, --A[i].second;
}
vector<array<int, 3>> B(Q);
rep (i, Q) {
cin >> B[i][0] >> B[i][1];
--B[i][0];
B[i][2] = i;
}
static constexpr int block = 470;
sort(all(B), [&](auto a, auto b) {
if (a[0] / block != b[0] / block) return a[0] < b[0];
return a[1] > b[1];
});
vector<bool> ans(Q);
int curl = block, curr = M;
UndoableUF uf(N);
bool f = false;
for (auto [l, r, k] : B) {
if (f) {
ans[k] = false;
continue;
}
while (curl <= l) {
uf.rollback();
rep2 (i, curl - block, curl) {
if (i >= M) break;
uf.merge2(A[i].first, A[i].second);
}
uf.snapshot();
if (!uf.is_bip()) {
ans[k] = false;
f = true;
break;
}
curl += block;
curr = M;
}
if (f) continue;
assert(curr >= r);
rrep2 (i, r, curr) {
uf.merge(A[i].first, A[i].second);
}
curr = r;
rep2 (i, curl - block, l) {
uf.merge(A[i].first, A[i].second);
}
ans[k] = uf.is_bip();
rep2 (i, curl - block, l) uf.undo();
}
rep (i, Q) puts(ans[i] ? "NO" : "YES");
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
144 ms |
14272 KB |
Output is correct |
| 4 |
Correct |
116 ms |
14380 KB |
Output is correct |
| 5 |
Incorrect |
129 ms |
15668 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
