HackerRank Longest Mod Path Problem Solution

HackerRank Longest Mod Path Problem Solution

Yashwant Parihar,

In this post, we will solve HackerRank Longest Mod Path Problem Solution.

In the middle of a nightmare, Maxine suddenly finds herself in a mysterious room with the following items:

  1. A piece of paper with the word score and the integer 0 written on it.
  2. A map of the castle where the room is located.
  3. There are N rooms uniquely labeled from 1 to N.
  4. There are N bidirectional corridors connecting pairs of rooms. The value of score changes every time she travels up or down a corridor, and this value differs depending on her direction of travel along the corridor. Each corridor can be traveled any number of times in either direction.
  5. Every room is reachable from every other room.
  • Maxine is located in the room labeled S.
    The exit is located in the room labeled E. Once this room is reached, score is reduced modulo M and Maxine can (but is not required to) exit that level!
    Assume some corridor i (where 1 <i<N) is associated with an integer,,, and connects rooms a; and b. Then:
  • Traveling corridor & from room a, to room b, increases score by ;.
  • Traveling corridor i from room b, to room a, decreases score by .

There are Q levels to Maxine’s nightmare castle, and each one has a different set of values
for S. E. and M. Given the above information, help Maxine by finding and printing her
maximum possible score for each level. Only you can help her wake up from this nightmare!
Note: Recall that the result of a modulo operation is always non-negative. For example,
(-8) mod 5 = 2.

Input Format
The first line contains a single integer, N, denoting the number of rooms.
Each of the N subsequent lines describes a corridor in the form of three space-separated integers denoting the respective values for a, b, and
The next line contains a single integer, Q. denoting the number of queries.
Each of the Q subsequent lines describes a level in the form of three space-separated integers denoting its respective S. E. and M values.

Output Format

For each of the Q levels, print the maximum possible score for that level on a new line.

Sample Input

3
1 3 5
2 3 8
2 1 31
1
1 2 13

Sample Output

12
HackerRank Longest Mod Path Problem Solution
HackerRank Longest Mod Path Problem Solution

Longest Mod Path C Solution

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define HASH_SIZE 123455
#define INF 1000000007
typedef struct _node{
  int x;
  int y;
  int w;
  struct _node *next;
} node;
typedef struct _lnode{
  int x;
  int w;
  struct _lnode *next;
} lnode;
void insert_edge(int x,int y,int w);
void dfs0(int x,int y);
void dfs1(int x);
void get_loop(int x,int y);
long long CC(long long n, long long d);
void insert(int x,int y,int w);
int search(int x,int y);
lnode *table[100000]={0};
node *hash[HASH_SIZE]={0};
int loop[100000]={0},trace[100000]={0},point[100000];
int first_point,breakp=0,cycle_found=0;
long long cycle=0,dis[100000]={0},cycle_save;

int main(){
  int N,a,b,x,S,E,M,Q,MOD,DIS,GCD,ans,i;
  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d%d%d",&a,&b,&x);
    insert_edge(a-1,b-1,x);
    if(a>b)
      Q=search(b-1,a-1);
    else
      Q=search(a-1,b-1);
    if(Q==INF)
      if(a>b)
        insert(b-1,a-1,-x);
      else
        insert(a-1,b-1,x);
    else{
      if(a>b)
        cycle=x+Q;
      else
        cycle=x-Q;
      cycle_found=1;
      cycle_save=cycle;
    }
  }
  dfs0(0,-1);
  if(!loop[0])
    point[0]=first_point;
  memset(trace,0,sizeof(trace));
  dfs1(0);
  if(cycle_found)
    cycle=cycle_save;
  scanf("%d",&Q);
  while(Q--){
    scanf("%d%d%d",&S,&E,&M);
    MOD=(cycle%M+M)%M;
    DIS=((dis[E-1]-dis[S-1])%M+M)%M;
    if(!MOD)
      ans=DIS;
    else{
      GCD=CC(MOD,M);
      ans=(M-1-DIS)/GCD*GCD+DIS;
    }
    printf("%d\n",ans);
  }
  return 0;
}
void insert_edge(int x,int y,int w){
  lnode *t=malloc(sizeof(lnode));
  t->x=y;
  t->w=w;
  t->next=table[x];
  table[x]=t;
  t=malloc(sizeof(lnode));
  t->x=x;
  t->w=-w;
  t->next=table[y];
  table[y]=t;
  return;
}
void dfs0(int x,int y){
  lnode *p;
  trace[x]=1;
  for(p=table[x];p;p=p->next)
    if(!trace[p->x]){
      dis[p->x]=dis[x]+p->w;
      dfs0(p->x,x);
    }
    else if(p->x!=y && !loop[p->x]){
      first_point=p->x;
      get_loop(p->x,-1);
      cycle+=p->w;
    }
  return;
}
void dfs1(int x){
  lnode *p;
  trace[x]=1;
  if(loop[x])
    point[x]=x;
  for(p=table[x];p;p=p->next)
    if(!trace[p->x]){
      if(!loop[p->x])
        point[p->x]=point[x];
      dfs1(p->x);
    }
  return;
}
void get_loop(int x,int y){
  lnode *p;
  loop[x]=1;
  for(p=table[x];p && !breakp;p=p->next)
    if(trace[p->x] && !loop[p->x]){
      cycle+=p->w;
      get_loop(p->x,x);
      if(!breakp)
        cycle-=p->w;
    }
    else if(p->x==first_point && p->x!=y){
      breakp=1;
      break;
    }
  return;
}
long long CC(long long n, long long d){
    while( 1 )
    {
        n = n % d;
        if( n == 0 )
                return d;
        d = d % n;
        if( d == 0 )
                return n;
    }
}
void insert(int x,int y,int w){
  int bucket=(x*100000LL+y)%HASH_SIZE;
  node *t;
  t=(node*)malloc(sizeof(node));
  t->x=x;
  t->y=y;
  t->w=w;
  t->next=hash[bucket];
  hash[bucket]=t;
  return;
}
int search(int x,int y){
  int bucket=(x*100000LL+y)%HASH_SIZE;
  node *t=hash[bucket];
  while(t){
    if(t->x==x && t->y==y)
      return t->w;
    t=t->next;
  }
  return INF;
}

Longest Mod Path C++ Solution

#include <cstdio>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <ctime>
#include <cstring>
#include <cassert>
#include <bitset>
#include <sstream>
#include <queue>

#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define sz(a) ((int) (a).size())
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

typedef long long int64;
typedef long double ldb;

const long double eps = 1e-9;
const int inf = (1 << 30) - 1;
const long long inf64 = ((long long)1 << 62) - 1;
const long double pi = acos(-1);

template <class T> T sqr (T x) {return x * x;}
template <class T> T abs (T x) {return x < 0 ? -x : x;}

const int MAXN = 120 * 1000;

vector <pair <int, int> > adj[MAXN];
long long a[MAXN];
bool used[MAXN];
long long cycle = 0;

void dfs(int v, long long num) {
    a[v] = num;
    used[v] = true;
    for (int i = 0; i < sz(adj[v]); ++i) {
        int u = adj[v][i].fs;
        if (!used[u]) {
            dfs(u, num + adj[v][i].sc);
        } else if (a[v] + adj[v][i].sc - a[u] != 0) {
            cycle = a[v] + adj[v][i].sc - a[u];
        }
    }
}

int gcd(int a, int b) {
    return (a == 0 ? b : gcd(b % a, a));
}

int main () {

    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int v1, v2, c;
        scanf("%d%d%d", &v1, &v2, &c);
        v1--, v2--;
        adj[v1].pb(mp(v2, c));
        adj[v2].pb(mp(v1, -c));
    }

    dfs(0, 0);
    
    int q;
    scanf("%d", &q);
    for (int i = 0; i < q; ++i) {
        int s, e, m;
        scanf("%d%d%d", &s, &e, &m);
        s--, e--;
        
        int val = ((a[e] - a[s]) % m + m) % m;
        int cycle_val = (cycle % m  + m) % m;
        
        int d = gcd(cycle_val, m);

        int res = (val % d) + m - d;
        printf("%d\n", res);
    }

    return 0;
}

Longest Mod Path C Sharp Solution

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

class Solution {

    /*
     * Complete the longestModPath function below.
     */
    static int[] longestModPath(int[][] corridor, int[][] queries)
    {
        PathGraph pg = new PathGraph(corridor.Length);
        pg.ProcessRays(corridor);
        pg.ProcessCycle(corridor);
        pg.PrepareQuery();
        int[] result = new int[queries.Length];
        for (int i = 0; i < queries.Length; i++)
        {
            result[i] = pg.Query(queries[i][0] - 1, queries[i][1] - 1, queries[i][2]);
        }
        return result;
    }

    class PathGraph
    {
        public PathGraph(int n)
        {
            this.n = n;
        }

        public void ProcessRays(int[][] corridor)
        {
            roomConnect = new int[n];
            connectToRoom = new int[n];
            connectToScore = new int[n];
            for (int i = 0; i < corridor.Length; i++)
            {
                int s = corridor[i][0] - 1;
                int c = ++roomConnect[s];
                if (c == 1)
                    connectToRoom[s] = i;
                else if (c == 2)
                    connectToScore[s] = i;

                int e = corridor[i][1] - 1;
                c = ++roomConnect[e];
                if (c == 1)
                    connectToRoom[e] = i;
                else
                    connectToScore[e] = i;
            }
            corridorProcessed = new bool[n];
            roomProcessed = new bool[n];
            //for (int i = 0; i < connectToRoom.Length; i++)
            //    connectToRoom[i] = -1;
            while (true)
            {
                bool rayEdgeFound = false;
                for (int i = 0; i < roomConnect.Length; i++)
                {
                    if (roomConnect[i] == 1 && !roomProcessed[i])
                    {
                        rayEdgeFound = true;
                        int corr = connectToRoom[i];
                        int j = i;
                        while (corr >= 0)
                        {
                            if (corridorProcessed[corr])
                                throw new ArgumentException();
                            roomProcessed[j] = true;
                            corridorProcessed[corr] = true;
                            int s = corridor[corr][0] - 1;
                            int e = corridor[corr][1] - 1;
                            if (j == s)
                            {
                                if (roomConnect[e] <= 1)
                                    throw new ArgumentException();
                                connectToRoom[s] = e;
                                connectToScore[s] = corridor[corr][2];
                                //DumpEdge(s, e, corridor[corr][2]);
                                j = e;
                            }
                            else
                            {
                                if (j != e)
                                    throw new ArgumentException();
                                if (roomConnect[s] <= 1)
                                    throw new ArgumentException();
                                connectToRoom[e] = s;
                                connectToScore[e] = -corridor[corr][2];
                                //DumpEdge(e, s, -corridor[corr][2]);
                                j = s;
                            }
                            if (--roomConnect[j] == 1)
                            {
                                corr = (connectToRoom[j] != corr) ? connectToRoom[j] : connectToScore[j];
                            }
                            else
                            {
                                connectToRoom[j] = -1;
                                connectToScore[j] = -1;
                                break;
                            }
                        }
                    }
                }
                if (!rayEdgeFound)
                    break;
                for (int i = 0; i < corridor.Length; i++)
                {
                    if (!corridorProcessed[i])
                    {
                        int s = corridor[i][0] - 1;
                        if (roomConnect[s] == 2)
                        {
                            if (connectToRoom[s] < 0)
                                connectToRoom[s] = i;
                            else
                                connectToScore[s] = i;
                        }
                        else if (roomConnect[s] == 1 && !roomProcessed[s])
                            connectToRoom[s] = i;

                        int e = corridor[i][1] - 1;
                        if (roomConnect[e] == 2)
                        {
                            if (connectToRoom[e] < 0)
                                connectToRoom[e] = i;
                            else
                                connectToScore[e] = i;
                        }
                        else if (roomConnect[e] == 1 && !roomProcessed[e])
                            connectToRoom[e] = i;
                    }
                }
            }
        }

        public void ProcessCycle(int[][] corridor)
        {
            cycleScore = 0;
            cycleLength = 0;
            for (int i = 0; i < roomConnect.Length; i++)
            {
                if (roomConnect[i] > 1)
                {
                    cycleRef = i;
                    int cs = i;
                    do
                    {
                        int corr = connectToRoom[cs];
                        if (corridorProcessed[corr])
                            corr = connectToScore[cs];
                        if (corridorProcessed[corr])
                            throw new ArgumentException();
                        corridorProcessed[corr] = true;
                        int s = corridor[corr][0] - 1;
                        int e = corridor[corr][1] - 1;
                        if (cs == s)
                        {
                            AddCycleEdge(s, e, corridor[corr][2]);
                            cs = e;
                        }
                        else
                        {
                            if (cs != e)
                                throw new ArgumentException();
                            AddCycleEdge(e, s, -corridor[corr][2]);
                            cs = s;
                        }
                    } while (cs != i);
                    break;
                }
            }
        }

        public void PrepareQuery()
        {
            roomScoreToCycle = new long[n];
            for (int i = 0; i < roomScoreToCycle.Length; i++)
                roomScoreToCycle[i] = long.MinValue;
            roomCycleEntry = new int[n];
            roomChainStack = new int[n];
        }

        public int Query(int S, int E, int M)
        {
            long R = CalculateRoomScoreToCycle(S, out S) - CalculateRoomScoreToCycle(E, out E);
            R += CalculateRoomScoreToCycleRef(S);
            R -= CalculateRoomScoreToCycleRef(E);
            return MaximizeScore((int)(R % M), (int)(cycleScore % M), M);
        }

        readonly int n;
        bool[] corridorProcessed;
        bool[] roomProcessed;
        int[] roomConnect;
        int[] connectToRoom;
        int[] connectToScore;
        long cycleScore;
        int cycleLength;
        int cycleRef;

        long[] roomScoreToCycle;
        int[] roomCycleEntry;
        int[] roomChainStack;

        void AddCycleEdge(int s, int e, int score)
        {
            connectToRoom[s] = e;
            connectToScore[s] = score;
            cycleScore += score;
            //DumpEdge(s, e, score);
            if (++cycleLength > n)
                throw new ArgumentException();
        }

        long CalculateRoomScoreToCycle(int s, out int cycleEntryRoom)
        {
            int sp = 0;
            long score = 0;
            int cycleEntry = -1;
            while (roomConnect[s] == 1)
            {
                if (roomScoreToCycle[s] != long.MinValue)
                {
                    score = roomScoreToCycle[s];
                    cycleEntry = roomCycleEntry[s];
                    break;
                }
                roomChainStack[sp++] = s;
                s = connectToRoom[s];
            }
            if (cycleEntry < 0)
                cycleEntry = s;
            while (sp > 0)
            {
                s = roomChainStack[--sp];
                score += connectToScore[s];
                roomScoreToCycle[s] = score;
                roomCycleEntry[s] = cycleEntry;
            }
            cycleEntryRoom = cycleEntry;
            return score;
        }

        long CalculateRoomScoreToCycleRef(int s)
        {
            int sp = 0;
            long score = 0;
            while (s != cycleRef)
            {
                if (roomScoreToCycle[s] != long.MinValue)
                {
                    score = roomScoreToCycle[s];
                    break;
                }
                roomChainStack[sp++] = s;
                s = connectToRoom[s];
            }
            while (sp > 0)
            {
                s = roomChainStack[--sp];
                score += connectToScore[s];
                roomScoreToCycle[s] = score;
            }
            return score;
        }
    }

    //static void DumpEdge(int s, int e, int score)
    //{
    //    Console.Write(s + 1);
    //    Console.Write(' ');
    //    Console.Write(e + 1);
    //    Console.Write(' ');
    //    Console.WriteLine(score);
    //}
    
    static int MaximizeScore(int r, int c, int M)
    {
        if (r < 0)
            r += M;
        if (c < 0)
            c += M;
        if (c == 0)
            return r;
        int gcd = CalculateGcd(c, M);
        return r + ((M - 1 - r) / gcd) * gcd;
    }
    
    static int CalculateGcd(int x, int y)
    {
        while (true)
        {
            if (x > y)
            {
                int t = x;
                x = y;
                y = t;
            }
            y = y % x;
            if (y == 0)
                return x;
        }
    }

    static void Main(string[] args) {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        int n = Convert.ToInt32(Console.ReadLine());

        int[][] corridor = new int[n][];

        for (int corridorRowItr = 0; corridorRowItr < n; corridorRowItr++) {
            corridor[corridorRowItr] = Array.ConvertAll(Console.ReadLine().Split(' '), corridorTemp => Convert.ToInt32(corridorTemp));
        }

        int q = Convert.ToInt32(Console.ReadLine());

        int[][] queries = new int[q][];

        for (int queriesRowItr = 0; queriesRowItr < q; queriesRowItr++) {
            queries[queriesRowItr] = Array.ConvertAll(Console.ReadLine().Split(' '), queriesTemp => Convert.ToInt32(queriesTemp));
        }

        int[] result = longestModPath(corridor, queries);

        textWriter.WriteLine(string.Join("\n", result));

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

Longest Mod Path Java Solution

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

    /*
     * Complete the longestModPath function below.
     */
     static long gcd(long a, long b){
        if(b == 0)
            return a;
        return gcd(b, a%b);
     }
    static int[] longestModPath(int[][] corridor, int[][] queries) {
        /*
         * Write your code here.
         */
        HashMap<Integer,HashMap<Integer,Integer>> adj = new HashMap<Integer,HashMap<Integer,Integer>>();
        HashMap<Integer,long[]> toCycle = new HashMap<Integer,long[]>();
        HashMap<Integer,long[]> cycle = new HashMap<Integer,long[]>();
        HashSet<Integer> leaf = new HashSet<Integer>();
        long cyclesum = 0;
        for(int i = 0; i < corridor.length; i++)
            adj.put(i, new HashMap<Integer,Integer>());
        for(int i = 0; i < corridor.length; i++){
            int temp1 = corridor[i][0]-1;
            int temp2 = corridor[i][1] - 1;
            if(adj.get(temp1).keySet().contains(temp2))
               cyclesum = Math.abs(adj.get(temp2).get(temp1) + corridor[i][2]);
            adj.get(temp1).put(temp2,corridor[i][2]);
            adj.get(temp2).put(temp1,-corridor[i][2]);
        }
        HashSet<Integer> used = new HashSet<Integer>();
        HashMap<Integer,Integer> parent = new HashMap<Integer,Integer>();
        Queue<Integer> stuff = new LinkedList<Integer>();
        stuff.add(0);
        used.add(0);
        long[] distances = new long[corridor.length];
        while(stuff.size() > 0){
            int temp = stuff.remove();
            for(int child: adj.get(temp).keySet()){
               if(used.contains(child) && parent.get(temp) != child)
                  cyclesum = distances[temp] - distances[child] + adj.get(temp).get(child);
               else if(!used.contains(child)){
                  stuff.add(child);
                  used.add(child);
                  distances[child] = distances[temp] + adj.get(temp).get(child);
                  parent.put(child,temp);
               }
            }
        }
        int[] answers = new int[queries.length];
        for(int i = 0; i < queries.length; i++){
            long k = gcd(cyclesum,(long)queries[i][2]);
            if(k == 1)
                answers[i] = queries[i][2]-1;
            else{
                int S = queries[i][0]-1;
                int E = queries[i][1]-1;
                int mod = queries[i][2];
                answers[i] = (int)((distances[E] - distances[S])%mod+mod)%mod;
                answers[i] = answers[i] + (int)((mod - answers[i]-1)/k*k);
            }
        }
        return answers;
    }
    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int n = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

        int[][] corridor = new int[n][3];

        for (int corridorRowItr = 0; corridorRowItr < n; corridorRowItr++) {
            String[] corridorRowItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

            for (int corridorColumnItr = 0; corridorColumnItr < 3; corridorColumnItr++) {
                int corridorItem = Integer.parseInt(corridorRowItems[corridorColumnItr]);
                corridor[corridorRowItr][corridorColumnItr] = corridorItem;
            }
        }

        int q = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

        int[][] queries = new int[q][3];

        for (int queriesRowItr = 0; queriesRowItr < q; queriesRowItr++) {
            String[] queriesRowItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

            for (int queriesColumnItr = 0; queriesColumnItr < 3; queriesColumnItr++) {
                int queriesItem = Integer.parseInt(queriesRowItems[queriesColumnItr]);
                queries[queriesRowItr][queriesColumnItr] = queriesItem;
            }
        }

        int[] result = longestModPath(corridor, queries);

        for (int resultItr = 0; resultItr < result.length; resultItr++) {
            bufferedWriter.write(String.valueOf(result[resultItr]));

            if (resultItr != result.length - 1) {
                bufferedWriter.write("\n");
            }
        }

        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}

Longest Mod Path JavaScript Solution

'use strict';

const fs = require('fs');

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

let inputString = '';
let currentLine = 0;

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

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

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

/*
 * Complete the 'longestModPath' function below.
 *
 * The function is expected to return an INTEGER_ARRAY.
 * The function accepts following parameters:
 *  1. 2D_INTEGER_ARRAY corridor
 *  2. 2D_INTEGER_ARRAY queries
 */

    function longestModPath(corridor, queries) {
    const loopSet = (val) => loop=GCD(loop, val)
    const roomSet = (x, val) => {if(room[x]!=null)loopSet(room[x]-val);else roomCount++;room[x]=val}
    const mapCorridor = (c,pos)=>({from:c[0],to:c[1],val:c[2],pos})
    const mapRodirroc = (c,pos)=>({from:c[1],to:c[0],val:-c[2],pos})
    const sortStack = (a,b)=>a.from-b.from||a.to-b.to||a.val-b.val
    const GCD = (A,B) => ((x,y)=>{const _gcd=(a,b)=>{let g;while(b){g=a%b;a=b;b=g;}return(a)};return((y>x)?_gcd(y,x):_gcd(x,y))})(Math.abs(A),Math.abs(B))
    let loop, nextPile
    let stack=corridor.map(mapCorridor).concat(corridor.map(mapRodirroc)).sort(sortStack)
    let pile=extract(1,0,1)
    let room=[null,0], roomCount=1
// Here I solve all the maze
    do {
        nextPile=[]
        pile.forEach(({from, to, val})=> {
            if (from==to) loopSet(val)
            else {
                roomSet(to, val + room[from])
                nextPile = nextPile.concat(extract(to))
            }
        })
        pile = nextPile
    } while (nextPile.length>0)
// Here I calculate all the queried results
    queries.forEach((q, i, a) =>{
        let m=q[0], n=q[1], mod=q[2], val, resp, looper = GCD(loop, mod)
        if (mod<=1) resp = 0
        else if (looper==1) resp = mod-1
        else {
            val = (m==n)?0:(room[n] - room[m])%looper
            resp = (mod - 1) - (mod - 1 - val) % looper
        }
        a[i] = resp
    })
    return queries
//Binary search function to get all corridors starting at "where"
    function extract(where, start = 0, end = null) {
        if ((end == null) || (end >= stack.length)) end = stack.length - 1
        if (start < 0) start = 0
        while (start < end) {
            let mid = Math.floor((start + end) / 2)
            let test = stack[mid]
            if (test.from == where) {
                let ini=mid, fin=mid, resp=[]
                if(corridor[test.pos]){
                    resp.push(test)
                    corridor[test.pos]=null
                }
                while((--ini>=0)&&(test=stack[ini]).from==where){
                    if(corridor[test.pos]){
                        resp.push(test)
                        corridor[test.pos]=null
                    }
                }
                while((++fin<stack.length)&&(test=stack[fin]).from==where){
                    if(corridor[test.pos]){
                        resp.push(test)
                        corridor[test.pos]=null
                    }
                }
                return resp
            } else if (where < test.from) end = mid - 1
            else start = mid + 1
        }
        return []
    }
}

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

    const n = parseInt(readLine().trim(), 10);

    let corridor = Array(n);

    for (let i = 0; i < n; i++) {
        corridor[i] = readLine().replace(/\s+$/g, '').split(' ').map(corridorTemp => parseInt(corridorTemp, 10));
    }

    const q = parseInt(readLine().trim(), 10);

    let queries = Array(q);

    for (let i = 0; i < q; i++) {
        queries[i] = readLine().replace(/\s+$/g, '').split(' ').map(queriesTemp => parseInt(queriesTemp, 10));
    }

    const result = longestModPath(corridor, queries);

    ws.write(result.join('\n') + '\n');

    ws.end();
}

Longest Mod Path Python Solution

#!/bin/python3

import math
import os
import random
import re
import sys
from math import gcd
#
# Complete the 'longestModPath' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts following parameters:
#  1. 2D_INTEGER_ARRAY corridor
#  2. 2D_INTEGER_ARRAY queries
#

n = eval(input())
adj = [[] for i in range(n)]
for i in range(n):
    a, b, c = list(map(int, input().strip().split()))
    a -= 1; b -= 1
    adj[a].append((b, c))
    adj[b].append((a, -c))

dist = [None]*n
parents = [set() for i in range(n)] # set because of special case: cycle of length 2
dist[0] = 0
stack = [0]
while stack:
    i = stack.pop()
    for j, c in adj[i]:
        if j in parents[i]: continue
        ndist = dist[i] + c
        parents[j].add(i)
        if dist[j] is None:
            dist[j] = ndist
            stack.append(j)
        else:
            cycle = abs(dist[j] - ndist)


for qq in range(eval(input())):
    s, e, m = list(map(int, input().strip().split()))
    a = gcd(cycle, m)
    print(m - a + (dist[e-1] - dist[s-1]) % a)
c C# C++ HackerRank Solutions java javascript python