C - Balls and Boxes Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 600 点

問題文

N 個の箱があります。 i = 1, 2, \ldots, N について、i 番目の箱には A_i 個の赤いボールと B_i 個の青いボールが入っています。

また、数列 (1, 2, \ldots, N) を並べ替えた 2 つの順列 P = (P_1, P_2, \ldots, P_N) と Q = (Q_1, Q_2, \ldots, Q_N) が与えられます。

高橋君は、下記の操作を好きな回数（ 0 回でも良い）だけ繰り返すことができます。

  • 1 \leq i \leq N を満たす整数 i を選び、i 番目の箱に入っているすべてのボールを箱から取り出して手に持つ。
  • 手に持っているすべての赤いボールを P_i 番目の箱に入れる。
  • 手に持っているすべての青いボールを Q_i 番目の箱に入れる。

高橋君の目標は、上記の操作の繰り返しによって、X 番目の箱以外にボールが入っていない状態にすることです。 この目標を達成することが可能かどうかを判定し、可能な場合はそのために行う操作回数の最小値を出力してください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq A_i, B_i \leq 1
  • 1 \leq P_i, Q_i \leq N
  • P,Q はそれぞれ (1, 2, \ldots, N) の順列
  • 1 \leq X \leq N
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N X
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
P_1 P_2 \ldots P_N
Q_1 Q_2 \ldots Q_N

出力

高橋君が X 番目の箱以外にボールが入っていない状態にすることが不可能な場合は -1 を、 可能な場合はそのために行う操作回数の最小値を出力せよ。

入力例 1

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

出力例 1

4

各箱に入っている赤いボールと青いボールの個数はそれぞれ A = (0, 1, 0, 1, 0), B = (0, 0, 1, 0, 1) で与えられています。 下記の手順を考えます。

  • まず、5 番目の箱に対して操作を行う。その結果、A = (0, 1, 0, 1, 0), B = (1, 0, 1, 0, 0) となる。
  • 次に、2 番目の箱に対して操作を行う。その結果、A = (1, 0, 0, 1, 0), B = (1, 0, 1, 0, 0) となる。
  • さらに、1 番目の箱に対して操作を行う。その結果、A = (0, 0, 0, 2, 0), B = (0, 0, 2, 0, 0) となる。
  • 最後に、4 番目の箱に対して操作を行う。その結果、A = (0, 0, 2, 0, 0), B = (0, 0, 2, 0, 0) となる。

上記の 4 回の操作によって、X = 3 番目の箱以外にボールが入っていない状態にすることができます。 これが考えられる最小の操作回数です。

入力例 2

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

出力例 2

0

どの箱にもボールが入っていません。 よって、はじめから X = 3 番目の箱以外にボールが入っていない状態であるので、必要な操作回数は 0 回です。

入力例 3

2 2
1 1
1 1
1 2
1 2

出力例 3

-1

どのような手順で操作を行っても、X = 2 番目の箱以外にボールが入っていない状態にすることはできません。

入力例 4

10 10
0 0 0 0 0 0 1 0 1 0
0 0 0 0 1 1 0 0 1 0
1 4 9 5 8 2 3 6 10 7
7 4 9 10 6 3 1 2 8 5

出力例 4

8

Score : 600 points

Problem Statement

There are N boxes. For i = 1, 2, \ldots, N, the i-th box contains A_i red balls and B_i blue balls.

You are also given two permutations P = (P_1, P_2, \ldots, P_N) and Q = (Q_1, Q_2, \ldots, Q_N) of (1, 2, \ldots, N).

Takahashi can repeat the following operation any number of times, possibly zero:

  • Choose an integer 1 \leq i \leq N, and take all the balls from the i-th box into his hand.
  • Put all the red balls in his hand into the P_i-th box.
  • Put all the blue balls in his hand into the Q_i-th box.

His goal is to make a state where all boxes other than the X-th box contain no balls by repeating the above operations. Determine whether it is possible to achieve his goal, and if possible, print the minimum number of operations needed to achieve it.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq A_i, B_i \leq 1
  • 1 \leq P_i, Q_i \leq N
  • P and Q are permutations of (1, 2, \ldots, N).
  • 1 \leq X \leq N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N X
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
P_1 P_2 \ldots P_N
Q_1 Q_2 \ldots Q_N

Output

If it is impossible for Takahashi to achieve a state where all boxes other than the X-th box contain no balls, print -1. If it is possible, print the minimum number of operations needed to achieve it.

Sample Input 1

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

Sample Output 1

4

The numbers of red and blue balls in each box are A = (0, 1, 0, 1, 0) and B = (0, 0, 1, 0, 1), respectively. Consider the following steps:

  • First, perform the operation on the 5th box. As a result, A = (0, 1, 0, 1, 0), B = (1, 0, 1, 0, 0).
  • Next, perform the operation on the 2nd box. As a result, A = (1, 0, 0, 1, 0), B = (1, 0, 1, 0, 0).
  • Then, perform the operation on the 1st box. As a result, A = (0, 0, 0, 2, 0), B = (0, 0, 2, 0, 0).
  • Finally, perform the operation on the 4th box. As a result, A = (0, 0, 2, 0, 0), B = (0, 0, 2, 0, 0).

These four operations achieve a state where all boxes other than the X-th (3rd) box contain no balls. This is the minimum number of operations possible.

Sample Input 2

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

Sample Output 2

0

There are no balls in any boxes. Thus, the state where all boxes other than the X-th (3rd) box contain no balls is already achieved, so the required number of operations is 0.

Sample Input 3

2 2
1 1
1 1
1 2
1 2

Sample Output 3

-1

There is no way to perform the operation to achieve a state where all boxes other than the X-th (2nd) box contain no balls.

Sample Input 4

10 10
0 0 0 0 0 0 1 0 1 0
0 0 0 0 1 1 0 0 1 0
1 4 9 5 8 2 3 6 10 7
7 4 9 10 6 3 1 2 8 5

Sample Output 4

8