Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <cstdio>
- #include <iomanip>
- #include <sstream>
- #include <cstring>
- #include <string>
- #include <cmath>
- #include <stack>
- #include <list>
- #include <queue>
- #include <deque>
- #include <set>
- #include <map>
- #include <vector>
- #include <algorithm>
- #include <numeric>
- #include <utility>
- #include <functional>
- #include <limits>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef unsigned int ui;
- typedef pair<int,int> pii;
- typedef vector<vector<int> > graph;
- const double pi = acos(-1.0);
- #define oned(a, x1, x2) { cout << #a << ":"; for(int _i = (x1); _i < (x2); _i++){ cout << " " << a[_i]; } cout << endl; }
- #define twod(a, x1, x2, y1, y2) { cout << #a << ":" << endl; for(int _i = (x1); _i < (x2); _i++){ for(int _j = (y1); _j < (y2); _j++){ cout << (_j > y1 ? " " : "") << a[_i][_j]; } cout << endl; } }
- #define mp make_pair
- #define pb push_back
- #define fst first
- #define snd second
- const int MAXN = 200005;
- int n, m, q, a[MAXN], b[MAXN];
- int parent[MAXN<<1];
- void init() {
- for(int i = 2; i <= 2*n+1; i++) {
- parent[i] = i;
- }
- }
- int getParent(int v) {
- if(parent[v]==v) {
- return v;
- } else {
- return parent[v] = getParent(parent[v]);
- }
- }
- bool mergeSets(int u, int v) {
- int pu = getParent(u<<1);
- int pv = getParent(v<<1);
- bool res;
- if((pu>>1) == (pv>>1)) {
- res = pu^pv;
- } else {
- parent[pu] = pv^1;
- parent[pu^1] = pv;
- res = true;
- }
- return res;
- }
- struct elem {
- int l, r, id;
- elem(){}
- bool operator < (const elem &e) const {
- if(l != e.l) return l < e.l;
- if(r != e.r) return r < e.r;
- return id < e.id;
- }
- };
- elem que[MAXN];
- int ans[MAXN];
- void solve() {
- sort(que+1,que+1+q);
- int ptr = 1;
- while(ptr <= q) {
- int pos = que[ptr].l;
- init();
- bool bip = true;
- for(int id = 1; id < pos; id++) {
- if(!mergeSets(a[id],b[id])) {
- bip = false;
- break;
- }
- }
- int x = m+1;
- if(bip) {
- x = m;
- while(x > pos) {
- if(!mergeSets(a[x],b[x])) {
- break;
- }
- x--;
- }
- }
- while(ptr <= q && que[ptr].l == pos) {
- ans[que[ptr].id] = que[ptr].r < x;
- ptr++;
- }
- }
- for(int i = 1; i <= q; i++) {
- printf(ans[i] ? "YES\n" : "NO\n");
- }
- }
- int main() {
- //freopen("input.in", "r", stdin);
- //freopen("output.out", "w", stdout);
- while(scanf("%d %d %d", &n, &m, &q)==3) {
- for(int i = 1; i <= m; i++) {
- scanf("%d %d", a+i, b+i);
- }
- for(int i = 1; i <= q; i++) {
- scanf("%d %d", &que[i].l, &que[i].r);
- que[i].id = i;
- }
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement