TRAVELER - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

You just simply need to do what is asked in the problem statement. Any adequate way is possible. Even the following naive solution will pass. Let’s store cities in simple array of strings and roads in array of triples (string, string, integer). You even don’t need to sort these arrays. For each route check at first whether all cities are correct by simple search of each name in the list of cities, then check whether they all are different by pair-wise comparison of all cities in the route. Finally search each pair of consecutive cities in the route in the list of all roads and add its length to the answer if it was found. This algorithm has complexity O(T * K * L * (N + K + M)) where L = 20 is the bound for the length of names.
Now we discuss the optimal solution. Again let’s store cities in simple array of strings but we sort them. Now for each road we find by binary search the indices of cities in this array and write its length in adjacent matrix. Then for each route we check correctness of the names again by binary search and use the boolean array of used cities in order to check whether they all are different. Finally we check the existence of the road by simple looking in the adjacent matrix. This solution has complexity O((N + M + T * K) * L * log N).
Feel the difference :slight_smile:

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.