FoxMeeting
2015 TCO 2A · 2015-04-08 · by praveen123
Problem Statement
Foxland is a country with n cities.
The cities are numbered 1 through n.
The road network in Foxland is a tree.
You are given the description of the roads: three
There are some foxes in Foxland.
Each fox lives in a different city.
You are given a
The foxes are running a secret candy-smuggling network. Recently they have been harrassed by a new strict police officer: cat Taro. In order to avoid him, the foxes have now learned to communicate by waving their tails at each other. However, two foxes can only communicate in this way if they see each other. More precisely, they must either both be in the same city, or they have to be in two adjacent cities. (Adjacent cities are cities directly connected by a road, regardless of the road's length.)
Foxes can forward messages to other foxes, which makes communication transitive: If fox x can talk to fox y and fox y can talk to fox z, fox x will be able to communicate with fox z as well.
In order to avoid Taro, each fox must be able to talk to all other foxes (either directly or indirectly). If it isn't possible in their current configuration, some foxes may be forced to move into different cities. The foxes think that it is also suspicious if a fox moves too far from its current home. Therefore, they want to minimize the maximum distance traveled by any fox.
Formally, find and return the smallest integer D with the following property: It is possible to relocate some (possibly zero, possibly all) of the foxes into new cities in such a way that:
- For each fox, the total total distance traveled by that fox is at most D.
- After the relocation, all foxes can communicate (either directly or indirectly).
Constraints
- n will be between 1 and 50, inclusive.
- A, B, and L will contain exactly n-1 elements each.
- Each element in A and B will be between 1 and n, inclusive.
- Each element in L will be between 1 and 100,000, inclusive.
- A, B, and L will define a tree.
- Number of elements in foxes will be between 1 and n, inclusive.
- Each element in foxes will be between 1 and n, inclusive.
- All the elements of foxes are distinct.
{1}
{2}
{5}
{1, 2}
Returns: 0
There are two cities connected by a single road of length 5. There are two foxes: one in each city. As they are in adjacent cities, they can already communicate so no relocation is necessary.
{1, 2}
{2, 3}
{1, 1}
{1, 3}
Returns: 1
This country has three cities and two roads: 1-2 (length 1) and 2-3 (length 1). Initially, there is one fox in city 1 and another fox in city 3. In one optimal solution, the first fox will move from city 1 to city 2. In another optimal solution, both foxes will move from their respective cities to city 2. In each of the solutions described above we have D = 1.
{1, 2}
{2, 3}
{1, 1}
{1, 2, 3}
Returns: 0
No relocation is necessary, all foxes can already talk to each other.
{10,8,3,7,2,6,9,1,4}
{5,5,8,10,5,5,6,10,3}
{71846,10951,42265,37832,29439,95676,83661,28186,21216}
{1,2,3,4,5,6,7,8,9,10}
Returns: 0
{8,15,22,24,2,25,13,26,18,4,9,29,1,12,3,16,14,21,19,27,17,7,20,10,30,11,6,5,23}
{28,28,8,8,28,28,25,2,13,24,24,22,22,29,4,22,8,4,1,24,21,14,18,16,13,21,14,1,25}
{79374,40629,43195,73589,24200,63937,35339,7598,65109,51764,11142,84017,51078,58051,81387,22035,34883,92710,52283,57337,79309,3383,41904,35839,38242,43208,82062,24676,71838}
{3,5,7,9,10,14,17,19,20,21,24,25,28}
Returns: 107013
Submissions are judged against all 183 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FoxMeeting with a public method int maxDistance(vector<int> A, vector<int> B, vector<int> L, vector<int> foxes) · 183 test cases · 2 s / 256 MB per case