Our task concerns a city with N roads connecting N + 1 junctions numbered from 0 to N. Roads connect junctions in such a way that each distinct pair of junctions is connected either by a direct road or through a path consisting of direct roads. There is exactly one way to reach any junction from any other junction.
There is an office next to junction 0 and a house next to every other junction. One person lives in each house. All the citizens work in the office and use a car to travel from their houses to the office. Each car has five seats and consumes 1 liter of fuel to move by one road (from one junction to a neighboring junction).
The citizens want to set up a carpool scheme that allows them all to travel to the office in a way that minimizes the total consumption of fuel. People can change cars at each house and then continue to travel together. Calculate the fuel consumption in the optimal scheme.
The network of cities is described using arrays A and B, each of length N. Each pair A[K] B[K] for 0 <= K < N specifies a road connecting junctions number A[K] and B[K]
Write a function:
int solution (vector<int> &A, vector<int> &B);
that, given non-empty arrays A and B of length N describing a road network in the city, returns the minimum fuel consumption for the optimal carpool scheme.
Example 1 :
- Given A = [0, 1, 1] and B = [1, 2, 3].
Output : there are N = 3 houses. The function should return 3, as the optimal carpool scheme uses 3 liters of fuel:
• Citizen 2 goes in his car from his house to house 1.
• Citizen 3 goes in her car from her house to house 1.
• Citizens 2 and 3 go with citizen 1 in his car to the office.
Example 2 :
- Given A = [1, 1, 1, 9, 9, 9, 9, 7, 8] and B = [2, 0, 3, 1, 6, 5, 4, 0, 0].
Output : There are N = 9 houses. The function should return 10, as the following carpool scheme is optimal:
• Citizens 7 and 8 go directly to the office in their cars (using 2 liters of fuel).
• Citizens 4, 5, and 6 go in their cars to house 9 (they use 3 liters of fuel) and then they go with citizen 9 in her car to house 1 (for another 1 liter).
• Citizens 2 and 3 go in their cars to house 1 (for 2 liters of fuel).
• Now 7 citizens are at house 1, so they need to use at least two cars to move to the office (for another 2 liters of fuel).
Constraints :
Write an efficient algorithm for the following assumptions:
1. N is an integer with in range [1, 1e5]
2. Each element of arrays A & B is an integer within the range [0, N]
3. There is exactly one (possibly Indirect) connection between any two distinct junctions. All solutions are welcome