fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ft first
  4. #define sc second
  5. #define el '\n'
  6. #define boost ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  7. #define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout)
  8. #define pb push_back
  9. #define all(x) (x).begin(),(x).end()
  10. using namespace std;
  11. const ll N = 2e5;
  12. ll n, m, parent[N + 1], sz[N + 1];
  13. ll parent_go[N + 1], sz_go[N + 1];
  14.  
  15. void read() {
  16.     cin >> n >> m;
  17. }
  18.  
  19. void make_set() {
  20.     for(ll i = 1; i <= n; i ++) {
  21.         parent[i] = i;
  22.         sz[i] = 1;
  23.         parent_go[i] = i;
  24.         sz_go[i] = 1;
  25.     }
  26. }
  27.  
  28. ll find_set(ll k) {
  29.     if(k == parent[k]) return k;
  30.     return parent[k] = find_set(parent[k]);
  31. }
  32.  
  33. void union_set(ll u, ll v) {
  34.     ll x = find_set(u);
  35.     ll y = find_set(v);
  36.  
  37.     if(x != y) {
  38.         if(sz[x] < sz[y]) swap(x, y);
  39.  
  40.         parent[y] = x;
  41.         sz[x] += sz[y];
  42.     }
  43. }
  44.  
  45. ll find_go(ll k) {
  46.     if(k == parent_go[k]) return k;
  47.     return parent_go[k] = find_go(parent_go[k]);
  48. }
  49.  
  50. void union_go(ll u, ll v) {
  51.     ll x = find_go(u);
  52.     ll y = find_go(v);
  53.  
  54.     parent_go[x] = y;
  55. }
  56.  
  57. void solve() {
  58.     make_set();
  59.  
  60.     for(ll i = 1; i <= m; i ++) {
  61.         ll x, l, r; cin >> x >> l >> r;
  62.         if(x == 1) {
  63.             union_set(l, r);
  64.         } else if(x == 2) {
  65.             ll k = find_set(l);
  66.             while(1) {
  67.                 l = find_go(l + 1);
  68.                 if(l > r) break;
  69.                 ll t = find_set(l);
  70.                 if(t != k) {
  71.                     union_set(t, k);
  72.                 }
  73.                 union_go(l, l + 1);
  74.             }
  75.         } else {
  76.             ll x = find_set(l);
  77.             ll y = find_set(r);
  78.  
  79.             if(x != y) cout << "NO" << el;
  80.             else cout << "YES" << el;
  81.         }
  82.     }
  83. }
  84. void write() {
  85.  
  86. }
  87. int main() {
  88.     boost;
  89.     //file();
  90.     read();
  91.     solve();
  92.     write();
  93.     return 0;
  94. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ILV9fz
language:
C++14 (gcc 8.3)
created:
1 hour ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!