manish

Untitled

Sep 15th, 2020
760
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int parent[200003], size[200003], maxi[200003];
  6. int parent2[200003], size2[200003], maxi2[200003];
  7.  
  8. void perform() {
  9.   for (int i = 0; i < 200003; i++) {
  10.     parent[i] = i;
  11.     size[i] = 1;
  12.     maxi[i] = i;
  13.     parent2[i] = i;
  14.     size2[i] = 1;
  15.     maxi2[i] = i;
  16.   }
  17. }
  18.  
  19. int get(int a) {
  20.   if (parent[a] == a) return a;
  21.   int x = a;
  22.   while (a != parent[a]) {
  23.     a = parent[a];
  24.   }
  25.   while (x != parent[x]) {
  26.     int temp = parent[x];
  27.     parent[x] = a;
  28.     x = temp;
  29.   }
  30.   return a;
  31. }
  32.  
  33. int get2(int a) {
  34.   if (parent2[a] == a) return a;
  35.   int x = a;
  36.   while (a != parent2[a]) {
  37.     a = parent2[a];
  38.   }
  39.   while (x != parent2[x]) {
  40.     int temp = parent2[x];
  41.     parent2[x] = a;
  42.     x = temp;
  43.   }
  44.   return a;
  45. }
  46.  
  47. void unioon(int a, int b) {
  48.   a = get(a);
  49.   b = get(b);
  50.   if (a != b) {
  51.     if (size[a] > size[b]) swap(b, a);
  52.     parent[a] = b;
  53.     size[b] += size[a];
  54.     maxi[b] = max(maxi[a], maxi[b]);
  55.   }
  56. }
  57.  
  58. void unioon2(int a, int b) {
  59.   a = get2(a);
  60.   b = get2(b);
  61.   if (a != b) {
  62.     if (size2[a] > size2[b]) swap(b, a);
  63.     parent2[a] = b;
  64.     size2[b] += size2[a];
  65.     maxi2[b] = max(maxi2[a], maxi2[b]);
  66.   }
  67. }
  68.  
  69. int main() {
  70.   ios_base::sync_with_stdio(false);
  71.   cin.tie(0);
  72.   int m;
  73.   cin >> m >> m;
  74.   perform();
  75.   int x, y, z;
  76.   while (m--) {
  77.     cin >> x >> y >> z;
  78.     if (x == 1) unioon(y, z);
  79.     if (x == 2) {
  80.       int p = maxi2[y];
  81.       while (p < z) {
  82.         unioon(p, z);
  83.         unioon2(p, p + 1);
  84.         p = maxi2[p + 1];
  85.       }
  86.       unioon2(y, z);
  87.     }
  88.  
  89.     if (x == 3) {
  90.       int ans = (get(y) == get(z));
  91.       if (ans) cout << "YES\n";
  92.       else cout << "NO\n";
  93.     }
  94.  
  95.   }
  96.   return 0;
  97. }
RAW Paste Data