Problem:


Score : 300 points

Problem Statement

There are N people numbered 1 to N. Each of them is either an honest person whose testimonies are always correct or an unkind person whose testimonies may be correct or not.

Person i gives A_i testimonies. The j-th testimony by Person i is represented by two integers x_{ij} and y_{ij}. If y_{ij} = 1, the testimony says Person x_{ij} is honest; if y_{ij} = 0, it says Person x_{ij} is unkind.

How many honest persons can be among those N people at most?

Constraints

All values in input are integers.

1 \leq N \leq 15

0 \leq A_i \leq N - 1

1 \leq x_{ij} \leq N

x_{ij} \neq i

x_{ij_1} \neq x_{ij_2} (j_1 \neq j_2)

y_{ij} = 0, 1

Input

Input is given from Standard Input in the following format:

N
A_1
x_{11} y_{11}
x_{12} y_{12}
:
x_{1A_1} y_{1A_1}
A_2
x_{21} y_{21}
x_{22} y_{22}
:
x_{2A_2} y_{2A_2}
:
A_N
x_{N1} y_{N1}
x_{N2} y_{N2}
:
x_{NA_N} y_{NA_N}

Output

Print the maximum possible number of honest persons among the N people.

Sample Input 1

3
1
2 1
1
1 1
1
2 0

Sample Output 1

2

If Person 1 and Person 2 are honest and Person 3 is unkind, we have two honest persons without inconsistencies, which is the maximum possible number of honest persons.

Sample Input 2

3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0

Sample Output 2

0

Assuming that one or more of them are honest immediately leads to a contradiction.

Sample Input 3

2
1
2 0
1
1 0

Sample Output 3

1



Sample input:
3
1
2 1
1
1 1
1
2 0


Sample output:
2

Submission status: Runtime Error

Solution code:
import numpy as np

def checkTestimony(honest, A_map, N):
    for i in range(N):
        for j in range(len(A_map[i])):
            Opponent = A_map[i][j][0] - 1
            OpJudge  = A_map[i][j][1]
            if honest[i] == 0:
                if honest[Opponent] == OpJudge:
                    return False 
            else:
                if honest[Opponent] != OpJudge:
                    return False 
    return True    

def setHonest (num, l):
    for i in range(len(l)):
        if (num >> i) & 1 == 1:
            l[i] = 1

N = int(input())
A_map = {}
ans = [0]

for i in range(N):
    A = int(input())
    if A > 0:
        for j in range(A):
            xy = list(map(int,input().split()))
            if i in A_map.keys():
                A_map[i].append(xy)
            else:
                A_map[i] = [xy]
if len(A_map) > 0:
    for i in range(2**N):
        honest = [0] * N
        setHonest(i, honest)

        if checkTestimony(honest, A_map, N) :
            honestNum = honest.count(1)
            ans.append(honestNum)
else:
    ans.append(N)

print(max(ans))

Submission status: Runtime Error

Solution code:
import numpy as np

def checkTestimony(honest, A_map, N):
    for i in range(N):
        for j in range(len(A_map[i])):
            Opponent = A_map[i][j][0] - 1
            OpJudge  = A_map[i][j][1]
            if honest[i] == 0:
                if honest[Opponent] == OpJudge:
                    return False 
            else:
                if honest[Opponent] != OpJudge:
                    return False 
    return True    

def setHonest (num, l):
    for i in range(len(l)):
        if (num >> i) & 1 == 1:
            l[i] = 1

N = int(input())
A_map = {}
ans = [0]

for i in range(N):
    A = int(input())
    if A > 0:
        for j in range(A):
            xy = list(map(int,input().split()))
            if i in A_map.keys():
                A_map[i].append(xy)
            else:
                A_map[i] = [xy]
if len(A_map) > 0:
    for i in range(2**N):
        honest = [0] * N
        setHonest(i, honest)

        if checkTestimony(honest, A_map, N) :
            honestNum = honest.count(1)
            ans.append(honestNum)

print(max(ans))

Submission status: Runtime Error

Solution code:
N = int(input())
say = []
for i in range(N):
    A = int(input())
    t = []
    for j in range(A):
        s = list(map(int,input().split()))
        t.append(s)
    say.append(t)

a = 0
for i in range(2**N):
    judge = 1
    c = 0
    
    for j in range(N):
        if judge = 0:
            break
        if ((i >> j) & 1):
            for k in range(len(say[j])):
                if ((i>>(say[j][k][0]-1))&1) != say[j][k][1]:
                    judge = 0
        else:
            for k in range(len(say[j])):
                if ((i>>(say[j][k][0]-1))&1) == say[j][k][1]:
                    judge = 0
    
    if judge:
        c = bin(i).count("1")
        a = max(a,c)
print(a)

Submission status: Runtime Error

Solution code:
N = int(input())
X = []
Y = []
A = [1]*N
for i in range(N):
	T = int(input())
	X += [[0] * T]
	Y += [[0] * T]
	for j in range(T):
		X[i][j],Y[i][j] = map(int,input().split())
		A[X[i][j]-1] *= Y[i][j]

def rethink(p):
	for j in range(len(X[p])):
		if A[X[p][j]-1] == 0 and Y[i][j] == 1:
			rethink(X[p-1][j])
		A[X[p][j]-1] = Y[i][j]

for i in range(N):
	if A[i] == 1:
		rethink(i)

print(A.count(1))

Submission status: Runtime Error

Solution code:
import itertools
n = int(input())
data = []
for x in range(n):
    for y in range(n):
        k, l = map(int, input().split())
        data.append((x, k - 1, l))
        

ans = 0
for i in itertools.product([1,0], repeat=n):
    s = True
    for g in data:
        if i[g[0]] == 1 and i[g[1]] != g[2]:
            s = False
            break
    if s:
        ans = max(ans, sum(i))
print(ans)

Submission status: Runtime Error

Solution code:
# load
N = int(input())
a = []
x = []
y = []
for i in range(N):
  a.append(int(input()))
  for j in range(a[i]):
    xtmp, ytmp = map(int, input().split())
    x.append(xtmp)
    y.append(ytmp)

# honest?
b = 0
for i in range(N):
  b += (2**i)

b = format(b, 'b') # string representing binary

contradiction = False
while True:
  for i in range(N):
    if int(b[i]) == 1 and (int(b[x[i]-1]) != y[i]):
      contradiction = True
      break
  if contradiction:
    contradiction = False
    b = format(int(b, 2) - 1, 'b')
  else:
    break

h = 0
for i in range(N):
  h += int(b[i])

print(h)

Submission status: Runtime Error

Solution code:
def hou2(tarrs, s, N):
    def checkTestimony(s, t):
        scopy = s[:]
        for i in range(len(s)):
            if s[i] != t[i] and s[i] != 0 and t[i] != 0:
                return None
            if t[i]:
                scopy[i] = t[i]
        return scopy
 
    def search(pos, N, s, acc):
        if pos < N:
            check_tp = checkTestimony(s, tarrs[pos])
            if s[pos] == 1:
                s[pos] = -1
                if check_tp:
                    check_tp[pos] = 1
                    return search(pos + 1, N, check_tp, acc + 1)
                else:
                    return 0
            if check_tp and s[pos] == 0:
                s[pos] = -1
                check_tp[pos] = 1
                return max(search(pos + 1, N, check_tp, acc + 1), search(pos + 1, N, s, acc))
            else: # testimony unacceptable, assuming unkind
                s[pos] = -1
                return search(pos + 1, N, s, acc)
        else:
            return acc
 
    return search(0, N, s, 0)
    
 
if __name__ == "__main__":
    import sys
    in_arr = []
    for line in sys.stdin:
        in_arr.append([int(_) for _ in line.strip().split()])
    N = in_arr[0][0]
    i = 1
    tarrs = []
    s = [0] * N
    while i < len(in_arr):
        tnum = in_arr[i][0]
        tarr = [0] * N
        for j in range(tnum):
            x, y = in_arr[1 + j + i]
            tarr[x - 1] = 1 if y else -1 # -1 claimed unkind, 1 claimed honest
        if tarr[len(tarrs)] == -1: # claimed self to be unkind
            s[len(tarrs)] = -1
        tarrs.append(tarr)
        i += tnum + 1
        print(hou2(tarrs, s, N))

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
import numpy as np

N = int(readline())
info = []
for i in range(N):
    A = int(readline())
    for _ in range(A):
        x,y = map(int,readline().split())
        info.append((i,x-1,y))
        
A = np.array(list(itertools.product([0,1],repeat=N)),np.bool)
for i,x,y in info:
    bl = (A[:,i]) & (A[:,x] == bool(y))
    A = A[bl]

answer = A.sum(axis = 1).max()
print(answer)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
import numpy as np

N = int(readline())
info = []
for i in range(N):
    A = int(readline())
    for _ in range(A):
        x,y = map(int,readline().split())
        info.append((i,x-1,y))
#print(info)

#info=[(0, 1, 1), (1, 0, 1), (2, 1, 0)]

N=3
#A = np.array(list(itertools.product([0,1],repeat=N)),np.bool)
A = np.array(list(itertools.product([0,1],repeat=N)),np.bool)

for i,x,y in info:
    # print(~A[:,i])
    # print(A[:,x])
    bl = (~A[:,i]) | (A[:,x] == bool(y))
    # bl = (A[:,i]) & A[:,x] == bool(y)
    A = A[bl]

answer = A.sum(axis = 1).max()
print(answer)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
import numpy as np

N = int(readline())
info = []
for i in range(N):
    A = int(readline())
    for _ in range(A):
        x,y = map(int,readline().split())
        info.append((i,x-1,y))
#print(info)

#info=[(0, 1, 1), (1, 0, 1), (2, 1, 0)]

N=3
#A = np.array(list(itertools.product([0,1],repeat=N)),np.bool)
A = np.array(list(itertools.product([0,1],repeat=N)),np.bool)

for i,x,y in info:
    # print(~A[:,i])
    # print(A[:,x])
    # bl = (~A[:,i]) | (A[:,x] == bool(y))
    bl = (A[:,i]) & A[:,x] == bool(y)
    A = A[bl]

answer = A.sum(axis = 1).max()
print(answer)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = int(input())
data_dict = {}
data_re_dict = {}
for i in range(1, n + 1):
    temp = int(input())
    temp_list = []
    for j in range(0, temp):
        x, y = map(int, input().split())
        temp_list.append(x)
        temp_list.append(y)
        if x in data_re_dict:
            data_re_dict[x].append(i)
            data_re_dict[x].append(y)
        else:
            data_re_dict[x] = [i, y]
    data_dict[i] = temp_list
max_o_man = 0
for i in range(1, n + 1):
    check_dict = {}
    check_list = [-100] * n
    check_list[i-1] = 1
    check_dict[i] = 1
    count = 1
    flag = 1
    for j in range(0, len(data_dict[i]), 2):
        check_dict[data_dict[i][j]] = data_dict[i][j+1]
        check_list[data_dict[i][j]-1] = 0
        if data_dict[i][j+1] == 1:
            count += 1
    if i in data_re_dict:
        for j in range(0, len(data_re_dict[i]), 2):
            if data_re_dict[i][j] in check_dict:
                if check_dict[data_dict[i][j]] != data_dict[i][j+1]:
                    flag = 0
                    break
            else:
                check_dict[data_re_dict[i][j]] = data_re_dict[i][j + 1]
                check_list[data_re_dict[i][j]-1] = 0
                if data_re_dict[i][j+1] == 1:
                    count += 1
    if flag == 0:
        continue
    for k in range(0, n - 1):
        x = -1
        if 0 not in check_list:
            x = check_list.index(-100)
            check_dict[x + 1] = 1
            count += 1
        else:
            x = check_list.index(0)
        check_list[x] = 1
        for j in range(0, len(data_dict[x + 1]), 2):
            if data_dict[x + 1][j] in check_dict:
                if check_dict[x + 1] == 1:
                    if check_dict[data_dict[x + 1][j]] != data_dict[x + 1][j+1]:
                        flag = 0
                        break
                elif check_dict[x + 1] == 0:
                    if check_dict[data_dict[x + 1][j]] == data_dict[x + 1][j+1]:
                        flag = 0
                        break
            else:
                if check_dict[x + 1] == 1:
                    check_dict[data_dict[x + 1][j]] = data_dict[x + 1][j+1]
                    check_list[data_dict[x + 1][j]-1] = 0
                    if data_dict[x + 1][j+1] == 1:
                        count += 1
                elif check_dict[x + 1] == 0:
                    if data_dict[x + 1][j+1] == 1:
                        check_dict[data_dict[x + 1][j]] = 0
                    elif data_dict[x + 1][j+1] == 0:
                        check_dict[data_dict[x + 1][j]] = 1
                    check_list[data_dict[x + 1][j]-1] = 0
                    if data_dict[x + 1][j+1] == 0:
                        count += 1
        if flag == 0:
            break
        if x + 1 in data_re_dict:
            for j in range(0, len(data_re_dict[x + 1]), 2):
                if data_re_dict[x + 1][j] in check_dict:
                    if check_dict[x + 1] == 1:
                        if check_dict[data_re_dict[x + 1][j]] != data_re_dict[x + 1][j+1]:
                            flag = 0
                            break
                    elif check_dict[x + 1] == 0:
                        if check_dict[data_re_dict[x + 1][j]] == data_re_dict[x + 1][j+1]:
                            flag = 0
                            break
                else:
                    if check_dict[x + 1] == 1:
                        check_dict[data_re_dict[x + 1][j]] = data_re_dict[x + 1][j+1]
                        check_list[data_re_dict[x + 1][j]-1] = 0
                        if data_re_dict[x + 1][j+1] == 1:
                            count += 1
                    elif check_dict[x + 1] == 0:
                        if data_re_dict[x + 1][j+1] == 1:
                            check_dict[data_re_dict[x + 1][j]] = 0
                        elif data_re_dict[x + 1][j+1] == 0:
                            check_dict[data_re_dict[x + 1][j]] = 1
                        check_list[data_re_dict[x + 1][j]-1] = 0
                        if data_re_dict[x + 1][j+1] == 0:
                            count += 1
            if flag == 0:
                break
    if flag == 1:
        if max_o_man < count:
            max_o_man = count
        if max_o_man == n:
            break
print(max_o_man)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = int(input())
data_dict = {}
data_re_dict = {}
for i in range(1, n + 1):
    temp = int(input())
    temp_list = []
    for j in range(0, temp):
        x, y = map(int, input().split())
        temp_list.append(x)
        temp_list.append(y)
        if x in data_re_dict:
            data_re_dict[x].append(i)
            data_re_dict[x].append(y)
        else:
            data_re_dict[x] = [i, y]
    data_dict[i] = temp_list
max_o_man = 0
for i in range(1, n + 1):
    check_dict = {}
    check_list = [-100] * n
    check_list[i-1] = 1
    check_dict[i] = 1
    count = 1
    flag = 1
    for j in range(0, len(data_dict[i]), 2):
        check_dict[data_dict[i][j]] = data_dict[i][j+1]
        check_list[data_dict[i][j]-1] = 0
        if data_dict[i][j+1] == 1:
            count += 1
    if i in data_re_dict:
        for j in range(0, len(data_re_dict[i]), 2):
            if data_re_dict[i][j] in check_dict:
                if check_dict[data_dict[i][j]] != data_dict[i][j+1]:
                    flag = 0
                    break
            else:
                check_dict[data_re_dict[i][j]] = data_re_dict[i][j + 1]
                check_list[data_re_dict[i][j]-1] = 0
                if data_re_dict[i][j+1] == 1:
                    count += 1

    for k in range(0, n - 1):
        x = -1
        if 0 not in check_list:
            x = check_list.index(-100)
            check_dict[x + 1] = 1
            count += 1
        else:
            x = check_list.index(0)
        check_list[x] = 1
        for j in range(0, len(data_dict[x + 1]), 2):
            if data_dict[x + 1][j] in check_dict:
                if check_dict[x + 1] == 1:
                    if check_dict[data_dict[x + 1][j]] != data_dict[x + 1][j+1]:
                        flag = 0
                        break
                elif check_dict[x + 1] == 0:
                    if check_dict[data_dict[x + 1][j]] == data_dict[x + 1][j+1]:
                        flag = 0
                        break
            else:
                if check_dict[x + 1] == 1:
                    check_dict[data_dict[x + 1][j]] = data_dict[x + 1][j+1]
                    check_list[data_dict[x + 1][j]-1] = 0
                    if data_dict[x + 1][j+1] == 1:
                        count += 1
                elif check_dict[x + 1] == 0:
                    if data_dict[x + 1][j+1] == 1:
                        check_dict[data_dict[x + 1][j]] = 0
                    elif data_dict[x + 1][j+1] == 0:
                        check_dict[data_dict[x + 1][j]] = 1
                    check_list[data_dict[x + 1][j]-1] = 0
                    if data_dict[x + 1][j+1] == 0:
                        count += 1
        if flag == 0:
            break
        if x + 1 in data_re_dict:
            for j in range(0, len(data_re_dict[x + 1]), 2):
                if data_re_dict[x + 1][j] in check_dict:
                    if check_dict[x + 1] == 1:
                        if check_dict[data_re_dict[x + 1][j]] != data_re_dict[x + 1][j+1]:
                            flag = 0
                            break
                    elif check_dict[x + 1] == 0:
                        if check_dict[data_re_dict[x + 1][j]] == data_re_dict[x + 1][j+1]:
                            flag = 0
                            break
                else:
                    if check_dict[x + 1] == 1:
                        check_dict[data_re_dict[x + 1][j]] = data_re_dict[x + 1][j+1]
                        check_list[data_re_dict[x + 1][j]-1] = 0
                        if data_re_dict[x + 1][j+1] == 1:
                            count += 1
                    elif check_dict[x + 1] == 0:
                        if data_re_dict[x + 1][j+1] == 1:
                            check_dict[data_re_dict[x + 1][j]] = 0
                        elif data_re_dict[x + 1][j+1] == 0:
                            check_dict[data_re_dict[x + 1][j]] = 1
                        check_list[data_re_dict[x + 1][j]-1] = 0
                        if data_re_dict[x + 1][j+1] == 0:
                            count += 1
            if flag == 0:
                break
    if flag == 1:
        if max_o_man < count:
            max_o_man = count
        if max_o_man == n:
            break
print(max_o_man)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = int(input())
data_dict = {}
data_re_dict = {}
for i in range(1, n + 1):
    temp = int(input())
    temp_list = []
    for j in range(0, temp):
        x, y = map(int, input().split())
        temp_list.append(x)
        temp_list.append(y)
        if x in data_re_dict:
            data_re_dict[x].append(i)
            data_re_dict[x].append(y)
        else:
            data_re_dict[x] = [i, y]
    data_dict[i] = temp_list
max_o_man = 0
for i in range(1, n + 1):
    check_dict = {}
    check_list = [-100] * n
    check_list[i-1] = 1
    check_dict[i] = 1
    count = 1
    for j in range(0, len(data_dict[i]), 2):
        check_dict[data_dict[i][j]] = data_dict[i][j+1]
        check_list[data_dict[i][j]-1] = 0
        if data_dict[i][j+1] == 1:
            count += 1
    for j in range(0, len(data_re_dict[i]), 2):
        check_dict[data_re_dict[i][j]] = data_re_dict[i][j + 1]
        check_list[data_re_dict[i][j]-1] = 0
        if data_re_dict[i][j+1] == 1:
            count += 1
    flag = 1
    for k in range(0, n - 1):
        x = -1
        if 0 not in check_list:
            x = check_list.index(-100)
            check_dict[x + 1] = 1
            count += 1
        else:
            x = check_list.index(0)
        check_list[x] = 1
        for j in range(0, len(data_dict[x + 1]), 2):
            if data_dict[x + 1][j] in check_dict:
                if check_dict[x + 1] == 1:
                    if check_dict[data_dict[x + 1][j]] != data_dict[x + 1][j+1]:
                        flag = 0
                        break
                elif check_dict[x + 1] == 0:
                    if check_dict[data_dict[x + 1][j]] == data_dict[x + 1][j+1]:
                        flag = 0
                        break
            else:
                check_dict[data_dict[x + 1][j]] = data_dict[x + 1][j+1]
                check_list[data_dict[x + 1][j]-1] = 0
                if data_dict[x + 1][j+1] == 1:
                    count += 1
        if flag == 0:
            break
        if x + 1 in data_re_dict:
            for j in range(0, len(data_re_dict[x + 1]), 2):
                if data_re_dict[x + 1][j] in check_dict:
                    if check_dict[x + 1] == 1:
                        if check_dict[data_re_dict[x + 1][j]] != data_re_dict[x + 1][j+1]:
                            flag = 0
                            break
                    elif check_dict[x + 1] == 0:
                        if check_dict[data_re_dict[x + 1][j]] == data_re_dict[x + 1][j+1]:
                            flag = 0
                            break
                else:
                    check_dict[data_re_dict[x + 1][j]] = data_re_dict[x + 1][j+1]
                    check_list[data_re_dict[x + 1][j]-1] = 0
                    if data_re_dict[x + 1][j+1] == 1:
                        count += 1
            if flag == 0:
                break
    if flag == 1:
        if max_o_man < count:
            max_o_man = count
        if max_o_man == n:
            break
print(max_o_man)

Submission status: Runtime Error

Solution code:
n = int(input())
xy = []

for i in range(n):
    a = int(input())
    temp = {}
    for j in range(a):
        x, y = map(int, input().split())
        temp[x] = y
    xy.append(temp)

ans = 0

for i in range(0, 2**n):
    # print('\n', i, bin(i))
    isValid = True
    temp = 0

    for k in range(len(xy)):
        hMap = xy[k]
        kBit = (i >> k) & 1
        # print('k:', k, 'kBit:', kBit)
        if kBit == 1:
            # print('hMap is correct:', hMap)
            for key, value in hMap.items():
                # print(key, value, (i >> (key-1)) & 1, 'must be same')
                if not (i >> (key-1)) & 1 == value:
                    # print('paradox!')
                    isValid = False
                    break
        else:
            # print('hMap is NOT correct:', hMap)
            for key, value in hMap.items():
                # print(key, value, (i >> (key-1)) & 1, 'must be different')
                if not (i >> (key-1)) & 1 != value:
                    # print('paradox!')
                    isValid = False
                    break
    if isValid:
        for j in range(n):
            # print('Check digit:', j)
            jBit = (i >> j) & 1
            # print('bit:', jBit)
            if jBit == 1:
                temp += 1
    	ans = max(ans, temp)

print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
ans=0
g[[-1 for i in range(n)] for j in range(n)]
for i in range(n):
  a=int(input())
  for j in range(a):
    x,y=map(int,input().split())
    g[i][x-1]=y
for i in range(2**n):
  ok=True
  for j in range(n):
    if (i>>j)&1:
      for k in range(n):
        if g[j][k]==-1:
          continue
        if (i>>j)&1!=g[j][k]:
          ok=False
  if ok:
    d=str(bin(i))
    t=d.count('1')
    ans=max(t,ans)
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
g = [[-1 for j in range(n)] for i in range(n)]

for i in range(n):
    for _ in range(int(input())):
        x,y = map(int,input().split())
        g[i][x-1] = y

ans = 0
for s in range(2**n):#bit全探索
    ok = True
    for i in range(n):#行ごとのfor
        if (s>>i&1) == 1:#iが正直者であったら
            for j in range(n):#列の要素のfor,iの言っていることが矛盾がないか確かめる
                if g[i][j] == -1:continue
                if (s>>j&1) != g[i][j]:ok = False#breakにしないのは、breakでは抜けきれないから
    if ok:
        t = str(bin(x)).count("1")
        ans = max(ans,t)
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
g = [[-1 for j in range(n)] for i in range(n)]

for i in range(n):
    for _ in range(int(input())):
        x,y = map(int,input().split())
        q[i][x-1] = y

ans = 0
for s in range(2**n):
    ok = True
    for i in range(n):
        if (s>>i&1) == 1:
            for j in range(n):
                if g[i][j] == -1:continue
                if (s>>j&1) != g[i][j]:ok = False
    if ok:
        t = str(bin(x)).count("1")
        ans = max(ans,t)
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
xy = []
A = []
for i in range(N):
    Ai = int(input())
    xyi = []
    for j in range(Ai):
        xyi.append(list(map(int, input().split())))
    A.append(Ai)
    xy.append(xyi)

ans = 0

for i in range(2**N):
    bin_i = format(i, '4b')
    flag = True
    for n, c in enumerate(bin_i):
        if c == '1':
            for j in range(N):
                for k in range(A[j]):
                    if xy[j][k][0] == n:
                        if xy[j][k][1] == 0:
                            flag = False
                            break
                if not flag:V
                    break
            if not flag:
                break
    if flag is True:
        honest = bin_i.count('1')
        if honest > ans:
            ans = honest

print(ans)

Submission status: Runtime Error

Solution code:
import logging

logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.disable(logging.CRITICAL)

def main():
    N = int(input())

    A = []
    x = []
    y = []

    for i in range(N):
        Ai = int(input())
        xi = []
        yi = []
        A.append(Ai)
        x.append(xi)
        y.append(yi)

        for j in range(Ai):
            xij, yij = map(int, input().split(' '))
            xi.append(xij)
            yi.append(yij)

    logging.info(A)
    logging.info(x)
    logging.info(y)

    ok_list = []
    for bits in range(2 ** N):
        ok_flag = True
        for i in range(N):
            if (bits >> i) & 1 == 0:
                continue

            for j in range(A[i]):
                if (bits >> (x[i][j] - 1) & 1) != y[i][j]:
                    ok_flag = False

    if ok_flag:
        ok_list.append(bin(bits).count('1'))

    print(max(ok_list))

    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

def checkTestimony(honest, A_map, N):
    for i in range(N):
        for j in range(len(A_map[i])):
            Opponent = A_map[i][j][0] - 1
            OpJudge  = A_map[i][j][1]
            if honest[i] == 0:
                if honest[Opponent] == OpJudge:
                    return False 
            else:
                if honest[Opponent] != OpJudge:
                    return False 
    return True    

def setHonest (num, l):
    for i in range(len(l)):
        if (num >> i) & 1 == 1:
            l[i] = 1

N = int(input())
A_map = {}
ans = [0]
for i in range(N):
    A = int(input())
    if A > 0:
        for j in range(A):
            xy = list(map(int,input().split()))
            if i in A_map.keys():
                A_map[i].append(xy)
            else:
                A_map[i] = [xy]

for i in range(2**N):
    honest = [0] * N
    setHonest(i, honest)
    if checkTestimony(honest, A_map, N) :
        honestNum = honest.count(1)
        ans.append(honestNum)

print(max(ans))

Submission status: Runtime Error

Solution code:
#人が一人しかいないとき
if N == 1:
    print(1)
    exit()

#人が2人以上いるとき
l = [0,1]
H = []
#N人それぞれが正直か不誠実かの全パターンを生成
for i in range(2**N+1):
    S = str(bin(i)).zfill(N)
    H.append(S[2:].zfill(N))
#入力を受け取る
IXY = []
for i in range(1,N+1):
    t = int(input())
    for j in range(t):
        x,y = map(int,input().split())
        #i番目の人が「x番目の人はyである」と証言
        IXY.append([i,x,y])

ANS = []
for h in H:
    flg = True
    for ixy in IXY:
        i,x,y = ixy[0]-1,ixy[1]-1,ixy[2]
        if h[i] == "1" and h[x] != str(y):
            flg = False
            break
    if flg:ANS.append(h)

ans = 0
for a in ANS:
    ans = max(a.count("1"),ans)
print(ans)

Submission status: Runtime Error

Solution code:
def inputlist():
	n=int(input())
	A=list()
	for i in range(n):
		Ai = int(input())
		s=list()
		for i in range(Ai):
			s += input().split()
		s = [int(i) for i in s]
		A.append(s)
	return A

A=inputlist()
n=len(A)
ans=0
for i in range(2**n):
	bit_str = str(format(i,'015b'))
	count=0
	for j in range(n):
		if ((i >> j) & 1):
			for k in range(0,len(A[j]),2):
				if (int(bit_str[(-1*A[j][k])-1]) == A[j][k+1]):
					count+=1
	ans = max(ans,count)
print(ans)

Submission status: Runtime Error

Solution code:
def inputlist():
	n=int(input())
	A=list()
	for i in range(n):
		Ai = int(input())
		s=list()
		for i in range(Ai):
			s += input().split()
		s = [int(i) for i in s]
		A.append(s)
	return A

A=inputlist()
n=len(A)
ans=0
for i in range(2**n):
	bit_str = str(format(i,'015b'))
	p = 0
	for j in range(n):
		if ((i >> j) & 1):
			for k in range(0,len(A[j])-1,2):
				if (int(bit_str[(-1*A[j][k])-1]) == A[j][k+1]):
					p=1
					continue
				else:
					p=0
					break
	if (p):
		ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
ret = {}
for i in range(0, n):
    a = int(input())
    ret[i] = [[], []]
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        if y == 1:
            ret[i][0].append(x)
        elif y == 0:
            ret[i][1].append(x)

dic = {}


def f(honest_p, honest_list):
    if honest_p in dic:
        return []
    dic[honest_p] = True
    # print('honest_list', honest_p, honest_list)
    if ret[honest_p][0] == []:
        return [honest_p]
    temp = [honest_p] + honest_list
    for i in honest_list:
        temp += f(i, ret[i][0])
    return temp


ans = 0
for i in range(0, n):
    dic = {}
    honest = list(set(f(i, ret[i][0])))
    # print('h', honest)
    dishonest = ret[i][1]
    for a in honest:
        for b in ret[a][1]:
            if b not in dishonest:
                dishonest.append(b)
    # print('d', dishonest)
    dishonest = list(set(dishonest))
    invalid = []
    for j in range(0, n):
        if i == j or j in honest or j in dishonest:
            continue
        val = True
        for k in ret[j][1]:
            if k in honest:
                val = False
        for k in ret[j][0]:
            if k in dishonest:
                val = False
        if not val:
            invalid.append(j)
    # print('invalid', invalid)
    import itertools
    lst = list(itertools.product([0, 1], repeat=n))
    for string in lst:
        string = list(string)
        for j in invalid:
            string[j] = 0
        # print(honest, dishonest, string)
        if not val and list(set(honest) & set(dishonest)) == []:
            # print(string)
            ans = max(ans, string.count(1))
print(ans)

Submission status: Runtime Error

Solution code:
def inputlist():
	n=int(input())
	A=list()
	for i in range(n):
		Ai = int(input())
		s=list()
		for i in range(Ai):
			s += input().split()
		s = [int(i) for i in s]
		A.append(s)
	return A

A=inputlist()
n=len(A)
ans=0
for i in range(2**n):
	bit_str = str(format(i,'015b'))
	p = 0
	for j in range(n):
		if ((i >> j) & 1):
			for k in range(0,len(A[j]),2):
				if (int(bit_str[(-1*A[j][k])-1]) == A[j][k+1]):
					p = 1
					continue
				else:
					p=0
					break
	if (p):
		ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import combinations, count
 
n = int(input())
r = range(n)
a = [(set(), set()) for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y].add(x - 1)
r = next(i for i in count(n, -1) for x in map(set, combinations(r, i))
         if set.union(*(a[j][0] for j in x)).isdisjoint(x) and
         set.union(*(a[j][1] for j in x)) <= x)
print(r)