fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define double long double
  4. #define endl '\n'
  5. #define fi first
  6. #define se second
  7. #define vi vector<int>
  8. #define pii pair<int, int>
  9. #define TIME 1.0 * clock() / CLOCKS_PER_SEC
  10. #define all(v) v.begin(), v.end()
  11. using namespace std;
  12. typedef long long ll;
  13. bool M1;
  14.  
  15. template <typename T> void maximize(T &a, T b){if(a < b) a = b;}
  16. template <typename T> void minimize(T &a, T b){if(a > b) a = b;}
  17.  
  18. const int MAXN = 4e5 + 7;
  19.  
  20. int n, t;
  21. int enemy[MAXN];
  22.  
  23.  
  24. struct DSU{
  25.     int n;
  26.     vector <int> par;
  27.  
  28.     DSU(int _n) : n(_n) {par.assign(n + 7, -1);}
  29.  
  30.     int find(int u){return par[u] < 0 ? u : u = find(par[u]);}
  31.  
  32.     bool join(int x, int y){
  33.         x = find(x);
  34.         y = find(y);
  35.  
  36.         if(x == y) return 0;
  37.  
  38.         if(par[x] > par[y]) swap(x, y);
  39.  
  40.         par[x] += par[y];
  41.         par[y] = x;
  42.  
  43.         return 1;
  44.     }
  45.  
  46. };
  47.  
  48.  
  49.  
  50. signed main(){
  51.     ios_base::sync_with_stdio(0);
  52.     cout.tie(0);
  53.     cin.tie(0);
  54.  
  55. //    freopen("t.inp", "r", stdin);
  56. //    freopen("t.out", "w", stdout);
  57.  
  58.  
  59.     cin >> n >> t;
  60.  
  61.     DSU dsu(2 * n + 5);
  62.  
  63.     auto otherSide = [&](int &x){return n + x;};
  64.  
  65.     while(t--){
  66.         int type, x, y;
  67.  
  68.         cin >> type >> x >> y;
  69.  
  70.  
  71.         if(type == 0){
  72.             dsu.join(x, y);
  73.             dsu.join(otherSide(x), otherSide(y));
  74.         }
  75.  
  76.         else if(type == 1){
  77.             dsu.join(x, otherSide(y));
  78.             dsu.join(y, otherSide(x));
  79.         }
  80.  
  81.         else{
  82.  
  83.             if(dsu.find(x) == dsu.find(otherSide(y))) cout << 1 << endl;
  84.             else if(dsu.find(x) == dsu.find(y)) cout << 0 << endl;
  85.             else cout << -1 << endl;
  86.  
  87.         }
  88.  
  89.     }
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96. }
  97. /*
  98. Link: 
  99. oj.vnoi.info/problem/bedao_r22_e
  100.  
  101. Sol:
  102. ibb.co/DHXS9BNj
  103.  
  104.  
  105. - Cách làm:
  106.  
  107. Ta nén mấy đỉnh có cùng cực (đẩy nhau) thành 1 đỉnh bằng DSU
  108.  
  109. Và nối mấy cái đỉnh hút nhau (trái cực) thành 1 cái cây và được hình minh hoạ kia.
  110.  
  111. Quan sát cây, nhận xét được rằng:
  112.  
  113. Để tính được mối quan hệ giữa 2 đỉnh thì trước hết nó phải cùng thuộc 1 cái cây trước đã, và khoảng cách giữa chúng là lẻ thì mới hút nhau, ngược lại thì đẩy.
  114.  
  115. Vậy làm sao để xử lí được bài toán con này? Ta hãy xem cách làm ở phần bên phải kia.
  116.  
  117.  
  118. - Idea cho subproblem:
  119.  
  120. Gọi e(x) = otherSide(x) = n + x, là cực khác của (x)
  121.  
  122.  
  123. Theo hình trên quan sát được thì:
  124.  
  125.  
  126.  
  127. (2) = e(1)              (1) = e(2)
  128.  
  129.  
  130.  
  131. (3) = e(2)              (2) = e(3)
  132.  
  133.  
  134.  
  135. (4) = e(3)              (3) = e(4)
  136.  
  137.  
  138.  
  139. (5) = e(4)              (4) = e(3)
  140.  
  141. Nếu hút nhau/khác cực (khoảng cách là lẻ) thì find(u) = find(e(v)) hoặc ngược lại. (cái này nháp là ra...)
  142.  
  143. Nếu đẩy nhau/cùng cực (khoảng cách là chẵng) thì
  144. find(u) = find(v), cũng như find(u) != find(e(v))
  145.  
  146. Có nghĩa nếu khác cực thì
  147.  
  148. TH còn lại: -1
  149.  
  150. ==> Ta sử dụng tính chất 1 đỉnh có 2 cực là để gán cùng cực và trái cực để tạo thành 1 cái cây nối các đỉnh hút nhau và có tính ziczac để tạo tính chẵn lẻ
  151.  
  152.  
  153. */
  154.  
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/27CDtc
language:
C++14 (gcc 8.3)
created:
1 day 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!