分数: 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