HackerRank Clues on a Binary Path problem solution

In this HackerRank Clues on a Binary Path problem solution we have given a map of Neptune, help Logan and Veronica find and print the number of different paths of length D from house number 1 to the other houses in Neptune.

Problem solution in Java.

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

public class Solution {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);

        int n = in.nextInt();
        int m = in.nextInt();
        int d = in.nextInt();

        if (
                !(1 <= n && n <= 70) ||
                !(0 <= m && m <= n * (n - 1)) ||
                !(1 <= d && d <= 20))
            throw new RuntimeException();

        int[] x = new int[m];
        int[] y = new int[m];
        int[] w = new int[m];

        for (int i = 0; i < m; ++i) {
            x[i] = in.nextInt(); x[i]--;
            y[i] = in.nextInt(); y[i]--;
            if (!(0 <= x[i] && x[i] < n) || !(0 <= y[i] && y[i] < n))
                throw new RuntimeException();
            w[i] = in.nextInt();
            if (!(0 <= w[i] && w[i] <= 1))
                throw new RuntimeException();
        }

        int l = (d + 1) / 2;

        int[][] dp =  new int[n][1 << l];
        int[][] ndp = new int[n][1 << l];

        for (int i = 0; i < n; ++i)
            for (int j = 0; j < (1 << l); ++j)
                dp[i][j] = ndp[i][j] = 0;

        dp[0][0] = 1;
        for (int i = 0; i < n; ++i)
            dp[i][0] |= 2;

        for (int c = 0; c < l; ++c) {
            for (int i = 0; i < m; ++i) {
                int u = x[i];
                int v = y[i];
                int b = w[i];

                for (int t = 0; t < (1 << c); ++t) {
                    ndp[u][(t << 1) | b] |= dp[v][t];
                    ndp[v][(t << 1) | b] |= dp[u][t];
                }
            }

            if (c + 1 < l) {
                for (int i = 0; i < n; ++i) {
                    for (int j = 0; j < (1 << (c + 1)); ++j) {
                        dp[i][j] = ndp[i][j];
                        ndp[i][j] = 0;
                    }
                }
            }
        }

        Boolean[] can = new Boolean[1 << d];
        for (int i = 0; i < (1 << d); ++i)
            can[i] = false;

        int r = d - l;
        for (int v = 0; v < n; ++v) {
            for (int t = 0; t < (1 << r); ++t) {
                int c = (l == r ? ndp[v][t] : dp[v][t]);
                if ((c & 1) == 0)
                    continue;
                for (int s = 0; s < (1 << l); ++s) {
                    if ((ndp[v][s] & 2) > 0)
                        can[(t << l) ^ s] = true;
                }
            }
        }

        int res = 0;
        for (int i = 0; i < (1 << d); ++i)
            if (can[i])
                res++;

        out.println(res);
        out.close();
    }
}

class InputReader {
    private final BufferedReader reader;
    private StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }

    public String nextLine() {
        try {
            return reader.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(nextLine());
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

}

Problem solution in C++.

#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
  
using namespace std;
   
#define pb push_back
#define mp make_pair
#define F first
#define S second

const int N = 99;
const int L = 13;

int n, m, l;
bool used[(1 << 20) + 100];
bool canMake[N][(1 << 10) + 100];
bool f[N][N][L][(1 << 10) + 100];
vector< pair<int, int> > g[N];

int main() {
    scanf("%d%d%d", &n, &m, &l);
    for (int i = 1; i <= m; i++) {
        int u, v, c;
        scanf("%d%d%d", &u, &v, &c);
        g[u].pb(mp(v, c));
        g[v].pb(mp(u, c));
    }
    queue<int> q_start, q_ver, q_len, q_mask;
    for (int i = 1; i <= n; i++) {
        f[i][i][0][0] = true;
        q_start.push(i);
        q_ver.push(i);
        q_len.push(0);
        q_mask.push(0);
    }
    int maxMoves = (l + 1) / 2;
    while (!q_start.empty()) {
        int start = q_start.front();
        int ver = q_ver.front();
        int len = q_len.front();
        int mask = q_mask.front();
        q_start.pop(); q_ver.pop(); q_len.pop(); q_mask.pop();
        if (len == maxMoves) {
            continue;
        }
        for (int i = 0; i < (int)g[ver].size(); i++) {
            int to = g[ver][i].F;
            int bit = g[ver][i].S;
            int newMask = mask;
            if (bit == 1) {
                newMask += (1 << len);
            }
            if (f[start][to][len + 1][newMask] == false) {
                f[start][to][len + 1][newMask] = true;
                q_start.push(start);
                q_ver.push(to);
                q_len.push(len + 1);
                q_mask.push(newMask);
            }
        }
    }
    int maxMask = (1 << maxMoves);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int mask = 0; mask < maxMask; mask++) {
                if (f[i][j][maxMoves][mask]) {
                    canMake[j][mask] = true;
                }
            }
        }
    }
    int lengthOfFirstPart = l - maxMoves;
    int maxMask2 = (1 << lengthOfFirstPart);
    for (int ver = 1; ver <= n; ver++) {
        for (int m1 = 0; m1 < maxMask2; m1++) {
            if (f[1][ver][lengthOfFirstPart][m1]) {
                for (int m2 = 0; m2 < maxMask; m2++) {
                    if (canMake[ver][m2]) {
                        used[(m1 << maxMoves) + m2] = true;
                    }
                }
            }
        }
    }
    int ans = 0;
    int maxMaskOverall = (1 << l);
    for (int i = 0; i < maxMaskOverall; i++) {
        if (used[i]) {
            ++ans;
        }
    }
    printf("%d\n", ans);
    return 0;
}