Flyover in Twinland

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mems(x,v) memset(x,v,sizeof(x))
#define LL long long
#define Size 505
#define INF (1<<30)
int dir4[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};

struct Edge{
    int u;
    int v;
    LL w;
    LL factor;
    Edge(){
        u = v = w = factor = 0;
    }
    Edge(int a,int b,LL c,LL d){
        u = a;v = b;w = c;factor = d;
    }
};

bool cmp(Edge a,Edge b){
    return (a.w<b.w);
}

int N,M,V,E;
int clr = 0;

LL Mat[Size][Size];
LL color[Size][Size];
bool vis[Size][Size];
int Szz[500000];
int Graph[500000][105];

Edge eList[5000000];
int parent[500000];

bool isValid(int r,int c){
    if(r<0 || c<0 || r>=N || c>=M) return false;
    return true;
}

int DFS1(int r,int c,int id){
    color[r][c] = id;
    vis[r][c] = true;
    int res = 0;
    for(int i = 0;i<4;i++){
        int nr = r + dir4[i][0];
        int nc = c + dir4[i][1];
        if(isValid(nr,nc) == false) continue;
        if(vis[nr][nc] == true) continue;
        if(Mat[nr][nc] == 0) continue;
        res += (DFS1(nr,nc,id) + 1);
    }
    return res;
}

/// Color all the islands and count number of cities in those islands:

void DFS2(int r,int c,int id){
    Graph[id][Mat[r][c]] = 1;
    vis[r][c] = true;
    for(int i = 0;i<4;i++){
        int nr = r + dir4[i][0];
        int nc = c + dir4[i][1];
        if(isValid(nr,nc) == false) continue;
        if(vis[nr][nc] == true) continue;
        if(Mat[nr][nc] == 0) continue;
        DFS2(nr,nc,id);
    }
}

/// Find all the edges and build the graph:

void updateGraph(){
    V = E = 0;
    mems(vis,false);
    mems(color,-1);
    int cc = 0;
    for(int i = 0;i<N;i++){
        for(int j = 0;j<M;j++){
            if(vis[i][j] == true) continue;
            if(Mat[i][j] == 0) continue;
            int t = DFS1(i,j,cc) + 1;
            Szz[cc] = t;
            cc++;
        }
    }
    mems(vis,false);
    mems(Graph,0);
    for(int i = 0;i<N;i++){
        for(int j = 0;j<M;j++){
            if(vis[i][j] == true) continue;
            if(Mat[i][j] == 0) continue;
            int cc = color[i][j];
            if(Szz[cc]>=100){
                DFS2(i,j,V);
                V++;
            }
        }
    }
}

int getParent(int u){
    if(parent[u] == u) return u;
    return parent[u] = getParent(parent[u]);
}

/// Minimum spanning tree kruskal algorithm:

LL MST(LL factorLimit){
    for(int i = 0;i<V;i++){
        parent[i] = i;
    }
    LL cnt = 0,cost = 0;
    for(int i = 0;i<E;i++){
        Edge e = eList[i];
        if(e.factor > factorLimit) continue;
        int parU = getParent(e.u);
        int parV = getParent(e.v);
        if(parU != parV){
            cnt++;
            cost += e.w;
            parent[parU] = parV;
        }
    }
    if(cnt != V-1) return -1;
    return cost;
}

/// Find both salary & construction cost to build a flyover from u to v:

pair<LL,LL> getMinimumCost(int u,int v){
    LL prvU = -1,prvV = -1;
    LL rs = INF,w = 0;
    for(int cc = 1;cc<100;cc++){
        if(Graph[u][cc] == 1) prvU = cc;
        if(Graph[v][cc] == 1) prvV = cc;
        if(prvU != -1 && prvV != -1){
            rs = min(rs,abs(prvU - prvV));
        }
        if(Graph[u][cc] == 1 || Graph[v][cc] == 1) w++;
    }
    return make_pair(rs,w*w);
}

void solve(){
    updateGraph();
    for(int u = 0;u<V;u++){
        for(int v = u+1;v<V;v++){
            pair<LL,LL> pr = getMinimumCost(u,v);
            eList[E++] = Edge(u,v,pr.first,pr.second);
        }
    }

    sort(eList,eList+E,cmp);
    LL L = 0,R = 20000,cnt = 30,M;
    LL resFactor,resCost;
    if(V<=1){
        printf("0 0\n");
        return;
    }

    /// Binary search for the maximum salary Rio'll have to pay:
    while(cnt--){
        M = (L+R)/2;
        int cs = MST(M);
        if(cs != -1){
            R = M;
            resFactor = M;
            resCost = cs;
        }else{
            L = M+1;
        }
    }
    printf("%lld %lld\n",resFactor,resCost);
}

int main(){
    scanf("%d %d",&N,&M);
    for(int i = 0;i<N;i++){
        for(int j = 0;j<M;j++){
            scanf("%lld",&Mat[i][j]);
        }
    }
    mems(vis,false);

    /// First we find all the components:
    DFS1(0,0,0);
    solve();
    return 0;
}