← 返回题目列表

Codeforces · 2112/F

F. 变量和运算

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

有 $$$n$$$ 个变量;我们将第 $$$i$$$ 变量的值表示为 $$$a_i$$$。

还有 $$$m$$$ 操作将应用于这些变量;第 $$$i$$$ 操作由三个整数 $$$x_i、y_i、z_i$$$ 描述。当应用第 $$$i$$$ 操作时,变量 $$$x_i$$$ 被分配以下值:$$$\min(a_{x_i}, a_{y_i} + z_i)$$$。

每个操作都将被应用 恰好一次,但它们的顺序不固定;它们可以按任何顺序应用。

让我们调用一系列初始变量值 $$$a_1, a_2, \dots, a_n$$$ 稳定,如果无论我们以哪种顺序应用操作,结果值都将是相同的。如果第 $$$i$$$ 个变量的结果值取决于运算顺序,则初始变量值的序列称为 $$$i$$$-不稳定.

您必须处理 $$$q$$$ 查询。在每个查询中,您将获得初始值 $$$a_1、a_2、\dots、a_n$$$ 和整数 $$$k$$$;在应用操作之前,您最多可以 $$$k$$$ 次选择一个变量并将其减少 $$$1$$$。对于每个变量 $$$i$$$,您必须独立确定是否可以将给定值转换为 $$$i$$$ 不稳定序列。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 500$$$; $$$1 \le m \le 4 \cdot 10^5$$$) — 分别是变量和操作的数量。

然后是 $$$m$$$ 行。其中第 $$$i$$$ 包含三个整数 $$$x_i, y_i, z_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$; $$$0 \le z_i \le 10^5$$$) — 第 $$$i$$$ 操作的描述。

下一行包含一个整数 $$$q$$$ ($$$1 \le q \le 1000$$$) — 查询数。

每个查询由两行组成:

  • 第一行包含一个整数 $$$k$$$ ($$$0 \le k \le 10^9$$$) — 您可以选择变量的最大次数并将其减少 $$$1$$$;
  • 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — 变量的初始值。

输出

对于每个查询,打印 $$$n$$$ 零和/或一的字符串。第 $$$i$$$ 个字符应该是 1 如果可以获得 $$$i$$$-不稳定序列,或者 0 否则。

示例

输入
复制

4 5
2 1 10
3 2 5
1 4 8
1 2 6
3 1 17
3
0
20 0 15 5
10
20 0 15 5
30
20 0 15 5

输出
复制

0000
0000
0110

输入
复制

3 5
1 2 100
1 2 10
1 3 5
1 2 100
3 2 5
1
1000000000
0 0 0

输出
复制

000

输入
复制

3 4
2 3 5
1 2 0
3 1 4
1 3 4
10
5
7 5 3
2
5 7 0
1
1 1 1
5
3 0 1
0
5 3 5
5
6 0 4
5
1 5 6
1
7 7 2
1
1 6 6
4
7 7 2

输出
复制

000
000
000
001
000
001
001
000
000
000

注意

考虑第一个例子。如果初始变量值为 $$$[20, 0, 15, 5]$$$,则无论操作顺序如何,结果值都将为 $$$[6, 0, 5, 5]$$$。减少变量 $$$10$$$ 倍是不够的。然而,如果我们可以应用不超过 $$$30$$$ 的更改,我们可以将 $$$1$$$-st 变量减少 $$$2$$$,并将 $$$4$$$-th 变量减少 $$$25$$$,我们得到等于 $$$[18, 0, 15, -20]$$$ 的初始值,并且该序列是 $$$2$$$-不稳定的$$$3$$$-不稳定:

  • 如果您按照给定的顺序应用操作,您将得到 $$$[-12, 0, 5, -20]$$$;
  • 但是,如果您按 $$$[3, 2, 4, 1, 5]$$$ 的顺序应用运算,您将得到 $$$[-12, -2, 5, -20]$$$;
  • 如果您按 $$$[3, 4, 5, 1, 2]$$$ 的顺序应用运算,您将得到 $$$[-12, -2, 3, -20]$$$。