TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P6559
  • 問題
  • P6559【USACO 2020 Jan Platinum】Falling Portals
    制限 : 時間制限 : - MS   メモリ制限 : - KB
    審判説明 : 1s,512m
    問題説明

    \(N\)($2\le N\le 2\cdot 10^5$)个世界,每个世界有一个传送门。初始时,世界 \(i\)(对于 $1 \leq i \leq N$)位于 \(x\) 坐标 \(i\)\(y\) 坐标 \(A_i\)\(1\le A_i\le 10^9\) )。每个世界里还有一头奶牛。在时刻 $0$,所有的 \(y\) 坐标各不相同,然后这些世界开始坠落:世界 \(i\) 沿着 \(y\) 轴负方向以 \(i\) 单位每秒的速度移动。

    在任意时刻,如果两个世界在某一时刻 $y$ 坐标相同(可能是非整数时刻),传送门之间就会“同步”,使得其中一个世界的奶牛可以选择瞬间传送到另一个世界。

    对于每一个 $i$,在世界 $i$ 的奶牛想要去往世界 $Q_i$($Q_i\neq i$)。帮助每头奶牛求出如果她以最优方案移动需要多少时间。

    每个询问的输出是一个分数 $a/b$,其中 $a$ 和 $b$ 为互质的正整数,或者 $-1$,如果不可能到达。

    测试点性质:

    • 测试点 2-3 满足 $N\le 100$。
    • 测试点 4-5 满足 $N\le 2000$。
    • 测试点 6-14 没有额外限制。

    入力形式

    输入格式(文件名:falling.in):

    输入的第一行包含一个整数 $N$。

    下一行包含 $N$ 个空格分隔的整数 $A_1,A_2,\ldots,A_N$。

    下一行包含 $N$ 个空格分隔的整数 $Q_1,Q_2,\ldots,Q_N$。

    出力形式

    输出格式(文件名:falling.out):

    输出 $N$ 行,第 $i$ 行包含奶牛 $i$ 的旅程的时间。
    サンプル入力

    4
    3 5 10 2
    3 3 2 1

    サンプル出力

    7/2
    7/2
    5/1
    -1
    考虑原先在世界 2 的奶牛的答案。在时刻 2 世界 1 和世界 2 同步,所以奶牛可以前往世界 1。在时刻 7/2 世界 1 和世界 3 同步,所以奶牛可以前往世界 3。