← 返回题目列表

AtCoder · arc189_c

C. 球和盒子

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有 N 盒。 对于 i = 1, 2, \ldots, N, i第一个盒子包含 A_i 红球和 B_i 蓝色球。

你还得到了两种排列 P = (P_1, P_2, \ldots, P_N) 和 Q = (Q_1, Q_2, \ldots, Q_N) of (1, 2, \ldots, N).

Takahashi 可以重复以下操作任意次数,可能为零:

  • 选择一个整数 1 \leq i \leq N,并从 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).
  • 接下来,对第二个框执行操作。结果, A = (1, 0, 0, 1, 0), B = (1, 0, 1, 0, 0).
  • 然后,对第一个框执行操作。结果, 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).

这四个操作实现了除 X第(第三)个盒子不含球。 这是可能的最小操作数。


示例输入 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第(第二)个盒子不含球。


示例输入 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