zipdang04

quygaquagy

Dec 6th, 2021 (edited)
625
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. using namespace __gnu_pbds;
  6.  
  7. typedef long long ll;
  8. typedef long double ld;
  9. typedef vector<int> vi;
  10. typedef vector<ll> vl;
  11. typedef pair<int, int> pii;
  12. typedef pair<ll, ll> pll;
  13. typedef map<int, int> mii;
  14. typedef unordered_map<int, int> umii;
  15. typedef map<ll, ll> mll;
  16. typedef unordered_map<ll, ll> umll;
  17. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  18.  
  19. // struct Node
  20. // {
  21. //  int node, len;
  22. //  Node() {node = len = 0;}
  23. //  Node(int node, int len) {this -> node = node, this -> len = len;}
  24. // };
  25. // typedef vector<Node> vg;
  26.  
  27. #define MAX 2000001
  28. #define MOD 1000000007
  29.  
  30. #define fi first
  31. #define se second
  32. #define pf push_front
  33. #define pb push_back
  34.  
  35. #define FOR(type, i, a, b) for(type i = (a); i <= (b); i++)
  36. #define FORR(type, i, b, a) for(type i = (b); i >= (a); i--)
  37.  
  38. #define testBit(n, bit) ((n >> bit) & 1)
  39. #define flipBit(n, bit) (n ^ (1ll << bit))
  40. #define cntBit(n) __builtin_popcount(n)
  41. #define cntBitll(n) __builtin_popcountll(n)
  42. #define randomize mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
  43.  
  44. struct Comp
  45. {
  46.     int num, ver;
  47.     Comp() {num = ver = 0;}
  48.     Comp(int num, int ver) {this -> num = num, this -> ver = ver;}
  49. };
  50.  
  51. int n, m;
  52. int ver[MAX];
  53. int pos[MAX];
  54.  
  55. Comp value[MAX];
  56. bool match[MAX] = {};
  57. int dsu[MAX], len;
  58.  
  59. int findRoot(int node){
  60.     if (dsu[node] < 0) return node;
  61.     dsu[node] = findRoot(dsu[node]);
  62.     return dsu[node];
  63. }
  64.  
  65. int join(int u, int v){
  66.     u = findRoot(u), v = findRoot(v);
  67.     if (u == v) return u;
  68.     if (dsu[u] > dsu[v]) swap(u, v);
  69.     dsu[u] += dsu[v]; dsu[v] = u;
  70.     return u;
  71. }
  72.  
  73. void transfer(int a, int b){
  74.     int verA = ver[a], verB = ver[b];
  75.     int posA = pos[a], posB = pos[b];
  76.     // cerr << "A - ver:" << verA << ", pos:" << posA << '\n';
  77.     // cerr << "B - ver:" << verB << ", pos:" << posB << '\n';
  78.    
  79.     if (match[posA]) return;
  80.     match[posA] = true;
  81.     // cerr << "A matched.\n";
  82.    
  83.     if (match[posB]){
  84.         // cerr << "B had matched, finding a new one...\n";
  85.         len++; ver[b]++, verB++;
  86.         value[len] = {b, verB};
  87.         posB = pos[b] = len;
  88.     }
  89.    
  90.     int root = join(posA, posB);
  91.     value[root] = {b, verB};
  92. }
  93.  
  94. Comp get(int node){
  95.     return value[findRoot(node)];
  96. }
  97.  
  98. main()
  99. {
  100.     ios_base::sync_with_stdio(0); cin.tie(0);
  101.     cin >> n >> m;
  102.     // memset(dsu, sizeof(dsu), -1);
  103.     fill(dsu, dsu + MAX, -1);
  104.     // /*check: */ cerr << "ok: " << (dsu[30] == -1) << ' ' << (dsu[1516] == -1) << '\n';
  105.     FOR(int, i, 1, n) ver[i] = 1, pos[i] = i, value[i] = {i, 1}; len = n;
  106.    
  107.     FOR(int, _, 1, m){
  108.         char q; cin >> q;
  109.         if (q == 'E'){
  110.             int a, b; cin >> a >> b;
  111.             transfer(a, b);
  112.         } else {
  113.             int x; cin >> x;
  114.             // Comp ohdear = get(x);
  115.             // cout << "ans: " << ohdear.num << ' ' << ohdear.ver<< '\n';
  116.             cout << get(x).num << '\n';
  117.         }
  118.     }
  119. }
RAW Paste Data