← 返回题目列表

AtCoder · awc0031_a

A. 烹饪比赛和食材

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

分数: 266 分

问题陈述

高桥担任烹饪比赛的评委。 N 厨师正在参加本次比赛,每位厨师都被分配了一个编号, 1 to N.

比赛使用 M 成分类型,编号为 1 to M。厨师 i 专门从事 C_i 原料种类,以及其专攻的原料数量是 T_{i,1}, T_{i,2}, \ldots, T_{i,C_i}。当 C_i = 0,厨师 i 没有他们专门生产的成分。

比赛预赛结果,厨师 i 获得的分数为 V_i。的 N 厨师按照以下规则排名,排名靠前的 K 厨师(排名 1圣通 Kth) 晋级决赛。

  • 得分较高的厨师排名较高(即排名数字较小)。
  • 得分相同的厨师中,厨师编号较小的厨师排名较高。

在这些规则下,所有厨师的排名是唯一确定的,并且 K 晋级决赛的厨师也是独一无二的。

决赛中, K 晋级厨师将只使用他们共同擅长的食材来烹饪菜肴。也就是说,只有当所有食材都满足时才可以在决赛中使用某种食材。 K 晋级决赛的厨师专注于该食材。

对于高桥,找出所有成分的数量 K 晋级决赛的厨师普遍专攻。如果没有这种食材,则输出 0.

约束

  • 1 \leq K \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 0 \leq C_i \leq M
  • \sum_{i=1}^{N} C_i \leq 2 \times 10^5
  • 1 \leq V_i \leq 10^9
  • 1 \leq T_{i,j} \leq M
  • 对于每个厨师 i, T_{i,1}, T_{i,2}, \ldots, T_{i,C_i} 都是不同的
  • 所有输入值均为整数

输入

N M K
V_1 C_1 T_{1,1} T_{1,2} \ldots T_{1,C_1}
V_2 C_2 T_{2,1} T_{2,2} \ldots T_{2,C_2}
\vdots
V_N C_N T_{N,1} T_{N,2} \ldots T_{N,C_N}
  • 第一行包含厨师人数 N,成分类型数量 M,以及入围人数 K,用空格分隔。
  • 在下面 N 行, i- 第行 (1 \leq i \leq N) 首先包含厨师 i的得分 V_i 和成分数量 C_i 那个厨师 i 专门从事,用空格分隔。如果 C_i \geq 1,成分编号 T_{i,1}, T_{i,2}, \ldots, T_{i,C_i} 位于同一行,以空格分隔。如果 C_i = 0,该行仅包含两个值 V_i 和 C_i.

输出

在一行上输出所有成分的数量 K 晋级决赛的厨师普遍擅长。


示例输入 1

3 5 2
100 3 1 2 3
80 4 1 2 4 5
90 2 1 2

示例输出 1

2

示例输入 2

5 6 3
50 2 1 3
100 3 1 2 3
100 4 1 2 3 4
75 3 2 3 5
60 0

示例输出 2

2

示例输入 3

10 8 4
500 5 1 2 3 4 5
450 4 1 2 3 6
480 6 1 2 3 4 5 6
300 3 1 2 7
520 4 1 2 3 8
200 2 1 2
490 5 1 2 3 5 7
350 4 2 3 4 5
400 3 1 3 4
100 1 1

示例输出 3

3