Advertisement
aayyk

Untitled

Nov 13th, 2019
156
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.06 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <queue>
  7. #include <stack>
  8. #include <climits>
  9. #include <string>
  10. #include <set>
  11. #include <cmath>
  12. #include <map>
  13. #include <unordered_map>
  14. #include <numeric>
  15. #include <random>
  16. #include <memory>
  17. #include <chrono>
  18. #include <iterator>
  19. #include <functional>
  20. #include <unordered_set>
  21. #include <cassert>
  22. #ifdef LOCAL
  23. #include "debug.h"
  24. #else
  25. #define debug(x...)
  26. #endif
  27. //#pragma GCC optimize("Ofast")
  28. //#define int ll
  29.  
  30.  
  31.  
  32. using namespace std;
  33. typedef long long ll;
  34. typedef long double ld;
  35. typedef pair <int, int> pii;
  36. #define mp make_pair
  37. #define pb push_back
  38. #define sz(x) int((x).size())
  39.  
  40. #ifndef LOCAL
  41. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  42. #else
  43. mt19937 rng(228);
  44. #endif
  45.  
  46. const int N = 1e5 + 7;
  47. const int inf = INT_MAX / 2;
  48. const ll INF = LLONG_MAX / 3;
  49. const int MOD = 1e9 + 7;
  50. const double eps = 1e-6;
  51. const string cars[] = {"🚗", "🚕", "🚙"};
  52.  
  53.  
  54. set < int > s[N];
  55.  
  56. struct dsu {
  57.     vector <int> p, rang;
  58.  
  59.     dsu(int n) {
  60.         p.resize(n);
  61.         iota(p.begin(), p.end(), 0);
  62.         rang.resize(n);
  63.     }
  64.     dsu() {};
  65.  
  66.     int find(int x) {
  67.         return (p[x] == x ? x : p[x] = find(p[x]));
  68.     }
  69.  
  70.     void join(int x, int y) {
  71.         int a = find(x);
  72.         int b = find(y);
  73.  
  74.         if (a != b) {
  75.             set < int > t;
  76.             for (int x : s[a]) {
  77.                 s[x].erase(a);
  78.                 t.insert(x);
  79.             }
  80.            
  81.             for (int x : s[b]) {
  82.                 s[x].erase(b);
  83.                 t.insert(x);
  84.             }
  85.            
  86.  
  87.             if (rang[a] <= rang[b]) {
  88.                 p[a] = b;
  89.                 if (rang[a] == rang[b]) {
  90.                     rang[b]++;
  91.                 }
  92.                 s[a] = t;
  93.  
  94.                 for (int x : t) {
  95.                     s[x].insert(a);
  96.                 }
  97.             }
  98.             else {
  99.                 p[b] = a;
  100.                 s[b] = t;
  101.  
  102.  
  103.                 for (int x : t) {
  104.                     s[x].insert(b);
  105.                 }
  106.             }
  107.         }
  108.     }
  109.  
  110.     void add(int v) {
  111.         int t = p.size();
  112.         for (int i = t; i < t + v; i++) {
  113.             p.push_back(p.size());
  114.             rang.push_back(0);
  115.         }
  116.     }
  117. } a(N);
  118.  
  119.  
  120. signed main() {
  121. #ifdef LOCAL
  122.     freopen("input.txt", "r", stdin);
  123.     freopen("output.txt", "w", stdout);
  124. #endif
  125.     cout << fixed << setprecision(4);
  126.     ios::sync_with_stdio(false);
  127.     cin.tie();
  128.     cout.tie();
  129.  
  130.     int n, q;
  131.     cin >> n >> q;
  132.  
  133.     while (q--) {
  134.         char cc;
  135.         int u, v;
  136.         cin >> cc >> u >> v;
  137.  
  138.         if (cc == '+') {
  139.             a.join(u, v);
  140.         }
  141.         else if (cc == '-') {
  142.             s[a.find(u)].insert(a.find(v));
  143.             s[a.find(v)].insert(a.find(u));
  144.         }
  145.         else {
  146.             int q = a.find(u), w = a.find(v);
  147.             if (q == w) {
  148.                 cout << "+\n";
  149.             }
  150.             else if (s[q].find(w) != s[q].end() || s[w].find(q) != s[w].end()) {
  151.                 cout << "-\n";
  152.             }
  153.             else {
  154.                 cout << "?\n";
  155.             }
  156.         }
  157.     }
  158.  
  159.  
  160.     return 0;
  161. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement