HackerRank Roads in HackerLand problem solution

In this HackerRank Roads in HackerLand problem solution we have given a map of HackerLand and we need to find the sum of the minimum distance between each pair of cities and we need to print the answer in binary representation.

Problem solution in Python.

#!/bin/python3

p = list(range(10 ** 5))

def dsu_get(v):
    if p[v] != v: p[v] = dsu_get(p[v])
    
    return p[v]

def dsu_merge(u, v):
    u = dsu_get(u)
    v = dsu_get(v)
    p[u] = v
    
    return u != v

n, m = map(int, input().split())
e = []
for i in range(m):
    a, b, c = map(int, input().split())
    e += [(c, b - 1, a - 1)]

e.sort()

G = [[] for x in range(n)]
for c, a, b in e:
    if dsu_merge(a, b):
        G[a] += [(b, c)]
        G[b] += [(a, c)]

f = [0] * m
def dfs(v, par = -1):
    sz = 1
    for u, c in G[v]:
        if u == par: continue
        
        y = dfs(u, v)
        
        f[c] = y * (n - y)
        sz += y
    
    return sz

dfs(0)

ans = 0
for x in f[::-1]:
    ans *= 2
    ans += x

print(bin(ans)[2:])

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {
  public static class Edge {
    public int node1, node2, power;
    long count;

    public Edge(int node1, int node2, int power) {
      this.node1 = node1;
      this.node2 = node2;
      this.power = power;
    }
  }

  public static class Node {
    public int id;

    public ArrayList<Edge> edges;

    public Node(int id) {
      this.id = id;
      edges = new ArrayList<>();
    }
  }

  static long[] results;
  static int N, M;
  static Node[] nodes;

  // disjoint set implementation
  static int[] forests;

  static int find(int node) {
    if (forests[node] < 0) return node;
    return forests[node] = find(forests[node]);
  }

  static void join(int root1, int root2) {
    if (forests[root2] < forests[root1]) forests[root1] = root2;
    else {
      if (forests[root1] == forests[root2]) forests[root1]--;
      forests[root2] = root1;
    }
  }

  // count edge uses
  static int descend(Node parent, Node node) {
    int total = 1;

    for (Edge edge : node.edges) {
      if (parent != null && (edge.node1 == parent.id || edge.node2 == parent.id)) continue;

      Node target;

      if (edge.node1 == node.id) target = nodes[edge.node2];
      else target = nodes[edge.node1];

      edge.count = descend(node, target);

      total += edge.count;
    }

    return total;
  }

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    N = scanner.nextInt();
    M = scanner.nextInt();

    Edge[] edges = new Edge[M];

    results = new long[2 * M];

    nodes = new Node[N];
    for (int n = 0; n < N; n++) nodes[n] = new Node(n);

    for (int m = 0; m < M; m++) {
      int node1 = scanner.nextInt() - 1;
      int node2 = scanner.nextInt() - 1;
      int power = scanner.nextInt();
      edges[power] = new Edge(node1, node2, power);
    }

    ArrayList<Edge> bucket = new ArrayList<>();

    // build MST
    forests = new int[N];
    Arrays.fill(forests, -1);

    for (int m = 0; m < M; m++) {
      int n1 = edges[m].node1, n2 = edges[m].node2;
      if (find(n1) != find(n2)) {
        join(find(n1), find(n2));

        nodes[n1].edges.add(edges[m]);
        nodes[n2].edges.add(edges[m]);

        bucket.add(edges[m]);
      }
    }

    // calculate distances
    Node root = nodes[bucket.get(0).node1];

    descend(null, root);

    for (Edge edge : bucket) results[edge.power] = edge.count * (N - edge.count);

    // binary output
    long carry;
    long nm;

    long[] buffer = new long[2 * M];

    for (int i = 0; i < 2 * M; i++) {
      nm = results[i];
      int j = 0;
      while (nm != 0) {
        buffer[i + j] += nm % 2;
        nm /= 2;
        j++;
      }
    }

    carry = 0;
    Arrays.fill(results, 0);
    for (int i = 0; i < 2 * M; i++) {
      results[i] = (buffer[i] + carry) % 2;
      carry = (buffer[i] + carry) / 2;
    }

    boolean init = false;
    for (int i = 2 * M - 1; i >= 0; i--) {
      if (results[i] == 0 && init) System.out.print(0);
      else if (results[i] == 1) {
        System.out.print(1);
        init = true;
      }
    }
  }
}

Problem solution in C++.

#include <bits/stdc++.h>

using namespace std;

template<class T> inline T sqr(const T& a) {
  return a * a;
}

template<class T> inline int len(const T &c) {
  return static_cast<int>(c.size());
}

template<class T> inline void maximize(T &r, const T c) {
  r = max(r, c);
}

template<class T> inline void minimize(T &r, const T c) {
  r = min(r, c);
}

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

const ld EPS = 1e-9;
const ld PI = 2 * acos(0.0);
const int N = 100100;

struct DSU {
  int size;
  vector<int> p;
  vector<int> w;

  DSU(int n) :
    size(n),
    p(n, -1),
    w(n, 1) {}

  int Parent(int v) {
    if (p[v] == -1)
      return v;
    return p[v] = Parent(p[v]);
  }

  void Union(int u, int v) {
    u = Parent(u);
    v = Parent(v);
    if (w[u] < w[v])
      swap(u, v);
    p[v] = u;
    w[u] += w[v];
  }
};

vector<pt> g[N];
vector<pt> tree[N];
li total;
int subt[N];
vector<li> ans;

int Dfs(int v, int prev, int w) {
  subt[v] = 1;
  for (pt &e : tree[v]) {
    if (e.first == prev)
      continue;
    subt[v] += Dfs(e.first, v, e.second);
  }
  if (w >= 0) {
    li used = (total - subt[v]) * subt[v];
    while (w >= len(ans)) {
      ans.push_back(0);
    }
    ans[w] += used;
  }
  return subt[v];
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  total = n;
  vector<pair<int, pt>> edges;
  for (int i = 0; i < m; ++i) {
    int x, y, w;
    scanf("%d%d%d", &x, &y, &w);
    --x, --y;
    edges.push_back({w, {x, y}});
    g[x].push_back({y, w});
    g[y].push_back({x, w});  
  }
  sort(edges.begin(), edges.end());

  DSU dsu(n);
  for (auto &e : edges) {
    int x = e.second.first;
    int y = e.second.second;
    int u = dsu.Parent(x);
    int v = dsu.Parent(y);
    if (u != v) {
      tree[x].push_back({y, e.first});
      tree[y].push_back({x, e.first});
      dsu.Union(u, v);
    }
  }

  Dfs(0, -1, -1);

  li r = 0;
  for (int i = 0; i < len(ans) || r; ++i) {
    while (i >= len(ans)) {
      ans.push_back(0);
    }
    r += ans[i];
    ans[i] = r & 1;
    r >>= 1;
  }
  bool started = false;
  for (int i = len(ans) - 1; i >= 0; --i) {
    bool on = ans[i] > 0;
    if (on) {
      started = true;
    }
    if (started) {
      putchar(on ? '1' : '0');
    }
  }
  if (!started) {
    puts("0");
  } else {
    puts("");
  }
  return 0;
}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <malloc.h>

typedef struct _node{
 int vertex;
    int weight;
 struct _node * next;
}node;

typedef node * pnode;

pnode AL[200005];
int hsh[100005];
long long int ans[200105];

void insert(pnode *A,int v,int w){
 pnode p=(pnode)malloc(sizeof(node));
 p->vertex=v;
    p->weight=w;
 p->next=*A;
 *A=p;
 return;
}

int find(int i){
    if(hsh[i]==i)return i;
    hsh[i]=find(hsh[i]);
    return hsh[i];
}

int check(int i,int j){
    int hi=find(i),hj=find(j);
    if(hi==hj)return 0;
    if(hj<hi)hsh[hi]=hj;
    else hsh[hj]=hi;
    return 1;
}

int dfs(int i,int pre,int n){
    pnode p=AL[i];
    int count=1;
    int temp;
    while(p!=NULL){
        if(p->vertex!=pre){
            temp=dfs(p->vertex,i,n);
            ans[p->weight]=(long long int)(n-temp)*(long long int)temp;
            count+=temp;
        }
        p=p->next;
    }
    return count;
}

int main() {
    int n,m,edge[200005][2],i,j,k,u,v,w,mx;
    long long int longj;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++){
        scanf("%d%d%d",&u,&v,&w);
        edge[w][0]=u-1;
        edge[w][1]=v-1;
    }
    for(i=0;i<n;i++)hsh[i]=i;
    for(i=0;i<n;i++)AL[i]=NULL;
    for(i=j=0;i<m&&j<n-1;i++){
        if(check(edge[i][0],edge[i][1])){
            insert(&AL[edge[i][0]],edge[i][1],i);
            insert(&AL[edge[i][1]],edge[i][0],i);
            j++;
        }
    }
    k=dfs(0,-1,n);
    mx=m;
    for(i=0;i<mx;i++){
        longj=ans[i];
        ans[i]=0;
        k=0;
        while(longj>0){
            ans[i+k]+=longj%2;
            k++;
            longj/=2;
            if(mx<i+k)mx=i+k;
        }
    }
    i=mx;
    while(i>0&&ans[i]==0)i--;
    for(;i>=0;i--)printf("%lld",ans[i]);
    return 0;
}