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 int
struct 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: %dn",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("%lldn",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 j
int 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: %dn",K++);
        for(int i=0;i<Queries;i++)
        {
            scanf("%d %d",&A,&B);
            printf("%dn",D[A-1][B-1]);
        }
  }
  return 0;
}

coding problems