#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
template<typename T>
int len(T &a){return a.size();}
struct DSU{
vector<vector<int>> child;
vector<int> l;
vector<int> dis;
int n;
bool odd = 0;
DSU (int _n){init(_n);}
void init(int _n){
n = _n;
child.resize(n);
l.resize(n); iota(all(l), 0);
dis.assign(n, 0);
for(int i = 0; i < n; i ++){
child[i] = {i};
}
}
int get(int x){
return (x == l[x] ? x : l[x] = get(l[x]));
}
void unite(int a, int b){
//cout << a << ' ' << b << endl;
int la = get(a), lb = get(b);
if(la == lb){
if((dis[a] + dis[b] + 1) % 2) odd = 1;
return;
}
if(len(child[la]) > len(child[lb])) swap(la, lb), swap(a, b);
int db = dis[b];
b = lb, a = la;
for(auto u : child[a]){
child[b].push_back(u);
dis[u] = db + 1;
}
l[a] = b;
child[a].clear();
}
};
void solve(){
int n, m, q; cin >> n >> m >> q;
vector<pair<int,int>> edge(m);
for(auto &[a, b] : edge) cin >> a >> b, a --, b --;
vector<vector<pair<int,int>>> qu(m);
for(int i = 0; i < q; i ++){
int l, r;
cin >> l >> r;
l --; r --;
qu[l].push_back({r, i});
}
vector<int> ans(q);
for(int i = 0; i < m; i ++){
if(len(qu[i]) == 0) continue;
DSU t(n);
//cout << i << endl;
for(int j = 0; j < i; j ++){
//cout << edge[j].ff << endl;
t.unite(edge[j].ff, edge[j].ss);
}
int r = m;
if(t.odd == 0){
r = i - 1;
for(int j = m - 1; j >= i; j --){
t.unite(edge[j].ff, edge[j].ss);
if(t.odd){
r = j;
break;
}
}
}
for(auto [rig, j] : qu[i]){
ans[j] = rig < r;
}
}
for(auto u : ans){
cout << (u ? "YES" : "NO") << '\n';
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int tests = 1;
while(tests --){
solve();
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
57 ms |
20424 KB |
Output is correct |
| 4 |
Correct |
75 ms |
26824 KB |
Output is correct |
| 5 |
Incorrect |
60 ms |
24428 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 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 |
- |
