[Gym] 102021M - Mountaineers

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 102021M - Mountaineers
Source            : Codeforces Gym
Category          : Graph Theory
Algorithm         : Minimum Spanning Tree, LCA
Verdict           : Accepted

Minimum Spanning Tree from 2D grid.

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define pii       pair <int, int>  
  
static const int maxn = 500 + 5;  
static const int Max = 500 * 500 + 5;  
static const int logn = 16;  
  
int dr[] = {+0, -1, +0, +1};  
int dc[] = {-1, +0, +1, +0};  
  
struct Edge  
{  
    int u, v, w;  
    Edge(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {}  
    friend bool operator < (Edge A, Edge B)  
    {  
        return A.w < B.w;  
    }  
};  
  
struct Node  
{  
    int v, w;  
    Node(int v = 0, int w = 0) : v(v), w(w) {}  
};  
  
vector <Edge> Edges;  
int which_node[maxn][maxn], wgt[maxn][maxn];  
int par[Max];  
  
vector <Node> graph[Max];  
  
void makeSet()  
{  
    for (int i = 1; i < Max; i++) par[i] = i;  
}  
  
int findRep(int r)  
{  
    if (r == par[r]) return r;  
    return par[r] = findRep(par[r]);  
}  
  
void kruskal()  
{  
    makeSet();  
    sort(Edges.begin(), Edges.end());  
    for (Edge E : Edges)  
    {  
        int u = E.u;  
        int v = E.v;  
        int w = E.w;  
        int p = findRep(u);  
        int q = findRep(v);  
        if (p != q)  
        {  
            graph[u].emplace_back(v, w);  
            graph[v].emplace_back(u, w);  
            par[q] = p;  
        }  
    }  
}  
  
struct info  
{  
    int f, w;  
    info(int f = 0, int w = 0) : f(f), w(w) {}  
};  
  
int depth[Max];  
info father[Max][logn];  
  
void dfs(int u = 1, int p = -1)  
{  
    for (int i = 1; i < logn; i++)  
    {  
        int f = father[u][i-1].f;  
        father[u][i].f = father[f][i-1].f;  
        father[u][i].w = max(father[f][i-1].w, father[u][i-1].w);  
    }  
    for (Node g : graph[u])  
    {  
        int v = g.v;  
        int w = g.w;  
        if (v == p) continue;  
        depth[v] = depth[u] + 1;  
        father[v][0].f = u;  
        father[v][0].w = w;  
        dfs(v, u);  
    }  
}  
  
pii findLCA(int u, int v)  
{  
    if (depth[u] < depth[v]) swap(u, v);  
    int maxi = -1;  
    for (int i = logn-1; i >= 0; i--)  
    {  
        if (depth[father[u][i].f] >= depth[v])  
        {  
            maxi = max(maxi, father[u][i].w);  
            u = father[u][i].f;  
        }  
    }  
    if (u == v) return pii(u, maxi);  
    for (int i = logn-1; i >= 0; i--)  
    {  
        if (father[u][i].f != father[v][i].f)  
        {  
            maxi = max(maxi, father[u][i].w);  
            maxi = max(maxi, father[v][i].w);  
            u = father[u][i].f;  
            v = father[v][i].f;  
        }  
    }  
    maxi = max(maxi, father[u][0].w);  
    maxi = max(maxi, father[v][0].w);  
    return pii(father[u][0].f, maxi);  
}  
  
int main()  
{  
    //freopen("in.txt", "r", stdin);  
  
    ios_base::sync_with_stdio(false);  
    cin.tie(nullptr);  
  
    int row, column, query;  
    cin >> row >> column >> query;  
    int ptr = 0;  
    for (int i = 1; i <= row; i++)  
    {  
        for (int j = 1; j <= column; j++)  
        {  
            which_node[i][j] = ++ptr;  
            cin >> wgt[i][j];  
        }  
    }  
    for (int i = 1; i <= row; i++)  
    {  
        for (int j = 1; j <= column; j++)  
        {  
            int u = which_node[i][j];  
            for (int k = 0; k < 4; k++)  
            {  
                int x = i + dr[k];  
                int y = j + dc[k];  
                bool valid = (x >= 1 && x <= row && y >= 1 && y <= column);  
                if (valid)  
                {  
                    int v = which_node[x][y];  
                    int w = max(wgt[i][j], wgt[x][y]);  
                    Edges.emplace_back(u, v, w);    
                }  
            }  
        }  
    }  
    kruskal();  
    depth[1] = 1;  
    dfs();  
    while (query--)  
    {  
        int x1, y1, x2, y2;  
        cin >> x1 >> y1 >> x2 >> y2;  
        int u = which_node[x1][y1];  
        int v = which_node[x2][y2];  
        if (u == v)  
        {  
            cout << wgt[x1][y1] << endl;  
            continue;  
        }  
        pii ans = findLCA(u, v);  
        assert(ans.second != -1);   
        cout << ans.second << endl;  
    }  
}