配点: 100 点
問題文
Bitaro 正在打台球。 JOI乡村台球在桌子上一字排开 N 球 这是一个使用 1,2,...,N 的游戏,桌子上有一个用于落球的洞。球一旦落入洞中,就无法返回球台,也无法再次掉落。 Bitaro 的目标是将数字最大的球放入洞中。
丢球是一项需要集中注意力的任务。起初,比特罗的 集中力 是 X 和球 i (1 \leqq i \leqq N)会提高你的注意力。 A_i 减少。浓度 如果小于 A_i ,则球 i 无法删除。
另外,在这个台球游戏中,有关于落球顺序的规则。具体来说, P_i = -1 (1 \leqq i \leqq N)当球 i 可以随时删除, 当 P_i \neq -1 时,球 要掉落 i ,球必须 P_i 肯定已经被删除了。
给定 Bitaro 的注意力和每个球的信息,编写一个程序来确定 Bitaro 是否可以将球扔进洞中,如果可以,请找到他可以扔下的最大球数。
制約
- 1 \leqq N \leqq 200\,000.
- 1 \leqq X \leqq 10^{15}.
- 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N).
- 1 \leqq P_i \leqq N 或 P_i = -1 (1 \leqq i \leqq N).
- P_i \neq i (1 \leqq i \leqq N).
- 所有输入值都是整数。
小課題
- (6 点) N \leqq 1000, P_i = -1 (1 \leqq i \leqq N).
- (9 点) N \leqq 1000, P_1 = -1, P_i = i-1 (2 \leqq i \leqq N).
- (16 点) N \leqq 1000, P_i < i (1 \leqq i \leqq N).
- (20 点) P_i < i (1 \leqq i \leqq N).
- (19 点) N \leqq 1000.
- (30 点)没有额外的限制。
入力
输入按以下格式给出。
N X A_1 A_2 \dots A_N P_1 P_2 \dots P_N
出力
Bitaro 可以放入洞中的最大球数。
在 1 行上输出。
然而,Bitaro 1 如果你不能丢球,请使用
输出 -1 。
入力例 1
6 7 1 2 4 3 10 100 -1 -1 -1 -1 -1 -1
出力例 1
4
起初,Bitaro的注意力是 7 。
全部
关于 i (1 \leqq i \leqq N)关于 P_i = -1 因此,只要Bitaro有足够的专注力,他可以随时将任何球投进洞中。
例如,如果您执行以下操作,Bitaro 将会踢球。 您可以删除 4 。
- 一、球 将 3 放入孔中。比特太郎的浓度 4 减少,剩余浓度为 3 变为。
- 接下来,球 4 放入孔中。比特太郎的浓度 3 减少,剩余浓度为 0 变为。
另外,Bitaro 正在打球。 5,6 无法掉入洞中。因此,Bitaro 最多可以将球放入洞中的数量是 4 。
此输入示例是一个小作业。 1,3,4,5,6 满足约束。 将
入力例 2
5 12 1 2 3 5 8 -1 1 2 3 4
出力例 2
4
起初,Bitaro的注意力是 12 。
例如,如果您执行以下操作,Bitaro 将会踢球。
您可以删除 4 。
- 一、球
将 1 放入洞中。 ( P_1 = -1 因此,球 1 可以随时删除。 )
- Bitaro的浓度是 1 减少,剩余浓度为 11 变为。
- 接下来,球 2 放入洞中。 ( P_2 = 1 球 1 已经掉落,所以球 2 可以被删除。 )
- Bitaro的浓度是 2 减少,剩余浓度为 9 变为。
- 接下来,球 3 放入洞中。 ( P_3 = 2 球 2 已经掉落,所以球 3 可以被删除。 )
- Bitaro的浓度是 3 减少,剩余浓度为 6 变为。
- 接下来,球 4 放入洞中。 ( P_4 = 3 球 3 已经掉落,所以球 4 可以被删除。 )
- Bitaro的浓度是 5 减少,剩余浓度为 1 变为。
另外,Bitaro 正在打球。 5 无法掉入洞中。因此,Bitaro 最多可以将球放入洞中的数量是 4 。
此输入示例是一个小作业。 2,3,4,5,6 满足约束。 将
入力例 3
8 10 3 1 4 1 5 9 2 6 -1 1 2 -1 4 4 5 7
出力例 3
7
此输入示例是一个小作业。 3,4,5,6 满足约束。 将
入力例 4
2 1000000000000000 1 1 2 1
出力例 4
-1
P_1 = 2 因此,球 1 ,球必须 2 肯定已经被删除了。相反, P_2 = 1 因此,球 2 ,球必须 1 肯定已经被删除了。由此看来,比特太郎 1 甚至不能丢球。因此, -1 。
此输入示例是一个小作业。 5,6 满足约束。 将
入力例 5
9 2468024680 123456789 234567891 345678912 456789123 567891234 678912345 789123456 891234567 912345678 6 5 4 -1 3 2 1 9 8
出力例 5
6
此输入示例是一个小作业。 5,6 满足约束。 将