← 返回题目列表

AtCoder · awc0030_b

B. 购物清单

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

分数: 266 分

问题陈述

高桥是一名大学生,他每天都会去购买食材。附近超市有卖 N 成分类型,每种成分都有固定价格并分类为 蔬菜 or 肉.

出于健康原因,高桥决定购买确切的 1 蔬菜和完全一样 1 肉类项目,总共 2 成分,在每次购物之旅中。

高桥正在计划他的购物 M 天。不过,超市的库存每天都有所不同,并不是所有的食材每天都能买到。

对于每种成分 i (1 \leq i \leq N),价格 P_i 和分类 给出了 T_i 。如果 T_i = 0,成分 i 是一种蔬菜;如果 T_i = 1,成分 i 是肉。每种成分都属于这两个类别之一。

每天 j (1 \leq j \leq M),可用成分的数量 K_j 和可用成分编号列表 给出了 S_{j,1}, S_{j,2}, \ldots, S_{j,K_j} 。同一天的可用列表中相同的成分不会出现多次。

每天选择时查找最低总价 1 蔬菜和 1 肉类项目来自当天可用的食材。如果可用的成分不包括蔬菜和肉类,则无法满足条件,则输出 -1.

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq P_i \leq 10^9
  • T_i \in \{0, 1\}
  • 1 \leq K_j \leq N
  • 1 \leq S_{j,k} \leq N (1 \leq k \leq K_j)
  • 每天 j, S_{j,1}, S_{j,2}, \ldots, S_{j,K_j} 都是不同的
  • \sum_{j=1}^{M} K_j \leq 2 \times 10^5
  • 所有输入值均为整数

输入

N M
P_1 T_1
P_2 T_2
\vdots
P_N T_N
K_1 S_{1,1} S_{1,2} ... S_{1,K_1}
K_2 S_{2,1} S_{2,2} ... S_{2,K_2}
\vdots
K_M S_{M,1} S_{M,2} ... S_{M,K_M}
  • 第一行包含整数 N 表示成分种类的数量和整数 M 代表购物天数,以空格分隔。
  • 从第 2 行到 (N + 1)第行,给出了每种成分的信息。
  • 的 (1 + i)第行包含价格 成分 P_i 成分的 i 和分类值 T_i (0:蔬菜, 1:肉),用空格分隔。
  • 从 (N + 2)第 行 (N + M + 1)第行,给出了每天可用的成分信息。
  • 的 (N + 1 + j)- 第行包含可用成分的数量 K_j 当天 j 和可用成分编号 S_{j,1}, S_{j,2}, \ldots, S_{j,K_j},用空格分隔。

输出

输出 M 行。上 j- 第行 (1 \leq j \leq M),输出选择时总价的最低值 1 蔬菜和 1 肉类项目来自当天可用的食材 j。如果不存在有效选择,则输出 -1.


示例输入 1

5 3
100 0
200 1
150 0
300 1
250 0
3 1 2 3
2 1 5
4 1 3 4 5

示例输出 1

300
-1
400

示例输入 2

6 4
500 0
300 1
200 0
400 1
150 0
600 1
3 1 3 5
2 2 4
5 1 2 3 4 5
2 1 3

示例输出 2

-1
-1
450
-1

示例输入 3

10 5
120 0
350 1
80 0
500 1
200 0
150 1
90 0
420 1
300 0
180 1
6 1 2 3 4 5 6
4 7 8 9 10
3 1 5 9
5 2 4 6 8 10
8 1 2 3 6 7 8 9 10

示例输出 3

230
270
-1
-1
230