COI '16 #1 Ili

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 4.0s
Memory limit: 1G

Problem type

Mirko is building a simple logic circuit in his workshop. The circuit consists of n starting wires denoted with x_1, x_2, \dots, x_n and m logic elements OR denoted with c_1, c_2, \dots, c_m. Each element has exactly two inputs and one output. Each of the inputs is connected to either a starting wire x_j or to the output of another element c_j. Of course, there are no cycles in a logic circuit and, moreover, it holds that the input of c_j can be connected to the output of c_i only when it holds i < j.

Each starting wire in the circuit can be set to value 0 or 1, and the value of the output of each element is the logic OR operation of its inputs — the value is 0 if the values of both inputs are 0, otherwise it is 1.

Mirko does not know the initial values of the starting wires, but with careful measurements, he has determined the values of the output of some elements. Find the remaining values of the outputs that can be unambiguously determined based on the measurements.

Input Specification

The first line of input contains the positive integers n and m — the number of starting wires and the number of elements in the circuit. The following line contains a string of exactly m characters that describes the measured value of the output of the element c_j, or is equal to ? if Mirko did not perform this measurement. The j^\text{th} of the following m lines contains labels of two inputs of the circuit c_j, each label being either a label of the starting wire in the form of xi where it holds 1 \le i \le n, or a label of the element ci where it holds 1 \le i < j. The two inputs of the element c_j may be the same. You can assume that the measured values are mutually consistent.

Output Specification

The first line of output must contain a string of m characters — the j^\text{th} character in the string must correspond to the value of the output of c_j or be ? if that value cannot be unambiguously determined.

Constraints

Subtask Score Constraints
1 7 n \le 15, m \le 20
2 42 n, m \le 500
3 51 n, m \le 10\,000

Sample Input 1

4 4
10??
x1 x2
x2 x3
x3 x4
x1 c3

Sample Output 1

10?1

Explanation for Sample Output 1

Sample Input 2

4 5
11???
x1 x2
x3 x4
x1 x3
x2 x4
c3 c4

Sample Output 2

11??1

Comments

There are no comments at the moment.