Problem Brief

Compute Number of Locations

You are trying to purchase a car and will be visiting a number of locations N (represented as points), each labeled i (1 ≤ i ≤ N). There are M roads connecting the points together, and road j (1 ≤ j ≤ M) of length d_j bidirectionally connects points u_j and v_j.

The car comes with a fuel tank that has a capacity of L, moving 1 unit of distance for every 1 unit of fuel it expends.

Some of the points have a gas station. g_i = 1 if there is a gas station at point i, and g_i = 0 if there is no gas station. If you reach a point with a gas station without running out of fuel you are able to fill up your car's tank. (If you run out of fuel just as you reach a point with a gas station, you can still fill up.) If you run out of gas before reaching a gas station then you have no option but to call a tow truck to transport your vehicle.

You reside at location 1, which has a gas station. Your challenge is to create a program that computes the number of locations you can visit without running out of fuel. You must also return home at the end of the journey. You are free to take whichever path you like in order to reach a destination and to refuel at any particular gas station however many times you like.

Function Description

Complete the function computeNumberOfLocations in the editor.

computeNumberOfLocations has the following parameters:

1. N: an integer, the number of locations
2. M: an integer, the number of roads
3. L: an integer, the fuel tank capacity
4. int g[N]: an array of integers indicating the presence of gas stations
5. int roads[M][2]: a 2D array of integers where each element is a pair of integers representing a road

Returns

int: the number of locations you can visit without running out of fuel

1Example 1

Input

N = 99, M = 999, L = 9999, g = [9, 99, 999, 9999, 99999, 999999], roads = [[9], [99]]

Output

999

Explanation

Hallo ~ Test case example is missing in the source I could find. I made up one so that the system does not complain...Even the test case is missing, the problem satement and constraints should give us a pretty clear overview on what they are aking for. Wishing you the very best luck on acing every intervew steps forward!

Constraints

Limits and guarantees your solution can rely on.

1 ≤ N, M ≤ 100000, integer
1 ≤ L ≤ 10^9, integer
g_i is 0 or 1 (1 ≤ i ≤ N) -> g_i = 1 indicates that there is a gas station at point i;;; -> g_i = 0 indicates that there is NOT a gas station at point i
u_j ≤ v_j + 1 (1 ≤ j ≤ M - 1), integer
1 ≤ u_j < v_j ≤ N (1 ≤ j ≤ M), integer
1 ≤ d_j ≤ 10^6 (1 ≤ j ≤ M), integer
Every point is accessible from point 1.
[Single Gas station & Line Case] (accounts for 18% of cases) -> Roads are on a straight line. put differently: M = N - 1, u_j = j, v_j = j + 1 (1 <= j <= M);;; -> The only gas station is located at point 1. g₂ = 0, ..., g_N = 0
[Multi Gas stations & Line Case] (accounts for 18% of cases) -> Roads are on a straight line. M = N -1, u_j = j, v_j = j + 1 (1 <= j <= M)