← 返回题目列表

Codeforces · 1010/D

D. 火星探测器

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

娜塔莎乘坐火星探测器绕火星旅行。但突然间它崩溃了,即——它内部的逻辑方案。该方案是一个无向树(连通无环图),根位于顶点$$$1$$$,其中每个叶子(不包括根)都是输入,所有其他顶点都是逻辑元素,包括根,它是输出。每个输入都馈送一位。输出端返回一位。

有四种类型的逻辑元素:AND($$$2$$$ 输入)、OR($$$2$$$ 输入)、XOR($$$2$$$ 输入)、NOT($$$1$$$ 输入)。逻辑元素从其直接后代(输入)获取值并返回它们执行的函数的结果。娜塔莎知道火星探测器的逻辑方案,也知道只有一个输入被破坏。为了修复火星探测器,她需要更改此输入的值。

对于每个输入,确定如果 Natasha 更改此输入,输出将是什么。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^6$$$) - 图中的顶点数(输入和元素)。

接下来的 $$$n$$$ 行的第 $$$i$$$ 包含第 $$$i$$$ 个顶点的描述:第一个单词“AND”、“OR”、“XOR”、“NOT”或“IN”(表示方案的输入)是顶点类型。如果此顶点为“IN”,则遵循此输入的值($$$0$$$ 或 $$$1$$$),否则遵循此元素的输入顶点的索引:“AND”、“OR”、“XOR”有 $$$2$$$ 输入,而“NOT”有 $$$1$$$ 输入。顶点从 1 开始编号。

保证输入数据包含正确的逻辑方案,并由顶点 $$$1$$$ 产生输出。

输出

打印字符串“0”和“1”(不带引号)——按顶点索引升序排列每个输入的问题答案。

示例

输入 #1

10
AND 9 4
IN 1
IN 1
XOR 6 5
AND 3 7
IN 0
NOT 10
IN 1
IN 1
AND 2 8

输出 #1

10110

注意

示例中的原始方案(在输入更改之前):

绿色表示位“1”,黄色表示位“0”。

如果 Natasha 将输入位 $$$2$$$ 更改为 $$$0$$$,则输出将为 $$$1$$$。

如果 Natasha 将输入位 $$$3$$$ 更改为 $$$0$$$,则输出将为 $$$0$$$。

如果 Natasha 将输入位 $$$6$$$ 更改为 $$$1$$$,则输出将为 $$$1$$$。

如果 Natasha 将输入位 $$$8$$$ 更改为 $$$0$$$,则输出将为 $$$1$$$。

如果 Natasha 将输入位 $$$9$$$ 更改为 $$$0$$$,则输出将为 $$$0$$$。