Polish version    English version  
  History of OI -> XI OI 2003/2004 -> Problems

 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
Stage III - results
Stage II - results
Stage I - results
Stage II
Stage III
For contestants
Helpful resources
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
XI Olympiad in Informatics 2003/2004

Task: bra


II stage competition  
Source file: bra.xxx (xxx=pas,c,cpp)
Memory limit: 32 MB

Let us consider a circuit consisting of n gates. The gates are numbered from 0 to n-1. Each gate has a certain number of inputs and exaclty one output. Each of them (inputs and outputs) may be in either one of the states 0, 1 or 1/2. Each input is connected to exactly one output of some gate. Input's state equals the state of the output it is connected to. Each output may be connected to an aribtrary number of inputs. The gates with numbers 0 i 1 are special --- they don't have any input at all while their outputs are always in the following states: 0 for a gate with a number 0, 1 for a gate with a number 1. We say that the state of the output of a gate (in short: gate's state) is "valid", if:

  • a) it equals 0 and the gate has more inputs in state 0 than in state 1.
  • b) it equals 1/2 and the gate has the same number of inputs in state 0 as in state 1.
  • c) it equals 1 and the gate has more inputs in state 1 than it has in state 0.
  • d) the gate is special, i.e. it's number is 0 or 1, and its state is 0 or 1 respectively.
We say that a circuit's state is "valid" if all the states of its gates are valid. We say that a gate's state is "fixed" if the gate is in the same state in all circuit's valid states.


Write a programme that:

  • Reads the circuit's description from the standard input.
  • For each gate checks if it's state is fixed, and determines it, if so.
  • Writes the determined states of gates to the standard output.


The first line of the standard input contains the number of gates n, 2 <= n <= 10,000. The following n-2 lines contain the descriptions of gates' connections - line no. i describes inputs of the gate no. i. There is the number k_i of inputs of this gate, followed by k_i numbers of gates, k_i >= 1. Those are the numbers of gates whose outputs are connected to successive inputs of the gate's no. i. Numbers in each line are separated by single spaces. The total number of all inputs of all gates does not exceed 200,000.


Your programme should write n lines to the standard output. Depending on the state of gate no. i-1, ist line should contain:
  • 0 --- if it is determined and equals 0,
  • 1/2 --- if it is determined and equals 1/2,
  • 1 --- if it is determined and equals 1,
  • ? (question mark) --- if it is not determined.


For the following input data:

2 0 1
2 4 2
2 2 4

the correct answer ist:


Print friendly version