Woburn Challenge 2018-19 Finals Round - Senior Division
Problem 5: Opening Weekend
At last, the time has come for months of hard work to finally pay off — the cows' and monkeys' production is hitting the big screen this weekend!
It will be playing at movie theatres in N (2 ≤ N ≤ 400,000) different cities, numbered from 1 to N in increasing order of their theatres' quality. There are N − 1 roads running amongst these cities, the i-th of which allows vehicles to drive in either direction between cities Ai and Bi (1 ≤ Ai, Bi ≤ N, Ai ≠ Bi). However, each road also passes through a tunnel which imposes a limit on the heights of vehicles which may drive along it — in particular, a vehicle may only travel along the i-th road if its height is at most Li cm (1 ≤ Li ≤ 109). It's possible for a 1cm-high vehicle (if such a thing exists) to travel from any city to any other city by following a sequence of roads.
There are K (1 ≤ K ≤ 400,000) moviegoers who have been waiting anxiously to see the film, with the i-th one living in city Ci (1 ≤ Ci ≤ N) and driving a vehicle with a height of Hi cm (1 ≤ Hi ≤ 109). However, they won't necessarily settle for watching the film in their own cities — they're prepared to drive wherever it takes to get the best possible movie-watching experience! However, they're also not great at planning ahead, so each moviegoer will follow this simple procedure:
- They'll consider both their current city and all cities they can directly reach from that city (by driving along a single road whose tunnel their vehicle can fit through), and find the one with the highest-quality movie theatre (the largest city number).
- If that largest-numbered city is their current city, they'll stop to watch the film there.
- Otherwise, they'll drive to that largest-numbered city, and repeat the procedure from Step 1.
The Head Monkey and Bo Vine want to make sure that each theatre has enough seats available for its screening — nobody should be left out from witnessing their masterpiece! In order to help estimate audience sizes, determine which city each of the K moviegoers will end up stopping at to watch the film.
In test cases worth 5/34 of the points, N ≤ 2000 and K ≤ 2000.
In test cases worth another 12/34 of the points, each city has at most two roads directly adjacent to it.
The first line of input consists of two space-separated integers, N and K.
N − 1 lines follow, the i-th of which consists of three space-separated integers, Ai, Bi, and Li, for i = 1..(N − 1).
K lines follow, the i-th of which consists of two space-separated integers, Ci and Hi, for i = 1..K.
Output K lines, the i-th of which should consist of a single integer, the city at which moviegoer i will stop to watch the film, for i = 1..K
3 3 1 2 10 3 1 5 1 4 2 1 1 10
3 2 2
The first moviegoer will drive from city 1 to city 3 and then remain there.
The second moviegoer will remain at city 2.
The third moviegoer will drive from city 1 to city 2 and then remain there.
Point Value: 20 (partial)
Time Limit: 8.00s
Memory Limit: 256M
Added: May 18, 2019
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3