Advertisement
Nik_Perepelov

Доп контест 2 задача Соне

Nov 17th, 2021
1,054
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.55 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int parent[150000];
  6. int my_rank[150000];
  7.  
  8. void make_set (int v) {
  9.     parent[v] = v;
  10.     my_rank[v] = 0;
  11. }
  12.  
  13. int find_set (int v) {
  14.     if (v == parent[v])
  15.         return v;
  16.     return find_set (parent[v]);
  17. }
  18.  
  19. void union_sets (int a, int b) {
  20.     a = find_set (a);
  21.     b = find_set (b);
  22.     if (a != b) {
  23.         if (my_rank[a] < my_rank[b])
  24.             swap (a, b);
  25.         parent[b] = a;
  26.         if (my_rank[a] == my_rank[b])
  27.             ++my_rank[a];
  28.     }
  29. }
  30.  
  31. int main(){
  32.     int n, m, k;
  33.     cin >> n >> m >> k;
  34.     vector<int> questions[3];
  35.     questions[0].resize(k);
  36.     questions[1].resize(k);
  37.     questions[2].resize(k);
  38.     for (int i = 0; i < n; i++)
  39.         make_set(i);
  40.     for (int i = 0; i < m; i++){
  41.         int a, b;
  42.         cin >> a >> b;
  43.     }
  44.     for (int i = 0; i < k; i++){
  45.         string data;
  46.         int a, b;
  47.         cin >> data >> a >> b;
  48.         if (data == "ask")
  49.             questions[0][i] = 1;
  50.         else
  51.             questions[0][i] = 2;
  52.         questions[1][i] = a - 1;
  53.         questions[2][i] = b - 1;
  54.     }
  55.  
  56.     vector<bool> result;
  57.     for (int i = k - 1; i >= 0; i--){
  58.         if (questions[0][i] == 1){
  59.             result.push_back(find_set(questions[1][i]) == find_set(questions[2][i]));
  60.         } else
  61.             union_sets(questions[1][i], questions[2][i]);
  62.     }
  63.  
  64.     for (int i = result.size() - 1; i >= 0; i--) {
  65.         if (result[i])
  66.             cout << "YES\n";
  67.         else
  68.             cout << "NO\n";
  69.     }
  70. }
  71.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement