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;
#define ii pair<int, int>
#define tp tuple<int, int, int>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
const int N = 2e5 + 5,
block = 448;
int n, m, q;
ii edge[N];
bool pre, res[N];
int pa[N], sz[N], lz[N], it;
pair<int*, int> trace[3*N];
vector<tp> que[block + 5];
int fset(int i, int &c){
c ^= lz[i];
return i == pa[i] ? i : fset(pa[i], c);
}
bool uset(int u, int v){
int cu = 0, cv = 0;
u = fset(u, cu);
v = fset(v, cv);
if(u == v){
if(cu == cv) return true;
return false;
}
if(sz[u] < sz[v]) swap(u, v);
trace[it++] = {pa + v, pa[v]}; pa[v] = u;
trace[it++] = {sz + u, sz[u]}; sz[u] += sz[v];
if(cu == cv){
trace[it++] = {lz + v, lz[v]};
lz[v] ^= 1;
}
return false;
}
void rollback(int t){
for(; it > t; ){
it--;
*trace[it].fi = trace[it].se;
}
}
int getblock(int i){
return (i - 1) / block + 1;
}
void solve(int b, vector<tp> &query){
int lst = m;
int flag = it;
bool val = false;
for(auto x : query){
int l, r, idx; tie(r, l, idx) = x;
if(r <= b*block){
for(int i = lst; i > b * block; i--) uset(edge[i].fi, edge[i].se);
int tmp = it;
bool ok = false;
for(int i = (b - 1) * block + 1; i <= min(b * block, m); i++){
if(l <= i && i <= r) continue;
if(uset(edge[i].fi, edge[i].se)){
ok = true;
break;
}
}
res[idx] = ok;
rollback(tmp);
}else{
for(int i = lst; i > r; i--)
val |= uset(edge[i].fi, edge[i].se);
lst = r;
int tmp = it;
bool dd = false;
for(int i = (b - 1) * block + 1; i < l; i++) dd |= uset(edge[i].fi, edge[i].se);
res[idx] = dd | val | pre;
rollback(tmp);
}
}
rollback(flag);
for(int i = (b - 1) * block + 1; i <= min(b * block, m); i++) pre |= uset(edge[i].fi, edge[i].se);
}
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
// #define task "test"
// if(fopen(task ".inp", "r")){
// freopen(task ".inp", "r", stdin);
// freopen(task ".out", "w", stdout);
// }
cin >> n >> m >> q;
for(int i = 1; i <= m; i++){
int u, v; cin >> u >> v;
edge[i] = {u, v};
}
for(int t = 1; t <= q; t++){
int l, r; cin >> l >> r;
que[getblock(l)].push_back({r, l, t});
}
for(int i = 1; i <= block; i++) sort(all(que[i]), greater<>());
for(int i = 1; i <= n; i++){
pa[i] = i;
sz[i] = 1;
lz[i] = 0;
}
for(int i = 1; i <= block; i++) solve(i, que[i]);
for(int i = 1; i <= q; i++) cout << (res[i] ? "YES\n" : "NO\n");
return 0;
}
# | 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... |