分数: 525 点
问题陈述
你被给予 Q 整数三元组 套装的 (a_1, b_1, d_1), (a_2, b_2, d_2), \ldots, (a_Q, b_Q, d_Q).
一个子集 S 集合中的 \lbrace 1, 2, \ldots, Q\rbrace 被定义为 好套装 如果存在整数序列 (X_1, X_2, \ldots, X_N) 长度 N 满足:
X_{a_i} - X_{b_i} = d_i 对于所有人 i \in S.
开始于 S 作为空集,执行以下操作 i = 1, 2, \ldots, Q 按此顺序:
If S \cup \lbrace i \rbrace 是一套好的,然后更换 S 与 S \cup \lbrace i \rbrace.
打印最终集合的所有元素 S in 升序.
约束
- 所有输入值均为整数。
- 1 \leq N, Q \leq 2 \times 10^5
- 1 \leq a_i, b_i \leq N
- -10^9 \leq d_i \leq 10^9
输入
输入由标准输入按以下格式给出:
N Q a_1 b_1 d_1 a_2 b_2 d_2 \vdots a_Q b_Q d_Q
输出
打印序列 最终组的所有元素的 (s_1, s_2, \ldots, s_k) 最终集合的所有元素 S in 升序,以空格分隔,格式如下:
s_1 s_2 \ldots s_k
示例输入 1
3 5 1 2 2 3 2 -3 2 1 -1 3 3 0 1 3 5
示例输出 1
1 2 4 5
开始于 S 作为空集,执行问题陈述中描述的操作 i = 1, 2, 3, 4, 5 按此顺序,如下。
- 对于 i = 1,集合 S \cup \lbrace i \rbrace = \lbrace 1 \rbrace 是一个很好的集合,因为 (X_1, X_2, X_3) = (3, 1, 4) 满足问题陈述中的条件,例如,因此替换 S 与 \lbrace 1\rbrace.
- 对于 i = 2,集合 S \cup \lbrace i \rbrace = \lbrace 1, 2 \rbrace 是一个很好的集合,因为 (X_1, X_2, X_3) = (3, 1, -2) 满足问题陈述中的条件,例如,因此替换 S 与 \lbrace 1, 2\rbrace.
- 对于 i = 3,集合 S \cup \lbrace i \rbrace = \lbrace 1, 2, 3 \rbrace 不是一个好的设置。
- 对于 i = 4,集合 S \cup \lbrace i \rbrace = \lbrace 1, 2, 4 \rbrace 是一个很好的集合,因为 (X_1, X_2, X_3) = (3, 1, -2) 满足问题陈述中的条件,例如,因此替换 S 与 \lbrace 1, 2, 4\rbrace.
- 对于 i = 5,集合 S \cup \lbrace i \rbrace = \lbrace 1, 2, 4, 5 \rbrace 是一个很好的集合,因为 (X_1, X_2, X_3) = (3, 1, -2) 满足问题陈述中的条件,例如,因此替换 S 与 \lbrace 1, 2, 4, 5\rbrace.
因此,最后一组 S is \lbrace 1, 2, 4, 5\rbrace.
示例输入 2
200000 1 1 1 1
示例输出 2
决赛 S 为空。
示例输入 3
5 20 4 2 125421359 2 5 -191096267 3 4 -42422908 3 5 -180492387 3 3 174861038 2 3 -82998451 3 4 -134761089 3 1 -57159320 5 2 191096267 2 4 -120557647 4 2 125421359 2 3 142216401 4 5 -96172984 3 5 -108097816 1 5 -50938496 1 2 140157771 5 4 65674908 4 3 35196193 4 4 0 3 4 188711840
示例输出 3
1 2 3 6 8 9 11 14 15 16 17 19