#include <bits/stdc++.h>
#define uwu return 0;
using namespace std;
#define fs first
#define sc second
const int SIZE = 2e5 + 5;
const int PERSIST = -1, IS_BIPARTITE = -2;
struct check_bipartite{
int N;
struct Disjoint_Set_Union{
stack <pair<int, int>> rollback;
int DSU[2 * SIZE];
bool status = 1;
inline void init(int n){
for (int i = 1; i <= 2 * n;i++){
DSU[i] = -1;
}
return;
}
inline int find_parent(int node){
if(DSU[node] < 0)
return node;
int pa = find_parent(DSU[node]);
rollback.push({node, DSU[node]});
return DSU[node] = pa;
}
inline void merge(int a, int b){
a = find_parent(a);
b = find_parent(b);
if(a == b)
return;
rollback.push({a, DSU[a]});
rollback.push({b, DSU[b]});
if(DSU[b] <= DSU[a])
swap(a, b);
DSU[a] += DSU[b];
DSU[b] = a;
return;
}
inline void checkpoint(){
rollback.push({PERSIST, 0});
return;
}
inline void roll(){
while(rollback.top().fs != PERSIST){
if(rollback.top().fs == IS_BIPARTITE)
status = rollback.top().sc;
else{
DSU[rollback.top().fs] = rollback.top().sc;
}
rollback.pop();
}
rollback.pop();
return;
}
} dsu;
void add(int a, int b){
dsu.merge(a, b + N), dsu.merge(b, a + N);
if(dsu.find_parent(a) == dsu.find_parent(a + N) || dsu.find_parent(b) == dsu.find_parent(b + N)){
dsu.rollback.push({IS_BIPARTITE, dsu.status});
dsu.status = 0;
}
}
}black_box;
int lft[SIZE];
pair <int, int> edge[SIZE];
void solve(int nl, int nr, int pl, int pr){
// cout << nl << ' ' << nr << ' ' << pl << ' ' << pr << '\n';
int nm = (nl + nr) / 2, pm;
black_box.dsu.checkpoint();
for (int i = nr; i > nm; i--){
black_box.add(edge[i].fs, edge[i].sc);
}
black_box.dsu.checkpoint();
pm = pl - 1;
while(black_box.dsu.status && pm <= min(nm, pr - 1)){
pm++;
black_box.add(edge[pm].fs, edge[pm].sc);
}
black_box.dsu.roll();
lft[nm] = pm;
black_box.add(edge[nm].fs, edge[nm].sc);
// cout << nm << ' ' << pm << '\n';
if(pm > 0 && nl != nm)
solve(nl, nm - 1, pl, pm);
black_box.dsu.roll(), black_box.dsu.checkpoint();
for (int i = pl; i < pm; i++){
black_box.add(edge[i].fs, edge[i].sc);
}
if(nm != nr)
solve(nm + 1, nr, max(pm, 1), pr);
black_box.dsu.roll();
return;
}
int main(){
int N, M, Q;
cin >> N >> M >> Q;
black_box.N = N;
black_box.dsu.init(N);
for (int i = 1; i <= M;i++){
cin >> edge[i].fs >> edge[i].sc;
}
solve(1, M, 1, M + 1);
for (int l, r; Q--;){
cin >> l >> r;
lft[r] >= l ? cout << "YES\n" : cout << "NO\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
152 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
152 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
152 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
152 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
152 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
152 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |