Advertisement
Guest User

Untitled

a guest
Jul 22nd, 2020
453
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.58 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <cstdio>
  4. #include <iomanip>
  5. #include <sstream>
  6. #include <cstring>
  7. #include <string>
  8. #include <cmath>
  9. #include <stack>
  10. #include <list>
  11. #include <queue>
  12. #include <deque>
  13. #include <set>
  14. #include <map>
  15. #include <vector>
  16. #include <algorithm>
  17. #include <numeric>
  18. #include <utility>
  19. #include <functional>
  20. #include <limits>
  21. using namespace std;
  22.  
  23. typedef long long ll;
  24. typedef unsigned long long ull;
  25. typedef unsigned int ui;
  26. typedef pair<int,int> pii;
  27. typedef vector<vector<int> > graph;
  28.  
  29. const double pi = acos(-1.0);
  30.  
  31. #define oned(a, x1, x2) { cout << #a << ":"; for(int _i = (x1); _i < (x2); _i++){ cout << " " << a[_i]; } cout << endl; }
  32. #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; } }
  33.  
  34. #define mp make_pair
  35. #define pb push_back
  36. #define fst first
  37. #define snd second
  38.  
  39. const int MAXN = 200005;
  40.  
  41. int n, m, q, a[MAXN], b[MAXN];
  42.  
  43. int parent[MAXN<<1];
  44.  
  45. void init() {
  46.     for(int i = 2; i <= 2*n+1; i++) {
  47.         parent[i] = i;
  48.     }
  49. }
  50.  
  51. int getParent(int v) {
  52.     if(parent[v]==v) {
  53.         return v;
  54.     } else {
  55.         return parent[v] = getParent(parent[v]);
  56.     }
  57. }
  58.  
  59. bool mergeSets(int u, int v) {
  60.     int pu = getParent(u<<1);
  61.     int pv = getParent(v<<1);
  62.     bool res;
  63.     if((pu>>1) == (pv>>1)) {
  64.         res = pu^pv;
  65.     } else {
  66.         parent[pu] = pv^1;
  67.         parent[pu^1] = pv;
  68.         res = true;
  69.     }
  70.     return res;
  71. }
  72.  
  73. struct elem {
  74.     int l, r, id;
  75.     elem(){}
  76.     bool operator < (const elem &e) const {
  77.         if(l != e.l) return l < e.l;
  78.         if(r != e.r) return r < e.r;
  79.         return id < e.id;
  80.     }
  81. };
  82.  
  83. elem que[MAXN];
  84.  
  85. int ans[MAXN];
  86.  
  87. void solve() {
  88.     sort(que+1,que+1+q);
  89.    
  90.     int ptr = 1;
  91.     while(ptr <= q) {
  92.         int pos = que[ptr].l;
  93.        
  94.         init();
  95.        
  96.         bool bip = true;
  97.  
  98.         for(int id = 1; id < pos; id++) {
  99.             if(!mergeSets(a[id],b[id])) {
  100.                 bip = false;
  101.                 break;
  102.             }
  103.         }
  104.        
  105.         int x = m+1;
  106.         if(bip) {
  107.             x = m;
  108.             while(x > pos) {
  109.                 if(!mergeSets(a[x],b[x])) {
  110.                     break;
  111.                 }
  112.                 x--;
  113.             }
  114.         }
  115.        
  116.        
  117.         while(ptr <= q && que[ptr].l == pos) {
  118.             ans[que[ptr].id] = que[ptr].r < x;
  119.             ptr++;
  120.         }
  121.     }
  122.    
  123.     for(int i = 1; i <= q; i++) {
  124.         printf(ans[i] ? "YES\n" : "NO\n");
  125.     }
  126. }
  127.  
  128. int main() {
  129.     //freopen("input.in", "r", stdin);
  130.     //freopen("output.out", "w", stdout);
  131.     while(scanf("%d %d %d", &n, &m, &q)==3) {
  132.         for(int i = 1; i <= m; i++) {
  133.             scanf("%d %d", a+i, b+i);
  134.         }
  135.         for(int i = 1; i <= q; i++) {
  136.             scanf("%d %d", &que[i].l, &que[i].r);
  137.             que[i].id = i;
  138.         }
  139.         solve();
  140.     }
  141. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement