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;
}
