Shortest Route SHROUTE SOLUTION

by

Shortest Route SHROUTE

There are N cities in Chefland numbered from 1 to N and every city has a railway station. Some cities have a train and each city has at most one train originating from it. The trains are represented by an array A, where Ai=0 means the i-th city doesn’t have any train originating from it, Ai=1 means the train originating from the i-th city is moving right (to a higher numbered city), and Ai=2 means the train originating from the i-th city is moving left (to a lower numbered city).

Each train keeps on going forever in its direction and takes 1 minute to travel from the current station to the next one. There is a special station at city 1 which lets travellers instantaneously teleport to any other station that currently has a train. Teleportation and getting on a train once in the city both take 0 minutes and all trains start at time 0.

There are M travellers at city 1, and the i-th traveller has destination city Bi. They ask Chef to guide them to teleport to a particular station from which they can catch a train to go to their destination in the least time possible. In case it’s not possible for a person to reach his destination, print −1.

Note: The input and output of this problem are large, so prefer using fast input/output methods.

Input
The first line contains an integer T, the number of test cases. Then the test cases follow.
Each test case contains three lines of input.
The first line contains two integers N, M.
The second line contains N integers A1,A2,…,AN.
The third line contains M integers B1,B2,…,BM.
Output
For each test case, output M space-separated integers C1,C2,…,CM, where Ci is the minimum time required by the i-th traveller to reach his destination and if the i-th traveller can’t reach his destination, Ci=−1.

Constraints
1≤N,M≤105
0≤Ai≤2
1≤Bi≤N
The sum of N over all test cases is at most 106.
The sum of M over all test cases is at most 106.
Subtasks
Subtask #1 (100 points): original constraints

Sample Input
3
5 1
1 0 0 0 0
5
5 1
1 0 0 0 2
4
5 2
2 0 0 0 1
3 1
Sample Output
4
1
-1 0
Explanation
Test Case 1: The only person takes the train from station 1 and hence takes |5−1|=4 minutes to reach his destination.

Test Case 2: The only person takes the train from station 5 and hence takes |5−4|=1 minute to reach his destination.

Test Case 3: Since no train passes station 3, it’s impossible for the first person to reach his destination and since the second person is already at station 1, it takes him 0 minutes to reach his destination.

Program:

N=int((input()))
for it in range(N):
    n,m=map(int,input().split())
    st=list(map(int,input().split()))
    des=list(map(int,input().split()))
    dp={}
    maxx=1000000007
    for i1 in range(n):
        if(i1==0):
            dp[i1]=0
        elif(st[i1]!=0):
            dp[i1]=0
        else:
            dp[i1]=maxx
    
    #right
    rit=-1     
    for i in range(n):  
        if(st[i]==1):
            rit=i
        if(rit!=-1):
            if(st[i]==0):
                dp[i]=min(dp[i],abs(i-rit))
        
        
    #left
    left=-1
    for i in range(n-1,-1,-1):  
        if(st[i]==2):
            left=i
        if(left!=-1):
            if(st[i]==0):
                dp[i]=min(dp[i],abs(left-i))
                 
            
    for i in range(m):
        o=des[i]-1
        if(dp[o]!=maxx):
            print(dp[o],end=" ")
        else:
            print(-1,end=" ")
    print()

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

RELATED :

Related :

Related :