#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct DSU{
int path[400400], rank[400400];
vector<array<int, 3>> st;
void init(int n){
st.clear();
for (int i=1;i<=n;i++) path[i] = i, rank[i] = 0;
}
int find(int s){
if (s==path[s]) return s;
return find(path[s]);
}
void merge(int x, int y){
x = find(x), y = find(y);
if (x==y) {st.push_back({-1, -1, -1}); return;}
if (rank[x] > rank[y]) swap(x, y);
st.push_back({x, y, rank[y]});
path[x] = y;
if (rank[x]==rank[y]) rank[y]++;
}
void pop(int cnt){
for (int i=1;i<=cnt;i++){
auto [x, y, r] = st.back(); st.pop_back();
if (x==-1) continue;
path[x] = x;
rank[y] = r;
}
}
}dsu;
int a[200200], b[200200], ans[200200], sz;
void rollback(int t){
dsu.pop((sz-t) * 2);
sz = t;
}
int push(int i){
dsu.merge(a[i]*2, b[i]*2+1);
dsu.merge(a[i]*2+1, b[i]*2);
sz++;
if (dsu.find(a[i]*2) == dsu.find(a[i]*2+1)) return 0;
return 1;
}
void dnc(int l, int r, int s, int e){
if (l > r) return;
int m = (l+r)>>1;
int t1 = sz;
for (int i=min(r, s-1);i>=m;i--) push(i);
int t2 = sz;
for (int i=max(s, m);i<=e;i++){
if (!push(i)) break;
ans[m] = i;
}
rollback(t2);
dnc(l, m-1, s, ans[m]);
rollback(t1);
for (int i=max(r+1, s);i<=ans[m]-1;i++) push(i);
dnc(m+1, r, ans[m], e);
rollback(t1);
}
int main(){
int n, m, q;
scanf("%d %d %d", &n, &m, &q);
for (int i=1;i<=m;i++) scanf("%d %d", a+i, b+i);
dsu.init(n*2+3);
dnc(1, m, 1, m);
while(q--){
int l, r;
scanf("%d %d", &l, &r);
if (ans[l] >= r) printf("YES\n");
else printf("NO\n");
}
}
Compilation message
Joker.cpp: In function 'int main()':
Joker.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | scanf("%d %d %d", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:80:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | for (int i=1;i<=m;i++) scanf("%d %d", a+i, b+i);
| ~~~~~^~~~~~~~~~~~~~~~~~~
Joker.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | scanf("%d %d", &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
