USACO 2020 January Contest, Platinum
Problem 3. Falling Portals
Contest has ended.
Log in to allow submissions in analysis mode
At any time when two worlds are at the same $y$-coordinate (possibly a fractional time), the portals "align", meaning that a cow on one of the worlds can choose to travel instantaneously to the other world.
For each $i$, the cow on world $i$ wants to travel to world $Q_i$ ($Q_i\neq i$). Help each cow determine how long her journey will take, if she travels optimally.
Each query output should be a fraction $a/b$ where $a$ and $b$ are positive and relatively prime integers, or $-1$ if it the journey is impossible.
SCORING:
- Test cases 2-3 satisfy $N\le 100.$
- Test cases 4-5 satisfy $N\le 2000.$
- Test cases 6-14 satisfy no additional constraints.
INPUT FORMAT (file falling.in):
The first line of input contains a single integer $N.$The next line contains $N$ space-separated integers $A_1,A_2,\ldots,A_N.$
The next line contains $N$ space-separated integers $Q_1,Q_2,\ldots,Q_N.$
OUTPUT FORMAT (file falling.out):
Print $N$ lines, the $i$-th of which contains the journey length for cow $i.$SAMPLE INPUT:
4 3 5 10 2 3 3 2 1
SAMPLE OUTPUT:
7/2 7/2 5/1 -1
Consider the answer for the cow originally on world 2. At time $2$ worlds 1 and 2 align, so the cow can travel to world 1. At time $\frac{7}{2}$ worlds 1 and 3 align, so the cow can travel to world 3.
Problem credits: Dhruv Rohatgi