Monday, November 4, 2019

[Spoj] DYNACON1 - Dynamic Tree Connectivity

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : DYNACON1 - Dynamic Tree Connectivity
Source            : Spoj
Category          : Data Structure
Algorithm         : Dynamic Connectivity
Verdict           : Accepted

  1. #include "bits/stdc++.h"  
  2.   
  3. using namespace std;  
  4.   
  5. #define pii             pair <int, int>  
  6. #define mk              make_pair  
  7.   
  8. static const int maxn = 3e5 + 5;  
  9.   
  10. vector <pii> Tree[maxn * 4];  
  11.   
  12. void update(int node, int a, int b, int i, int j, pii p)  
  13. {  
  14.       if (a > j or b < i) return;  
  15.       if (a >= i and b <= j) return void(Tree[node].push_back(p));  
  16.       int lchild = node * 2;  
  17.       int rchild = lchild + 1;  
  18.       int mid = (a + b) / 2;  
  19.       update(lchild, a, mid, i, j, p);  
  20.       update(rchild, mid + 1, b, i, j, p);  
  21. }  
  22.   
  23. int par[maxn];  
  24. int sz[maxn];  
  25. stack <int> st;  
  26.   
  27. void makeSet()  
  28. {  
  29.       for (int i = 1; i < maxn; i++)  
  30.       {  
  31.             par[i] = i;  
  32.             sz[i] = 1;  
  33.       }  
  34. }  
  35.   
  36. int findRep(int r)  
  37. {  
  38.       if (r == par[r]) return r;  
  39.       return findRep(par[r]);  
  40. }  
  41.   
  42. void marge(int u, int v)  
  43. {  
  44.       int p = findRep(u);  
  45.       int q = findRep(v);  
  46.       if (p == q) return;  
  47.       if (sz[p] > sz[q]) swap(p, q);  
  48.       par[p] = q;  
  49.       sz[q] += sz[p];  
  50.       st.push(p);  
  51. }  
  52.   
  53. void rollback(int moment)  
  54. {  
  55.       while (st.size() > moment)  
  56.       {  
  57.             int curr = st.top(); st.pop();  
  58.             sz[ par[curr] ] -= sz[curr];  
  59.             par[curr] = curr;  
  60.       }  
  61. }  
  62.   
  63. bool ans[maxn];  
  64. pii query[maxn];  
  65.   
  66. void dfs(int node, int a, int b)  
  67. {  
  68.       if (a > b) return;  
  69.       int moment = st.size();  
  70.       for (pii p : Tree[node]) marge(p.first, p.second);  
  71.       if (a == b)  
  72.       {  
  73.             if (query[a].first > 0)  
  74.             {  
  75.                   int u = query[a].first;  
  76.                   int v = query[a].second;  
  77.                   ans[a] = findRep(u) == findRep(v);  
  78.             }  
  79.       }  
  80.       else  
  81.       {  
  82.             int lchild = node * 2;  
  83.             int rchild = lchild + 1;  
  84.             int mid = (a + b) / 2;  
  85.             dfs(lchild, a, mid);  
  86.             dfs(rchild, mid + 1, b);  
  87.       }  
  88.       rollback(moment);  
  89. }  
  90.   
  91. map <pii, int> in;  
  92. vector <int> queries;  
  93.   
  94. signed main()  
  95. {  
  96.       ios_base::sync_with_stdio(false);  
  97.       cin.tie(nullptr);  
  98.       cout.tie(nullptr);  
  99.   
  100.       #ifndef ONLINE_JUDGE  
  101.             freopen("in.txt""r", stdin);  
  102.       #endif // ONLINE_JUDGE  
  103.   
  104.       int n, q;  
  105.       cin >> n >> q;  
  106.       for (int i = 1; i <= q; i++)  
  107.       {  
  108.             string type;  
  109.             int a, b;  
  110.             cin >> type >> a >> b;  
  111.             if (a > b) swap(a, b);  
  112.             assert(a != b);  
  113.             if (type[0] == 'c')  
  114.             {  
  115.                   queries.push_back(i);  
  116.                   query[i] = mk(a, b);  
  117.             }  
  118.             else if (type[0] == 'r')  
  119.             {  
  120.                   if (!in.count(mk(a, b))) continue;  
  121.                   int l = in[mk(a, b)];  
  122.                   int r = i;  
  123.                   update(1, 1, q, l, r, mk(a, b));  
  124.                   in.erase(mk(a, b));  
  125.             }  
  126.             else  
  127.             {  
  128.                   if (in.count(mk(a, b))) continue;  
  129.                   in[mk(a, b)] = i;  
  130.             }  
  131.       }  
  132.       for (auto it : in)  
  133.       {  
  134.             int l = it.second;  
  135.             int r = q;  
  136.             int a = it.first.first;  
  137.             int b = it.first.second;  
  138.             update(1, 1, q, l, r, mk(a, b));  
  139.       }  
  140.       makeSet();  
  141.       dfs(1, 1, q);  
  142.       for (int p : queries) cout << (ans[p] ? "YES" : "NO") << '\n';  
  143. }  

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.