[toph.co] Flyover in Twinland

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Flyover in Twinland
Source            : toph.co
Category          : Graph Theory
Algorithm         : Minimum Spanning Tree, Kruskal Algorithm
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
using ll = long long;
 
static const int maxn = 1e5 + 5;
 
int dr[] = {1, -1, 0, 0};
int dc[] = {0, 0, 1, -1};
 
ll grid[510][510];
set <ll> weight_in_a_island[maxn];
bool weight[maxn][110];
int city_in_this_island[maxn];
bool vis[510][510];
int row, column;
 
inline bool inside(int r, int c)
{
	return r >= 1 && r <= row && c >= 1 && c <= column;
}
 
inline void dfs(int sx, int sy, int island)
{
	vis[sx][sy] = 1;
	weight_in_a_island[island].insert(grid[sx][sy]);
	weight[island][ grid[sx][sy] ] = 1;
	city_in_this_island[island]++;
	for (int i = 0; i < 4; i++)
	{
		int x = sx + dr[i];
		int y = sy + dc[i];
		if (!inside[x][y] or vis[x][y] or grid[x][y] <= 0) continue;
		dfs(x, y, island);
	}
}
 
 
inline ll getMinDifference(int island1, int island2)
{
	ll mindif = 1e15;
	for (int i = 1; i < 100; i++)
      {
            if (weight_in_a_island[island1].find(i) != weight_in_a_island[island1].end())
            {
                  auto it = weight_in_a_island[island2].lower_bound(i);
                  if (it != weight_in_a_island[island2].end())
                  {
                        ll dif = abs(i - *it);
                        if (dif < mindif) mindif = dif;
                  }
                  if (it != weight_in_a_island[island2].begin())
                  {
                        it--;
                        ll dif = abs(i - *it);
                        if (dif < mindif) mindif = dif;
                  }
            }
      }
	return mindif;
}
 
inline ll Marge(int island1, int island2)
{
      ll cnt = 0;
      for (int i = 1; i < 100; i++)
      {
            if (weight[island1][i] or weight[island2][i]) cnt++;
      }
      return cnt;
}
 
struct node
{
	int u, v;
	ll engineer_pay, flyover_pay;
	node(int u = 0, int v = 0, ll engineer = 0, ll flyover = 0) : u(u), v(v), engineer_pay(engineer), flyover_pay(flyover) {}
	inline bool operator < (const node &p) const
	{
		if (engineer_pay == p.engineer_pay) return flyover_pay < p.flyover_pay;
		return engineer_pay < p.engineer_pay;
	}
};
 
vector <node> graph, temp_graph;
 
inline void makeGraph(int tisland)
{
	for (int i = 1; i <= tisland; i++)
	{
		for (int j = i+1; j <= tisland; j++)
		{
			ll flyover = getMinDifference(i, j);
			ll engineer = Marge(i, j);
			engineer *= engineer;
			graph.emplace_back(i, j, engineer, flyover);
		}
	}
}
 
int par[maxn];
 
inline void makeSet()
{
	for (int i = 0; i < maxn; i++) par[i] = i;
}
 
inline int findRep(int r)
{
	if (r == par[r]) return r;
	return par[r] = findRep(par[r]);
}
 
using pll = pair <ll, ll>;
 
inline pll kruskal(int tisland)
{
	makeSet();
	sort(graph.begin(), graph.end());
	ll engineer = -1e15;
	ll flyover = 0;
	int taken = 0;
	int i = 0;
	int len = graph.size();
	for ( ; i < len; i++)
	{
	    node e = graph[i];
		int p = findRep(e.u);
		int q = findRep(e.v);
		if (p != q)
		{
			par[q] = p;
			if (e.engineer_pay > engineer) engineer = e.engineer_pay;
			flyover += e.flyover_pay;
			taken++;
		}
		if (taken + 1 == tisland) break;
	}
	for ( ; i < len; i++)
      {
            node e = graph[i];
            if (e.engineer_pay > engineer) break;
      }
      for (int j = 0; j < i; j++)
      {
            node e = graph[j];
            temp_graph.emplace_back(e);
      }
      sort(temp_graph.begin(), temp_graph.end(), [](node a, node b)
           {
                 return a.flyover_pay < b.flyover_pay;
           });
      makeSet();
      flyover = 0;
      taken = 0;
      for (node e : temp_graph)
      {
            int p = findRep(e.u);
            int q = findRep(e.v);
            if (p != q)
            {
                  par[q] = p;
                  flyover += e.flyover_pay;
                  taken++;
            }
            if (taken + 1 == tisland) break;
      }
      return pll(engineer, flyover);
}
 
 
int main()
{
      //freopen("in.txt", "r", stdin);
 
      scanf("%d %d", &row, &column);
	for (int i = 1; i <= row; i++)
	{
		for (int j = 1; j <= column; j++)
		{
		      scanf("%lld", &grid[i][j]);
		}
	}
	int island = 0;
	for (int i = 1; i <= row; i++)
	{
		for (int j = 1; j <= column; j++)
		{
			if (vis[i][j] == false and grid[i][j] > 0)
			{
				island++;
				dfs(i, j, island);
				if (city_in_this_island[island] < 100)
                        {
                              city_in_this_island[island] = 0;
                              weight_in_a_island[island].clear();
                              memset(weight[island], 0, sizeof weight[island]);
                              island--;
                        }
			}
		}
	}
	if (island <= 1)
      {
            puts("0 0");
            return 0;
      }
	makeGraph(island);
	pll ans = kruskal(island);
	printf("%lld %lld\n", ans.first, ans.second);
}