远端评测题 1000ms 128MiB

「UOI-R1」智能推荐

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

数据已加强。

题目描述

现在有 NN 道题。

天数的编号从 00 开始,每一天你可以做若干道题,你只能做以前推荐过的或者当天推荐的题(每道题只可以做一次)。第一天,智能推荐会推荐 pp 道题。

推荐规则如下:

对于第 ii 道题,如果有可能被推荐的话,就会有一个题目集合 sis_i。当且仅当你把 sis_i 中每一道题都做出来并且其中有一道题是当天做的,那么下一天就会推荐第 ii 题。

你想做完第 KK 道题,问至少第几天你才能满足愿望?

输入格式

第一行三个整数 N,K,pN,K,p,含义如题目所述。

第二行 pp 个整数,表示第一天推荐的题的题号。

第三行一个整数 RR,表示有 RR 条推荐规则。

接下来 RR 行,每行包含一条规则,每行格式如下:

一个整数 viv_i,表示要推荐的题的题号。接着一个整数 sis_i,表示要使得这道题被推荐,一共要做的题目数量。接下来 sis_i 个整数 pip_i,表示要做的每道题。

输出格式

一个整数表示最少第几天才能满足愿望。

如无论如何,第 KK 题都无法完成,则输出 -1

5 5 2
1 2
3
3 2 1 2
4 3 1 2 3
5 3 1 3 4
3
1 1 1
1
0
0
7 7 2
1 2
2
3 2 1 2
6 2 1 2
-1
见文件附件的 rec4.in
见文件附件的 rec4.ans

提示

【样例解释 #1】

00 天推了第 1,21,2 题,都做了。

11 推了第 33 题,做了。

22 推了第 44 题,做了。

33 推了第 55 题,也就是第 KK 题,做了。

33 天即可做完第 KK 题目。

【样例解释 #2】

00 天推了第 11 题,也就是第 KK 题,做了。 第 00 天就做完了。

【数据范围】

以下记 si\left| s_i \right| 表示推荐规则中第 ii 条规则中,如果 viv_i 被推荐,要做的所有题。

对于 30%30\% 的数据,保证 1N1001 \leq N \leq 100

对于 50%50\% 的数据,保证没有环。

对于 100%100\% 的数据,保证 1K,si,pi,viN5×1031 \le K,s_i,p_i,v_i \le N \le 5\times 10^30R5×1030 \leq R \leq 5 \times 10^3si|s_i| 互不相同,且对于每一个 si|s_i| 都有 pip_i 互不相同,viv_i 互不相同。

2024.8.7~8.8普及集训第五/六天(追光班)

未参加
状态
已结束
规则
IOI
题目
16
开始于
2024-8-7 8:00
结束于
2024-8-15 16:00
持续时间
200 小时
主持人
参赛人数
30