DMOPC '17 Contest 2 P3 - Bad Bunnies

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Carrots fear one thing, and one thing alone: bad bunnies.

A lost carrot has found themselves in a unweighted graph with N nodes inside bad bunny territory. The carrot knows a little graph theory and recognizes that this graph is a tree! Currently, they are at node X and needs to get to node Y to escape. However, there are R rabbits, the i^{\text{th}} of which is on node R_i of the graph. Help this carrot figure out the closest they will ever have to be to a rabbit during their escape.


For all test cases, 1 \le R \le N, 1 \le a, b, X, Y, r \le N.

Subtask 1 [20%]

1 \le N \le 1\,000

Subtask 2 [80%]

1 \le N \le 200\,000

Input Specification

The first line of input will contain 2 integers, N, and R.
The next N-1 lines of input will contain 2 integers each, a, b, indicating there exists an edge between a and b
The next R lines of input will each contain a single integer, r, indicating that there is a rabbit at r.
The final line of input will contain two integers, X and Y.

Output Specification

A single integer, the closest the carrot will ever get to a rabbit on the path from node X to Y.

Sample Input

5 1
1 2
1 3
3 4
4 5
2 4

Sample Output



  • -2
    m4m3sh1b4  commented on April 22, 2018, 9:43 p.m.

    What happens when the rabbit is on the escape?