Roads in HackerLand – ASOCIATIA „INVESTESTE PENTRU VIITORUL TAU” BUZAU

Cerinta completa

John lives in HackerLand, a country with cities and bidirectional roads. Each of the roads has a distinct length, and each length is a power of two (i.e., raised to some exponent). It’s possible for John to reach any city from any other city.

Given a map of HackerLand, can you help John determine the sum of the minimum distances between each pair of cities? Print your answer in binary representation.

Input Format

The first line contains two space-seperated integers denoting (the number of cities) and (the number of roads), respectively.
Each line of the subsequent lines contains the respective values of , , and as three space-separated integers. These values define a bidirectional road between cities and having length .

Constraints

,
If , then .

Output Format

Find the sum of minimum distances of each pair of cities and print the answer in binary representation.

Sample Input

Sample Output

Explanation

In the sample, the country looks like this:

Let be the minimum distance between city and city .

Limbajul de programare folosit: java8

Cod:

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

public class Solution {
    private static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        FastScanner(InputStream is) {
            this.in = is;
        }

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);
            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }
            int val = 0;
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = read();
            }
            return val * sign;
        }
    }

    private static class DSU {
        int[] p;
        int[] r;

        DSU(int n) {
            p = new int[n];
            r = new int[n];
            for (int i = 0; i < n; i++) p[i] = i;
        }

        int find(int x) {
            while (p[x] != x) {
                p[x] = p[p[x]];
                x = p[x];
            }
            return x;
        }

        boolean union(int a, int b) {
            int ra = find(a), rb = find(b);
            if (ra == rb) return false;
            if (r[ra] < r[rb]) {
                int t = ra;
                ra = rb;
                rb = t;
            }
            p[rb] = ra;
            if (r[ra] == r[rb]) r[ra]++;
            return true;
        }
    }

    private static class Edge {
        int u, v, w;

        Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
    }

    private static class Adj {
        int to, w;

        Adj(int to, int w) {
            this.to = to;
            this.w = w;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt();
        int m = fs.nextInt();

        Edge[] edges = new Edge[m];
        int maxW = 0;
        for (int i = 0; i < m; i++) {
            int u = fs.nextInt() - 1;
            int v = fs.nextInt() - 1;
            int w = fs.nextInt();
            edges[i] = new Edge(u, v, w);
            if (w > maxW) maxW = w;
        }

        Arrays.sort(edges, Comparator.comparingInt(e -> e.w));

        @SuppressWarnings("unchecked")
        ArrayList<Adj>[] g = new ArrayList[n];
        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();

        DSU dsu = new DSU(n);
        int used = 0;
        for (Edge e : edges) {
            if (dsu.union(e.u, e.v)) {
                g[e.u].add(new Adj(e.v, e.w));
                g[e.v].add(new Adj(e.u, e.w));
                used++;
                if (used == n - 1) break;
            }
        }

        int[] parent = new int[n];
        int[] parentW = new int[n];
        Arrays.fill(parent, -1);

        int[] order = new int[n];
        int ordSz = 0;
        int[] stack = new int[n];
        int top = 0;
        stack[top++] = 0;
        parent[0] = 0;

        while (top > 0) {
            int u = stack[--top];
            order[ordSz++] = u;
            for (Adj ad : g[u]) {
                int v = ad.to;
                if (parent[v] != -1) continue;
                parent[v] = u;
                parentW[v] = ad.w;
                stack[top++] = v;
            }
        }

        long[] sub = new long[n];
        Arrays.fill(sub, 1L);

        int bits = maxW + 80;
        long[] cnt = new long[Math.max(bits, 128)];

        for (int i = n - 1; i >= 1; i--) {
            int u = order[i];
            int p = parent[u];
            long s = sub[u];
            sub[p] += s;

            int w = parentW[u];
            if (w >= cnt.length) {
                cnt = Arrays.copyOf(cnt, w + 80);
            }
            cnt[w] += s * (n - s);
        }

        for (int i = 0; i + 1 < cnt.length; i++) {
            if (cnt[i] >= 2) {
                cnt[i + 1] += cnt[i] >> 1;
                cnt[i] &= 1L;
            }
        }

        int hi = cnt.length - 1;
        while (hi > 0 && cnt[hi] == 0) hi--;

        StringBuilder out = new StringBuilder();
        for (int i = hi; i >= 0; i--) out.append(cnt[i]);
        System.out.println(out);
    }
}

Scor obtinut: 1.0

Submission ID: 464614498

Link challenge: https://www.hackerrank.com/challenges/johnland/problem

Roads in HackerLand