# HackerEarth IOI 2050 problem solution

In this HackerEarth IOI 2050 problem solution This is year 2050 and your school is hosting IOI 2050 this time. To organize the contest a lot of LAN cables will be laid down. N students from different countries will be coming to earn the prize of IOI winner. You are being asked to come up with a plan such that LAN utilization is minimized and all computers are connected to each other diretly or undirectly. LAN will be laid to connect these N computers. You will be given information about which computer to be connected to which and distance between them.
After you have come up with a plan you will be asked M queries of the form u,v for which you have to tell the minimum length of LAN used connect computers u and v according to your plan.

## HackerEarth IOI 2050 problem solution.

`#include<bits/stdc++.h>using namespace std;#define ll  long long intstruct node{  int src,dest;  ll wght;};int par[1005],rnk[1005];int Find(int nd){  if(par[nd]!=nd)    par[nd]=Find(par[nd]);  return par[nd];}void Union(int nd1, int nd2){  int x=Find(nd1);  int y=Find(nd2);  if(rnk[x]<rnk[y])    par[x]=y;  else if(rnk[x]>rnk[y])    par[y]=x;  else  {    par[y]=x;    rnk[x]++;  }}bool compare(node n1, node n2){  return n1.wght<n2.wght;}vector<node> mst;void kruskal(vector<node> g, int n){  for(int i=0;i<n;++i)  {    par[i]=i;    rnk[i]=0;  }  sort(g.begin(),g.end(),compare);  int cnt=0,cnt1=0;  while(cnt!=n-1)  {    node ne=g[cnt1++];    int x=Find(ne.src);    int y=Find(ne.dest);    if(x!=y)    {      mst.push_back(ne);      Union(x,y);      cnt++;    }  }}ll ans[1005][1005],wt[1005][1005];vector<int> adj[1005];bool visited[1005];/*...............Using DFS........................*/void dfs(int nd, int src){  visited[nd]=true;  for(int i=0;i<adj[nd].size();++i)  {    if(!visited[adj[nd][i]])    {      if(src==adj[nd][i])        ans[src][adj[nd][i]]=0;      else        ans[src][adj[nd][i]]=(ans[src][nd]+wt[nd][adj[nd][i]]);      dfs(adj[nd][i],src);    }  }}/*...............Using BFS........................*/void bfs(int nd, int src){  queue<int> q;  q.push(nd);  while(!q.empty())  {    int id=q.front();    q.pop();    if(visited[id])      continue;    visited[id]=true;    for(int i=0;i<adj[id].size();++i)    {      if(!visited[adj[id][i]])      {        if(src==adj[id][i])          ans[src][adj[id][i]]=0;        else          ans[src][adj[id][i]]=(ans[src][id]+wt[id][adj[id][i]]);        q.push(adj[id][i]);      }    }  }}int main(){  int t;  scanf("%d",&t);  int z=0;  while(t--)  {    ++z;    printf("Case: %d\n",z);    mst.clear();    int n,p,m;    scanf("%d %d %d",&n,&p,&m);    vector<node> graph;    node nd;    for(int i=0;i<p;++i)    {      scanf("%d %d %lld",&nd.src,&nd.dest,&nd.wght);      nd.src--;      nd.dest--;      graph.push_back(nd);    }    kruskal(graph,n);    for(int i=0;i<n;++i)    {      for(int j=0;j<n;++j)      {        ans[i][j]=0;        wt[i][j]=-1;      }      adj[i].clear();    }    int mst_size=mst.size();    for(int i=0;i<mst_size;++i)    {      wt[mst[i].src][mst[i].dest]=mst[i].wght;      wt[mst[i].dest][mst[i].src]=mst[i].wght;      adj[mst[i].src].push_back(mst[i].dest);      adj[mst[i].dest].push_back(mst[i].src);    }    for(int i=0;i<n;++i)    {      memset(visited,false,sizeof(visited));      /*Call any of the bfs or dfs*/      //dfs(i,i);      //bfs(i,i);    }    for(int i=0;i<m;++i)    {      int x,y;      scanf("%d %d",&x,&y);      x--;      y--;      printf("%lld\n",ans[x][y]);    }  }  return 0;}`

### Second solution

`#include <bits/stdc++.h>using namespace std;int sz[1005];int id[1005];bool visited[1005];int D[1005][1005]; // D(i,j) represent cst between node i and jint C[1005][1005];vector <vector<int> > MST(1005);vector <pair<int,pair<int,int> > > Connections;void UF(int N){    for(int i=0; i<N; i++){        id[i] = i;        sz[i] = 1;    }    for(int i=0;i<1005;i++){            for(int j=0;j<1005;j++){                D[i][j]=0;                C[i][j]=0;            }    }}// Return the id of component corresponding to object p.int find(int p){    int root = p;    while (root != id[root])        root = id[root];    while (p != root) {        int newp = id[p];        id[p] = root;        p = newp;    }    return root;}// Replace sets containing x and y with their union.void merge(int x, int y){    int i = find(x);    int j = find(y);    if (i == j) return;    // make smaller root point to larger one    if   (sz[i] < sz[j]){        id[i] = j;        sz[j] += sz[i];    }    else{        id[j] = i;        sz[i] += sz[j];    }}void MinimumSpanningTree(){  //Sort Vector Connections with respect to cost  sort(Connections.begin(),Connections.end());    for(int i=0;i<Connections.size();i++)    {        int Src=Connections[i].second.first,Dest=Connections[i].second.second,Cost=Connections[i].first;        if(find(Src)!=find(Dest))        {            //union of Src and Dest subtree            merge(Src,Dest);            MST[Src].push_back(Dest);            MST[Dest].push_back(Src);            C[Src][Dest]=Cost;            C[Dest][Src]=Cost;        }    }}void Recursion(int Src,int Dest){    if((!visited[Dest]))    {        visited[Dest]=true;        for(int i=0;i<MST[Dest].size();i++)        {            int NDest=MST[Dest][i];            if(!D[Src][NDest]){                if(Src==NDest)                    D[Src][NDest]=0;                else                    D[Src][NDest]=D[Src][Dest]+C[Dest][NDest];            }            Recursion(Src,NDest);        }    }}void CalculateCost(int N){    for(int i=0;i<N;i++)    {        memset(visited,false,sizeof(visited));        Recursion(i,i);    }}int main(){  int test,K=1;  scanf("%d",&test);  assert(test>0 && test<=50);  while(test--)  {    int N,P,Queries,Cost,Src,Dest,A,B;    scanf("%d %d %d",&N,&P,&Queries);    assert(N>=1 && N<=1000);    assert(P>=N-1 && P<=100000);    assert(Queries>=1 && Queries<=100000);    for(int i=0;i<P;i++)    {      scanf("%d %d %d",&Src,&Dest,&Cost);      assert(Src>=1 && Src<=N);      assert(Dest>=1 && Dest<=N);      assert(Cost>=1 && Cost<=1000000);      Connections.push_back(make_pair(Cost,make_pair(Src-1,Dest-1)));    }    UF(N);    MinimumSpanningTree();        CalculateCost(N);        for(int i=0;i<N;++i)        {        MST[i].clear();        }        //MST.clear() causes runtime error        Connections.clear();        printf("Case: %d\n",K++);        for(int i=0;i<Queries;i++)        {            scanf("%d %d",&A,&B);            printf("%d\n",D[A-1][B-1]);        }  }  return 0;}`