HackerRank Roads in HackerLand Solution

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.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;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <ctype.h>
#include <deque>
#include <queue>
#include <cstring>
#include <set>
#include <list>
#include <map>
#include <random>
#include <unordered_map>
#include <stdio.h>

using namespace std;

typedef long long ll;
typedef std::vector<int> vi;
typedef std::vector<bool> vb;
typedef std::vector<string> vs;
typedef std::vector<double> vd;
typedef std::vector<long long> vll;
typedef std::vector<std::vector<int> > vvi;
typedef vector<vvi> vvvi;
typedef vector<vll> vvll;
typedef std::vector<std::pair<int, int> > vpi;
typedef vector<vpi> vvpi;
typedef std::pair<int, int> pi;
typedef std::pair<ll, ll> pll;
typedef std::vector<pll> vpll;

const long long mod = 1000000007;

#define all(c) (c).begin(),(c).end()
#define sz(c) (int)(c).size()
#define forn(i, a, b) for(int i = a; i < b; i++)

#define pb push_back
#define mp make_pair
const int MAXN = 100000;
vector<int> lst[MAXN];
int parent[MAXN];

void make_set (int v) {
    lst[v] = vector<int> (1, v);
    parent[v] = v;
}

int find_set (int v) {
    return parent[v];
}

void union_sets (int a, int b) {
    a = find_set (a);
    b = find_set (b);
    if (a != b) {
        if (lst[a].size() < lst[b].size())
            swap (a, b);
        while (!lst[b].empty()) {
            int v = lst[b].back();
            lst[b].pop_back();
            parent[v] = a;
            lst[a].push_back (v);
        }
        
    }
}

vvpi nb;
vi ans(200100, 0);
vi used;
int n,m;
int dfs(int v) {
    used[v] = 1;
    int ssz = 1;
    for(auto u : nb[v]) {
        if(used[u.first]) continue;
        
        ll st = dfs(u.first);
        ssz+=st;
        
        ll r = st * (n-st);
        int cur = u.second;
        while(r>0) {
            if(r%2) ans[cur]++;
            r/=2;
            if(ans[cur] == 2) {
                ans[cur]=0;
                r++;
            }
            cur++;
        }
        
    }
    return ssz;
}

int main()
{
    vector<pair<int, pi>> e;
    scanf("%d %d", &n,&m);
    forn(i,0,m) {
        int a,b,c;
        scanf("%d %d %d", &a, &b, &c);
        e.pb(mp(c, mp(a-1, b-1)));
    }
    nb.resize(n);
    forn(i,0,n) make_set(i);
    sort(all(e));
    
    for(auto u : e) {
        int a = u.second.first;
        int b = u.second.second;
        int x = find_set(a);
        int y = find_set(b);
        if(x==y) continue;
        int c = u.first;
        nb[a].pb(mp(b, c));
        nb[b].pb(mp(a, c));
        union_sets(a, b);

    }
    used=vi(n,0);
    dfs(0);
    while(ans.back()==0) ans.pop_back();
    reverse(all(ans));
    for(auto x:ans) printf("%d", x);
    
}

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Solution {

    /*
     * Complete the roadsInHackerland function below.
     */
    static string roadsInHackerland(int n, int[][] roads) {
        var dset = new int[n];
        var adj = new int[n][];
        var dist = new int[n][];
        for(int i = 0; i < dset.Length; i++)
            dset[i] = i;
        Array.Sort(roads, (r1, r2) => r1[2] - r2[2]);
        foreach(var r in roads) {
            int v1 = r[0] - 1;
            int v2 = r[1] - 1;
            int p1 = find(dset, v1);
            int p2 = find(dset, v2);
            if(p1 != p2) {
                dset[p2] = p1;
                append(ref adj[v1], v2);
                append(ref adj[v2], v1);
                append(ref dist[v1], r[2]);
                append(ref dist[v2], r[2]);
            }
        }
        var total = new List<long>();
        dfs(total, 0, -1, adj, dist);
        int pos = 0;
        while(pos < total.Count) {
            long t = total[pos]/2;
            total[pos] %= 2;
            add(total, pos + 1, t);
            pos++;
        }
        total.Reverse();
        return string.Join("", total);
    }

    static int dfs(List<long> total, int curr, int parent, int[][] adj, int[][] dist) {
        int cTotal = 1;
        for(int i = 0; i < adj[curr].Length; i++)
            if(adj[curr][i] != parent) {
                int cnt = dfs(total, adj[curr][i], curr, adj, dist);
                cTotal += cnt;
                add(total, dist[curr][i], cnt*(adj.Length - (long)cnt));
            }
        return cTotal;
    }
    
    static void add(List<long> sum, int pow, long cnt) {
        if(cnt > 0) {
            while(sum.Count <= pow)
                sum.Add(0);
            sum[pow] += cnt;
        }
    }
    
    static int find(int[] dset, int v) {
        while(dset[v] != v) {
            var next = dset[v];
            dset[v] = dset[next];
            v = next;
        }
        return v;
    }
    
    static void append(ref int[] arr, int v) {
        Array.Resize(ref arr, (arr?.Length ?? 0) + 1);
        arr[arr.Length - 1] = v;
    }
    
    static void Main(string[] args) {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        string[] nm = Console.ReadLine().Split(' ');

        int n = Convert.ToInt32(nm[0]);

        int m = Convert.ToInt32(nm[1]);

        int[][] roads = new int[m][];

        for (int roadsRowItr = 0; roadsRowItr < m; roadsRowItr++) {
            roads[roadsRowItr] = Array.ConvertAll(Console.ReadLine().Split(' '), roadsTemp => Convert.ToInt32(roadsTemp));
        }

        string result = roadsInHackerland(n, roads);

        textWriter.WriteLine(result);

        textWriter.Flush();
        textWriter.Close();
    }
}

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

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}


function roadsInHackerland(n, roads) {
    function calculateMST(roads) {
        function getRootArr(roads) {
            let rootArr = [], rootCountArr = [];
            for (let i = 1; i <= n; i++) {
                rootArr[i] = i;
                rootCountArr[i] = 1;
            }

            return [rootArr, rootCountArr];
        }

        function getRoot(rootArr, node) {
            while (node !== rootArr[node])
                node = rootArr[node];

            return node;
        }

        function setRoot(rootArr, node, root) {
            rootArr[node] = root;
        }

        let finalRoads = [], rootArr = getRootArr(roads)[0], rootCountArr = getRootArr(roads)[1];
        roads.sort((r1, r2) => r1[2] - r2[2]);
        for (let road of roads) {
            if (1 + finalRoads.length === n)
                break;

            let root0 = getRoot(rootArr, road[0]), root1 = getRoot(rootArr, road[1]);
            if (root0 !== root1) {
                finalRoads.push(road);
                if (rootCountArr[root1] < rootCountArr[root0]) {
                    setRoot(rootArr, root1, root0);
                    rootCountArr[root0] += rootCountArr[root1];
                }
                else {
                    setRoot(rootArr, root0, root1);
                    rootCountArr[root1] += rootCountArr[root0];
                }
            }
        }

        return finalRoads;
    }

    function calculateEdge2Count(mst) {
        function constructMstMap(mst) {
            function addToMap(map, node, nodeAndWeight) {
                let nodeAndWeightArr;
                if (map.has(node))
                    nodeAndWeightArr = map.get(node);
                else {
                    nodeAndWeightArr = [];
                    map.set(node, nodeAndWeightArr);
                }

                nodeAndWeightArr.push(nodeAndWeight);
            }

            let node2NodeWeight = new Map();
            for (let road of mst) {
                let node0 = road[0], node1 = road[1];
                addToMap(node2NodeWeight, node0, [node1, road[2]]);
                addToMap(node2NodeWeight, node1, [node0, road[2]])
            }

            return node2NodeWeight;
        }

        function dfs(node, edge2Count, visited) {
            let edges = node2NodeWeight.get(node).filter(nodeAndWeight => !visited.has(nodeAndWeight[0]));
            if (edges.length === 0)
                return 0;

            let childrenCount = 0;
            for (let road of edges) {
                let theOtherNode = road[0];
                visited.add(theOtherNode);
                let roadCount = dfs(theOtherNode, edge2Count, visited);
                roadCount++;   // count theOtherNode itself
                edge2Count.set(road, roadCount);
                childrenCount += roadCount;
            }

            return childrenCount;
        }

        let node = mst[0][0], edge2Count = new Map(), visited = new Set();
        visited.add(node);
        let node2NodeWeight = constructMstMap(mst);
        dfs(node, edge2Count, visited);

        return edge2Count;
    }

    let mst = calculateMST(roads), edge2Count = calculateEdge2Count(mst);
    const NODE_COUNT = mst.length + 1;
    let total = 0n;
    for (let kv of edge2Count) {
        let weight = kv[0][1], count = kv[1], times = count * (NODE_COUNT - count);
        total += (2n ** BigInt(weight)) * BigInt(times);
    }

    return total.toString(2);
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const nm = readLine().split(' ');

    const n = parseInt(nm[0], 10);

    const m = parseInt(nm[1], 10);

    let roads = Array(m);

    for (let roadsRowItr = 0; roadsRowItr < m; roadsRowItr++) {
        roads[roadsRowItr] = readLine().split(' ').map(roadsTemp => parseInt(roadsTemp, 10));
    }

    let result = roadsInHackerland(n, roads);

    ws.write(result + "\n");

    ws.end();
}

#!/bin/python3
"""
    https://www.hackerrank.com/challenges/johnland/problem
"""
import os
import sys
import heapq as hq
import time

def find_other(t, i):
    """
        given a tuple (a,b) and 'i' equal to one of them, it returns
        the other value. i.e. if i==a, return 'b' and vice-versa
    """
    if i == t[0]:
        return t[1]
    elif i == t[1]:
        return t[0]
    else:
        return None


#
# Complete the roadsInHackerland function below.
#
def roadsInHackerland(n, roads):
    #
    # Write your code here.
    #
    #base_time = time.time()
    ### largest cost in the resulting MST. used to size the list
    max_cost = 0
    
    ### MST edges. key is tuple (i,j); i<j.  value is the edge'cost',
    edges_cost = dict()
    
    ### list of edges in which the node is part has in the resulting MST
    ### first entry is the number of 'unsolved' edges for the node
    MST_neigh = [[0, []] for _ in range(n)]
    
    ### nodes already added to graph
    added = set([0]);
    
    ### working heap list of tuples (distance, i, j)
    ws = []
    for j,dist in roads[0].items():
        ws.append((dist, 0, j))
    hq.heapify(ws)
    #ws.sort(reverse=True)

    while len(added) < n:
        ### retrive the smallest egde
        #dist,a,b = hq.heappop(ws)
        dist,a,b = hq.heappop(ws)
        
        if a > b:
            a,b = b,a
        if not a in added:
            i = a
        elif not b in added:
            i = b
        else:
            continue

        ### 'na' and 'nb' are calculated later
        edges_cost[(a,b)] = dist
        if dist > max_cost:
            max_cost = dist
        added.add(i)
        MST_neigh[a][0] += 1
        MST_neigh[b][0] += 1
        MST_neigh[a][1].append((a,b))
        MST_neigh[b][1].append((a,b))
        
        for j,dist in roads[i].items():
            if not j in added:
                #ws.append((dist, i, j))
                hq.heappush(ws, (dist, i, j))
        #hq.heapify(ws)
        

    #print("done w/ MST:   ", time.time()-base_time)
    #base_time = time.time()    
    ### find the number of nodes in subtrees on both sides of each edge 
    ### start with nodes having 1 unsolved edge
    
    ### number of nodes in each subtree on both side of an egde
    ### key: (i,j);  value dictionary of {i:nodes, j:nodes}
    edges_nodes = dict()
    
    ### list of nodes to process -add all nodes with 1 unsolved edge
    ws = []
    for node, item in enumerate(MST_neigh):
        if item[0] == 1:
            ws.append((node,item))
    
    while len(ws) > 0:
        me, item = ws.pop(0)
        tmp = 1                 # keeps track of number of nodes
        unsolved = None         # store the 1 unsolved edge
        
        ### avoid processing the very last edge twice
        if item[0] < 1:
            continue
        
        for edge in item[1]:    # walk the edge list
            if edge in edges_nodes:     # already solved
                tmp += edges_nodes[edge][find_other(edge, me)]
            else:
                unsolved = edge

        peer_node = find_other(unsolved, me)    # the other end of unsolved edge
        ### add to number of nodes per edge dict.
        edges_nodes[unsolved] = {me:tmp, peer_node:(n-tmp)}

        ### decrement the number of unsolved nodes
        item[0] -= 1        # this should end up 0
        MST_neigh[peer_node][0] -= 1
        
        ### if the other node only has one unsolved edge, add it to list
        if MST_neigh[peer_node][0] == 1:
            ws.append((peer_node, MST_neigh[peer_node]))

#    for item in enumerate(MST_neigh):
#        print(item)
#    for item in edges_cost.items():
#        print(item)
#    for item in edges_nodes.items():
#        print(item)
    #print("done w/ tree:  ", time.time()-base_time)
    #base_time = time.time()
        
    ### create a list holding the bit for each position
    ### largest number of times using an edge is (n/2)^2.
    ### that is 25Mil, which fits in 25 bits (24.575)
    res = [0] * (max_cost+25)
    
    for edge,i in edges_cost.items():
        ### number a times an edge is traveresed
        count = 1
        for num in edges_nodes[edge].values():
            count *= num
        while count > 0:
            if count & 1:
                res[i] += 1
            count >>= 1
            i += 1
#    print(res)
    ### reduce result's list elements to binary
    max_bit_set = 0
    for i in range(len(res)):
        if res[i] > 1:
            res[i+1] += (res[i]>>1)
            res[i] &= 1
        if (res[i] == 1):
            max_bit_set = i
    
    res = res[:max_bit_set+1]
    res.reverse()
    
    #print("done w/ binary:", time.time()-base_time)
    
    return "".join([str(i) for i in res])

if __name__ == '__main__':
    n, m = [int(i) for i in input().strip().split()]

    #base_time = time.time()
    roads = [dict() for _ in range(n)]

    for _ in range(m):
        i, j, dist = list(map(int, input().rstrip().split()))
        i,j = i-1, j-1
        if (not j in roads[i]) or (roads[i][j] > dist):
            roads[i][j] = dist
            roads[j][i] = dist

    #print("done reading:  ", time.time()-base_time)
    print(roadsInHackerland(n, roads))