#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> col;
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);
col.assign(n, 0);
for(int i = 0; i < n; i ++){
child[i] = {i};
}
}
void unite(int a, int b){
if(l[a] == l[b]){
if(col[a] == col[b]) odd = 1;
return;
}
if(len(child[l[a]]) > len(child[l[b]])) swap(a, b);
if(col[a] == col[b]){
for(auto u : child[a]) col[u] ^= 1;
}
a = l[a], b = l[b];
for(auto u : child[a]){
child[b].push_back(u);
l[u] = 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();
}
#ifdef LOCAL
cout << "\nDone" << endl;
#endif
}
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
58 ms |
16512 KB |
Output is correct |
| 4 |
Correct |
87 ms |
23312 KB |
Output is correct |
| 5 |
Incorrect |
58 ms |
20168 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
