[GYM] M - Mountaineers

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : M - Mountaineers
Source            : Codeforces GYM
Category          : Data Structure
Algorithm         : Disjoint Set Union
Verdict           : Accepted

Tutorial : https://codeforces.com/blog/entry/75369

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll            long long int  
#define endl          '\n'  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      int n, m, q;  
      cin >> n >> m >> q;  
      vector < vector <int> > cell_node(n + 1, vector <int>(m + 1));  
      vector < vector <int> > grid(n + 1, vector <int>(m + 1));  
      int ptr = 0;  
      for (int i = 1; i <= n; i++)  
      {  
            for (int j = 1; j <= m; j++)  
            {  
                  cin >> grid[i][j];  
                  cell_node[i][j] = ++ptr;  
            }  
      }  
      struct Edge  
      {  
            int u, v, w;  
            Edge(int u = 0, int v = 0, int w = 0)  
                  : u(u), v(v), w(w) {}  
            bool operator < (const Edge &other) const  
            {  
                  return w < other.w;  
            }  
      };  
      int dr[4] = {+0, -1, +0, +1};  
      int dc[4] = {-1, +0, +1, +0};  
      function <bool(int, int)> valid = [&](int r, int c)  
      {  
            return r >= 1 and r <= n and c >= 1 and c <= m;  
      };  
      vector <Edge> edges;  
      for (int i = 1; i <= n; i++)  
      {  
            for (int j = 1; j <= m; j++)  
            {  
                  for (int f = 0; f < 4; f++)  
                  {  
                        int x = i + dr[f];  
                        int y = j + dc[f];  
                        if (valid(x, y))  
                        {  
                              int u = cell_node[i][j];  
                              int v = cell_node[x][y];  
                              int w = max(grid[i][j], grid[x][y]);  
                              edges.emplace_back(u, v, w);  
                        }  
                  }  
            }  
      }  
      sort(edges.begin(), edges.end());  
      vector <int> par(ptr + 1);  
      vector <int> max_cost(ptr + 1);  
      vector <int> ans(q + 1);  
      set <int> st[ptr + 1];  
      for (int i = 1; i <= q; i++)  
      {  
            int x1, y1, x2, y2;  
            cin >> x1 >> y1 >> x2 >> y2;  
            if (x1 == x2 and y1 == y2)  
            {  
                  ans[i] = grid[x1][y1];  
                  continue;  
            }  
            int u = cell_node[x1][y1];  
            int v = cell_node[x2][y2];   
            st[u].insert(i);  
            st[v].insert(i);  
      }  
      for (int i = 1; i <= ptr; i++) par[i] = i;  
      function <int(int)> find_rep = [&](int r)  
      {  
            if (r == par[r]) return r;  
            return par[r] = find_rep(par[r]);  
      };  
      for (Edge it : edges)  
      {  
            int u = it.u;  
            int v = it.v;  
            int w = it.w;  
            int p = find_rep(u);  
            int q = find_rep(v);  
            if (p == q) continue;  
            int szp = st[p].size();  
            int szq = st[q].size();  
            if (szp < szq)  
            {  
                  swap(p, q);  
                  swap(max_cost[p], max_cost[q]);  
            }  
            vector <int> del;  
            for (int x : st[q])  
            {  
                  if (st[p].find(x) != st[p].end()) del.push_back(x);  
                  st[p].insert(x);  
            }  
            st[q].clear();  
            par[q] = p;  
            max_cost[p] = max(max_cost[p], max_cost[q]);  
            max_cost[p] = max(w, max_cost[p]);  
            for (int d : del)  
            {  
                  st[p].erase(d);  
                  ans[d] = max_cost[p];  
            }  
      }  
      for (int i = 1; i <= q; i++) cout << ans[i] << endl;  
}