[POI2004]逻辑门

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file poi2004_bra.in Output file poi2004_bra.out

【题目描述】

让我们考虑一个有n个门的电路。这些门从0到n-1编号。每个门有着确定数目的输入和一个输出。所有这些输入输出的值都是0,1或1/2.每个输入都来自某个门的一个输出,这两者的值相等。每个输出可以和不止一个输入相连。编号为0,1的门是特殊的——它们没有输入,并且输出值总是等于其编号:0号门总是输出0,1号门总是输出1.我们说门的输出状态(简称为门的状态)是合法的,如果满足以下条件:

·a) 输出值等于0并且这个门的输入中0多于1.

·b) 输出值等于1/2并且这个门的输入中0与1数目相同。

·c) 输出值等于1并且这个门的输入中1多于0.

·d) 这个门是特殊的,即其编号为0或1,并且其输出值等于编号。

当所有门的状态都合法时,我们称这个电路是合法的。我们说一个门的状态是固定的,如果这个门的输出状态在所有有效电路中都一样。

你需要读入电路的描述,并且对每个门,计算出它的状态是否固定,如果固定,这个状态是多少。

【输入格式】

输入文件的第一行是门的数量n,2<=n<=10000.

第2行到第n-1行描述了门的连接状态。第i行包含i号门的输入。这一行开头有一个整数k_i表示输入个数(k_i>=1),接下来有k_i个整数,描述了i号门的输入来自哪些门的输出。其中k_i>=1。这些数都用空格隔开。所有门的输入数之和不超过200000.

【输出格式】

输出n行,依次描述从0号门到n-1号门的固定情况。

根据i-1号门的状态,第i行应当输出:

·0——如果i号门的状态固定为0,

·1/2——如果i号门的状态固定为1/2,

·1——如果i号门的状态固定为1,

·?(问号)——如果不确定

【样例输入】

5

2 0 1

2 4 2

2 2 4

【样例输出】

0

1

1/2

?

?

【提示】

样例如下图:

【来源】

POI 2004 Gates