← 返回题目列表

AtCoder · awc0007_b

B. 可以合作的实验室

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

分数: 266 分

问题陈述

高桥在该大学的研究支持中心工作。 N 实验室,每个实验室都致力于多个研究主题。实验室 i (1 \leq i \leq N) 正在研究 M_i 研究主题,每个主题由一串小写英文字母表示 W_{i,1}, W_{i,2}, \ldots, W_{i,M_i}。请注意,同一研究主题不会在同一实验室内出现多次。

为了促进合作研究,该大学决定调查“有资格合作”的实验室。让 S_i = \{W_{i,1}, W_{i,2}, \ldots, W_{i,M_i}\} 是实验室的研究主题集 i 正在处理。两个实验室 i, j (i \neq j) 被认为是“有资格合作”,如果双方共同的研究主题数量 S_i 和 S_j 至少 K,即 |S_i \cap S_j| \geq K 成立。这里,两个研究主题是否相同取决于它们的代表字符串是否完全匹配。

高桥列出了每个实验室正在研究的研究主题。根据此信息,找到“有资格合作”的实验室对的数量。请注意,这对实验室 i 和实验室 j 被认为与实验室对相同 j 和实验室 i。计算对的数量 (i, j) 满意 1 \leq i < j \leq N 满足条件。

约束

  • 2 \leq N \leq 500
  • 1 \leq K \leq 50
  • 1 \leq M_i \leq 50 (1 \leq i \leq N)
  • W_{i,j} 是长度介于 1 和 20 仅由小写英文字母组成 (1 \leq i \leq N, 1 \leq j \leq M_i)
  • 同一研究主题不会在同一实验室内出现多次(也就是说,如果 j \neq k 然后 W_{i,j} \neq W_{i,k})

输入

输入由以下格式的标准输入给出。

N K
M_1
W_{1,1} W_{1,2} \ldots W_{1,M_1}
M_2
W_{2,1} W_{2,2} \ldots W_{2,M_2}
\vdots
M_N
W_{N,1} W_{N,2} \ldots W_{N,M_N}

第一行包含实验室数量 N 和阈值 K 用于确定“协作资格”,以空格分隔。

然后,对于每个实验室 i (i = 1, 2, \ldots, N),以下 2 行按顺序给出:

  • 第一行包含研究主题的数量 M_i 那个实验室 i 正在处理。
  • 第二行包含 M_i 字符串 W_{i,1}, W_{i,2}, \ldots, W_{i,M_i} 代表实验室的研究主题 i,用空格分隔。

输出

在一行中输出“有资格合作”的实验室对的数量。


示例输入 1

3 2
3
ai ml data
4
ml data web security
2
ai ml

示例输出 1

2

示例输入 2

4 1
3
biology chemistry physics
2
chemistry medicine
4
physics math statistics chemistry
3
biology ecology environment

示例输出 2

4

示例输入 3

5 3
5
deeplearning nlp vision robotics optimization
4
nlp vision speech recognition
6
deeplearning nlp vision gan transformer diffusion
3
robotics control automation
5
nlp vision deeplearning bert attention

示例输出 3

3