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: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    A = [0] * N
    L = [[] for _ in range(N)]
    maxans = 0

    for i in range(N):
        A[i] = int(input())
        for j in range(A[i]):
            x, y = map(int, input().split())
            x = x - 1
            L[i].append([x, y])

    for i in range(2 ** N):  # 正直者の組み合わせ全て調べる
        honest = [-1] * N
        consistent = True
        cnt = 0
        for j in range(N):
            if ((i >> j) & 1):  # jが正直者
                cnt += 1  # 正直者の数
                if honest[j] == 0:
                    consistent = False
                    break
                else:
                    honest[j] = 1

                for k in L[j]:  # 証言を全て見る
                    if k[1] == 1:  # 正直者だと言ってる
                        if honest[k[0]] == 0:  # のに本当は不正直
                            consistent = False  # 矛盾
                            break
                        else:
                            honest[k[0]] = 1  # k[0]jは正直者
                    else:
                        if honest[k[0]] == 1:
                            consistent = False
                            break
                        else:
                            honest[k[0]] = 0
            else:
                if honest[j] == 1:
                    consistent = False
                    break
                else:
                    honest[j] = 0

                for k in L[j]:
                    if k[1] == 1:  # 正直者だと言ってる（うそ）
                        if honest[k[0]] == 1:  # 本当は正直
                            consistent = False  # 矛盾
                            break
                        else:
                            honest[k[0]] = 0
                    else:
                        if honest[k[0]] == 0:
                            consistent = False
                            break
                        else:
                            honest[k[0]] = 1

        if consistent == True:
            maxans = max(maxans, cnt)

    print(maxans)


resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    A = [0] * N
    L = [[] for _ in range(N)]
    maxans = 0

    for i in range(N):
        A[i] = int(input())
        for j in range(A[i]):
            x, y = map(int, input().split())
            x = x - 1
            L[i].append([x, y])

    for i in range(2 ** N):  # 正直者の組み合わせ全て調べる
        honest = [-1] * N
        flag = True
        cnt = 0
        for j in range(N):
            if ((i >> j) & 1):  # jが正直者
                cnt += 1  # 正直者の数
                if honest[j] == 0:
                    flag = False
                    break
                else:
                    honest[j] = 1
                for k in L[j]:  # 証言を全て見る
                    if k[1] == 1:  # 正直者だと言ってる
                        if honest[k[0]] == 0:  # のに本当は不正直
                            flag = False  # 矛盾
                            break
                        else:
                            honest[k[0]] = 1  # k[0]jは正直者
                    else:
                        if honest[k[0]] == 1:
                            flag = False
                            break
                        else:
                            honest[k[0]] = 0
            else:
                if honest[j] == 1:
                    flag = False
                    break
                else:
                    honest[j] = 0

                for k in L[j]:
                    if k[1] == 1:  # 正直者だと言ってる（うそ）
                        if honest[k[0]] == 1:  # 本当は正直
                            flag = False  # 矛盾
                            break
                        else:
                            honest[k[0]] = 0
                    else:
                        if honest[k[0]] == 0:
                            flag = False
                            break
                        else:
                            honest[k[0]] = 1

        if flag == True:
            maxans = max(maxans, cnt)

    print(maxans)


resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    A = [0] * N
    L = [[] for _ in range(N)]
    maxans = 0

    for i in range(N):
        A[i] = int(input())
        for j in range(A[i]):
            x,y=map(int,input().split())
            x=x-1
            L[i].append([x,y])

    for i in range(2 ** N):  # 正直者の組み合わせ全て調べる
        honest = [-1] * N
        flag = True
        cnt = 0
        for j in range(N):
            if ((i >> j) & 1):  # jが正直者
                cnt += 1# 正直者の数
                if honest[j]==0:
                    flag=False
                    break
                for k in L[j]:#証言を全て見る
                    if k[1] == 1:# 正直者だと言ってる
                        if honest[k[0]] == 0:#のに本当は不正直
                            flag = False#矛盾
                            break
                        else:
                            honest[k[0]] = 1#k[0]jは正直者
                    else:
                        if honest[k[0]] == 1:
                            flag = False
                            break
                        else:
                            honest[k[0]] = 0
            else:
                if honest[j]==1:
                    flag=False
                    break

                for k in L[j]:
                    if k[1] == 1:# 正直者だと言ってる（うそ）
                        if honest[k[0]] == 1:#本当は正直
                            flag = False#矛盾
                            break
                        else:
                            honest[k[0]] = 0
                    else:
                        if honest[k[0]] == 0:
                            flag = False
                            break
                        else:
                            honest[k[0]] = 1

        if flag == True:
            maxans = max(maxans, cnt)

    print(maxans)


resolve()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import itertools

n = int(readline())
s = [[] for i in range(n)]
u = [[] for j in range(n)]
for j in range(n):
    a = int(readline())
    for k in range(a):
        x, y = map(int, readline().split())
        if y == 1:
            s[j].append(x)
        else:
            u[j].append(x)
bit = list(itertools.product([0, 1], repeat=n))
ans = 0
for i in range(2 ** n):
    flag = True
    memo = []
    check_s = []
    check_u = []
    for j in range(n):
        if bit[i][j] == 1:
            memo.append(j)
            check_s += s[j]
            check_u += u[j]
    if len(set(check_u) & set(memo)) == 0:
        if len(check_s) == 0 or len(set(check_s) & set(memo)):
            ans = max(ans, len(memo))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N = int(input())
evidences = [[] for _ in range(N)]
for i in range(N):
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        evidences[i].append((x-1, y))
 
result = 0
for i in range(1, 1<<N):
    consistent = True
    for j in range(N):
        if (i >> j) & 1 == 0:
            continue
        for x, y in evidences[j]:
            if (i >> x) & 1 != y:
                consintent = False
                break
        if not consistent:
            break
    if consistent:
        result = max(result, bin(i)[2:].count('1'))

print(result)

Submission status: Wrong Answer

Solution code:
N = int(input())
XY = [[] for _ in range(N)]
for i in range(N):
    A = int(input())
    for _ in range(A):
        x, y = [int(i) for i in input().split()]
        XY[i].append((x-1, y))
     
ans = [0]
for i in range(2 ** N):
    cou = 0
    for j in range(N):
        for k in range(len(XY[j])):
            if (i >> j) % 2 ==0 or (i >> XY[j][k][0]) % 2 != XY[j][k][1]:
                break
        else:
            cou += 1
    ans.append(cou)
    
print(max(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [0]*N
testi = []
assume = 2**N-1
ans = 0

for i in range(N):
    A[i] = int(input())
    if A[i] == 0:
        testi.append(-1)
    else:
        testi.append([list(map(int, input().split())) for _ in range(A[i])])

while(assume):
    flag = True
    for i in range(N):
        if assume & (2**i) != 0 and testi[i] != -1:
            for j in testi[i]:
                if j[1] != ((assume & (2**(j[0]-1))) >> (j[0]-1)):
                    flag = False
                    break
        
        if not flag:
            break
    
    assume -= 1
    if flag:
        tmp = bin(assume).count('1')
        if tmp > ans:
            ans = tmp

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [0]*N
testi = []
assume = 2**N-1
ans = 0

for i in range(N):
    A[i] = int(input())
    if A[i] == 0:
        testi.append(-1)
    else:
        testi.append([list(map(int, input().split())) for _ in range(A[i])])

while(assume):
    flag = True
    for i in range(N):
        if assume & (2**i) != 0 and testi[i] != -1:
            for j in testi[i]:
                if j[1] != ((assume & (2**(j[0]-1))) >> (j[0]-1)):
                    flag = False
                    break
        
        if not flag:
            break
    
    assume -= 1
    tmp = bin(assume).count('1')
    if tmp > ans:
        ans = tmp

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[0]*n
A=[]
for i in  range(0,n):
    l[i]=int(input())
    A.append([[0,0] for i in range(l[i])])
    for j in range(l[i]):
        A[i][j][0],A[i][j][1]=map(int,input().split())
count=0
for i in range(0,2**n):
    count1=0
    for j in range(n):
        if (i>>(n-j-1))&1:
            count1=count1+1
        for m in range(l[j]):
            if not (i>>(n-j-1))&1:
                if A[j][m][1]==(i>>(n-A[j][m][0]))&1:
                    break
            else:
                if A[j][m][1]!=(i>>(n-A[j][m][0]))&1:
                    break
        else:
            continue
        break
    else:
        if count1>count:
            count=count1
print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[0]*n
A=[]
for i in  range(0,n):
    l[i]=int(input())
    A.append([[0,0] for i in range(l[i])])
    for j in range(l[i]):
        A[i][j][0],A[i][j][1]=map(int,input().split())
count=0
for i in range(0,2**n):
    count1=0
    for j in range(n):
        if i>>(n-j-1)&1==1:
            count1=count1+1
        for m in range(l[j]):
            if (i>>(n-j-1)&1)==0:
                if A[j][m][1]==(i>>(n-A[j][m][0]))&1:
                    break
            else:
                if A[j][m][1]!=i>>(n-A[j][m][0])&1:
                    break
        else:
            continue
        break
    else:
        if count1>count:
            count=count1
print(count)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    XY = [[] for _ in range(N)]
    for i in range(N):
        A = int(input())
        for _ in range(A):
            x, y = map(int, input().split())
            XY[i].append((x-1, y))
#

    ans = 0
    for i in range(1, 2**N):
        flag = True
        cnt = 0
        for j in range(N):
            if i>>j & 1: #iのj bit shift
                cnt += 1 #iの二進表示の１の個数
                for x, y in XY[j]:
                    if i>>x & 1 != y:
                        flag = False
                        break
        if flag:
            ans = max(ans, cnt)

    print(ans)

Submission status: Wrong Answer

Solution code:
#二分探索の境界条件に良い問題かも

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    l = [[-1]*n for _ in range(n)]
    for i in range(n):
        a = int(input())
        for _ in range(a):
            x,y = map(int, input().split())
            l[i][x-1] = y
    
    res = 0
    for s in range(1<<n):
        flag = 1
        check = [-1]*n
        #i人目
        for i in range(n):
            #i人目が正直者
            if (s>>i) & 1:
                #j人目についての証言
                for j in range(n):
                    if i==j:
                        continue
                    if l[i][j] == -1:
                        continue
                    if check[j] == -1:
                        check[j] = l[i][j]
                    else:
                        if check[j] != l[i][j]:
                            flag = 0
            #i人目が嘘吐き
            else:
                #j番目の証言
                for j in range(n):
                    if i==j:
                        continue
                    if l[i][j] == -1:
                        continue
                    if check[j] == -1:
                        check[j] = l[i][j]^1
                    else:
                        if check[j] == l[i][j]:
                            flag = 0
            if flag==0:
                break
        else:
            for i in range(n):
                if check[i] == -1:
                    continue
                if ((s>>i)&1) != check[i]:
                    break
            else:
                res = max(res, bin(s).count('1'))
    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())
A = []
[A.append([]) for _ in range(N)]

for i in range(N):
    for j in range(int(input())):
        x , y = map(int,input().split())
        A[i].append([x,y])

maxT = 0

for i in range(2**N -1):
    ju = [0] * N
    ind = 0
    # trust 
    trust = 0
    for b in reversed(str(bin(i))[2::]):
        if b == "1":
            ju[ind] = 1
            trust += 1
        ind += 1
    
    flag = 0
    for n in range(N):

        if ju[n] == 0:
            continue

        for  y in A[n]:
            if ju[y[0]-1] != y[1]:
                flag = 1
                break
        
        if flag == 1:
            break
        
    if flag == 0:
        maxT = max(maxT , trust )

print(maxT)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
for _ in range(n):
  a_i = int(input())
  tmp = []
  for __ in range(a_i):
    tmp.append(list(map(int, input().split())))
  a.append(tmp)
ans = 0
for i in range(n):
  t = [-1] * n
  t[i] = 1
  for j in range(len(a[i])):
    t[a[i][j][0]-1] = a[i][j][1]
  flag = 1
  for j in range(n):
    if i == j or t[j] == 0:
      continue
    for k in range(len(a[j])):
      p, q = a[j][k]
      if (t[p-1]==1 and q==0 or t[p-1]==0 and q==1) and t[j] == 1:
        flag = 0
      t[p-1] = max(q, t[p-1])
    if flag == 0:
      t = [-1] * n
      break
  ans = max(ans, sum(t))
print(ans)

Submission status: Wrong Answer

Solution code:
# N = int(input())
#
# ans = []
# for i in range(N):
#     A = int(input())
#     for j in range(A):
#         ans.append(list(map(int, input().split())))
#
# print(ans)

print(bin(1 << 15))
print(1 << 15)
print(2**15)
n= int(input())
shogens = []
for i in range(n):
    a = int(input())
    shogens.append([])
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        shogens[i].append((x, y))
print(shogens)

# def is_honest(i, j):
#     return (i >> j) % 2 == 1
#
# def honest_cnt(i):
#     ans = 0
#     for j in range(n):
#         ans += is_honest(i, j)
#     return ans
# ans = 0
#
# for i in range(1 << n):
#     ok = True
#     print(bin(i))
#     for j in range(n):
#         if not is_honest(i, j):continue
#         for (x, y) in shogens[j]:
#             if y == 0 and is_honest(i, x):ok = False
#             if y == 1 and not is_honest(i, x):ok = False
#
#     if ok:
#         ans = max(ans, honest_cnt(i))
#
# print("ans", ans)

lists = {i : 0 for i in range(1 << 15)}
for i in range(1 << 15):
    count = 0
    for j in range(n):
        if (i >> j) & 1:
            for x, y in shogens[j]:
                if y == 0 and (i >> x) & 1: count -= 1
                if y == 1 and not (i >> x) & 1: count -= 1
    if count == 0:
        ans = 0
        for k in range(n):
            ans += (i >> k) % 2
        lists[i] = ans

print(max(lists.values()))
# print(0 >> 0)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
XY = [[] for _ in range(N)]
for i in range(N):
    a = ir()
    for j in range(a):
        x, y = lr()
        XY[i].append((x-1, y)) # 0-indexedとして

print(XY)        
A = np.array(list(itertools.product([0, 1], repeat=N)), np.bool)
for i in range(N):
    for x, y in XY[i]:
        print(i, '-----')      
        print(A)
        bl = (~A[:, i]) | (A[:, x] == bool(y))
        A = A[bl]

print(A)
answer = np.sum(A, axis=1).max()
print(answer)
# 24 repeat

Submission status: Wrong Answer

Solution code:
N=int(input())

A=[[-1]*N for _ in range(N)]
for i in range(N):
  a=int(input())
  for j in range(a):
    x,y=map(int, input().split())
    A[j][x-1]=y
#正直者が正直者に不親切と言われていない
#→正直ものが不親切を正直者と言っていないか
ans=0
for i in range(2**N):
  ok=True
  for j in range(N):
    if (i>>j&1)==1:
      for k in range(N):
        if A[j][k]!=-1 and (i>>k&1)!=A[j][k]:
          ok=False
  if ok:
    ans=max(ans, bin(i).count("1"))
  
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())

A=[[-1]*N for _ in range(N)]
for i in range(N):
  a=int(input())
  for j in range(a):
    x,y=map(int, input().split())
    A[a][x-1]=y
#正直者が正直者に不親切と言われていない
#→正直ものが不親切を正直者と言っていないか
ans=0
for i in range(2**N):
  ok=True
  for j in range(N):
    if (i>>j&1)==1:
      for k in range(N):
        if A[j][k]!=-1 and (i>>k&1)!=A[j][k]:
          ok=False
  if ok:
    ans=max(ans, bin(i).count("1"))
  
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())

A=[[-1]*N for _ in range(N)]
for i in range(N):
  a=int(input())
  for j in range(a):
    x,y=map(int, input().split())
    A[a][x-1]=y
#正直者が正直者に不親切と言われていない
#→正直ものが不親切を正直者と言っていないか
ans=0
for i in range(2**N):
  ok=True
  for j in range(N):
    if i>>j&1==1:
      for k in range(N):
        if A[j][k]!=-1 and i>>k&1!=A[j][k]:
          ok=False
          break
  if ok:
    ans=max(ans, bin(i).count("1"))
  
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
g=[[-1]*N for _ in range(N)]
ans=0
for i in range(N):
    A=int(input())
    for _ in range(A):
        x,y=map(int,input().split())
        g[i][x-1]=y
for s in range(2**N):
    flag=1
    for i in range(N):
        if (s>>i&1):
            for j in range(N):
                if g[i][j]!=-1 and (s>>j&1)==g[i][j]:
                    flag=0
                    break
        if flag==0:break
    if flag==1:
        t=0
        x=s
        while x>0:
            t+=x%2
            x//=2
        ans=max(ans,t)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
g=[[-1]*N for _ in range(N)]
ans=0
for i in range(N):
    A=int(input())
    for _ in range(A):
        x,y=map(int,input().split())
        g[i][x-1]=y
for s in range(2**N):
    flag=1
    for i in range(N):
        if (s>>i&1):
            for j in range(N):
                if g[i][j]==0 and (s>>j&1):
                    flag=0
                    break
                if flag==0:
                    break
    if flag==1:
        t=0
        x=s
        while x>0:
            t+=x%2
            x//=2
        ans=max(ans,t)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
g=[[-1]*N for _ in range(N)]
ans=0
for i in range(N):
    A=int(input())
    for _ in range(A):
        x,y=map(int,input().split())
        g[i][x-1]=y
for s in range(2**N):
    flag=1
    for i in range(N):
        if (s>>i)==1:
            for j in range(N):
                if g[i][j]!=-1 and (s>>j)!=g[i][j]:
                    flag=0
    if flag==1:
        t=0
        x=s
        while x>0:
            t+=x%2
            x//=2
        ans=max(ans,t)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
lst=[[] for _ in range(N)]
for i in range(N):
  for j in range(int(input())):
    x,y=map(int,input().split())
    x-=1
    lst[i].append([x,y])
ans=0
for i in range(2**N):
  honest=[]
  unkind=[]
  flag=0
  for j in range(N):
    if (i>>j)&1:
      honest.append(j)
    else:
      unkind.append(j)
  for p in honest:
    for l in lst[p]:
      x,y=l[0],l[1]
      if y:
        if x in unkind:
          flag=1
          break
      else:
        if x in honest:
          flag=1
          break
  for p in unkind:
    for l in lst[p]:
      x,y=l[0],l[1]
      if y:
        if x in honest:
          flag=1
          break
      else:
        if x in unkind:
          flag=1
          break
  if flag!=1:
    ans=max(ans,len(honest))
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
lst=[[] for _ in range(N)]
for i in range(N):
  for j in range(int(input())):
    x,y=map(int,input().split())
    x-=1
    lst[i].append([x,y])
ans=0
for i in range(2**N):
  honest=[]
  unkind=[]
  flag=0
  for j in range(N):
    if (i>>j)&1:        # jは正直者
      if j in unkind or flag:
        flag=1
        break
      if j not in honest:
        honest.append(j)
      for l in lst[j]:
        x,y=l[0],l[1]
        if y:
          if x in unkind:
            flag=1
            break
          if x not in honest:
            honest.append(x)
        else:
          if x in honest:
            flag=1
            break
          if x not in unkind:
            unkind.append(x)
    else:
      if j in honest or flag:
        flag=1
        break
      if j not in unkind:
        unkind.append(j)
      for l in lst[j]:
        x,y=l[0],l[1]
        if y:
          if x in honest:
            flag=1
            break
          if x not in unkind:
            unkind.append(x)
        else:
          if x in unkind:
            flag=1
            break
          if x not in honest:
            honest.append(x)
  if flag!=1:
    ans=max(ans,len(honest))
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
g=[[-1]*N for _ in range(N)]
ans=0
for i in range(N):
    A=int(input())
    for _ in range(A):
        x,y=map(int,input().split())
        g[i][x-1]=y
for s in range(2**N):
    flag=1
    for i in range(N):
        if (s>>i)==1:
            for j in range(N):
                if g[i][j]!=-1 and (s>>j&1)!=g[i][j]:
                    flag=0
    if flag==1:
        t=0
        x=s
        while x>0:
            t+=x%2
            x//=2
        ans=max(ans,t)
print(ans)

Submission status: Wrong Answer

Solution code:
def get(L, x, flag):
    if flag == 1:
        for i in range(len(x)):
            if not (L >> x[i][0]) & x[i][1]:
                return False
    else:
        for i in range(len(x)):
            if (L >> x[i][0]) & x[i][1]:
                return False
    return True


N = int(input())
x = []
for _ in range(N):
    A = int(input())
    y = []
    for _ in range(A):
        xi, yi = map(int, input().split())
        y.append([xi-1, yi])
    x.append(y)
result = []
for i in range(1 << N):
    for j in range(N):
        if not get(i, x[j], i >> j & 1):
            break
    else:
        result.append(i)
maxCount = 0
for i in result:
    count = 0
    for j in range(N):
        if i >> j & 1:
            count += 1
    maxCount = max(maxCount, count)

print(maxCount)

Submission status: Wrong Answer

Solution code:
N = int(input())

X = [[-1]*N for i in range(N)]
for i in range(N):
    a = int(input())
    for j in range(a):
        b, c = map(int, input().split())
        X[i][b-1] = c
ans = 0
for i in range(2**N):
    Y = [0]*(N)
    for j in range(N):
        if ((i >> j) & 1):
            Y[j] = 1
    for j in range(N):
        if Y[j] == 1:
            for k in range(N):
                if X[j][k] == -1:
                    continue
                if X[j][k] != Y[k]:
                    ans = 0
    ans = max(ans, sum(Y))

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

X = [[-1]*N for i in range(N)]
for i in range(N):
    a = int(input())
    for j in range(a):
        b, c = map(int, input().split())
        X[i][b-1] = c
ans = 0
for i in range(2**N):
    Y = [0]*(N)
    for j in range(N):
        if ((i >> j) & 1):
            Y[j] = 1
    for j in range(N):
        if Y[j] == 1:
            for k in range(N):
                if X[j][k] == -1:
                    continue
                if X[j][k] != Y[k]:
                    Y[j] = 0
    ans = max(ans, sum(Y))

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

X = [[-1]*N for i in range(N)]
for i in range(N):
    a = int(input())
    for j in range(a):
        b, c = map(int, input().split())
        X[i][b-1] = c
ans = 0
for i in range(2**N):
    Y = [0]*(N)
    for j in range(N):
        if ((i >> j) & 1):
            Y[j] = 1
    for j in range(N):
        if Y[j] == 1:
            for k in range(N):
                if X[j][k] == -1:
                    continue
                if X[j][k] != Y[k]:
                    Y[j] = 0
    print(Y)
    ans = max(ans, sum(Y))

print(ans)

Submission status: Wrong Answer

Solution code:
def get(L, x, flag):
    if flag:
        for i in range(len(x)):
            if not (L >> x[i][0]) & x[i][1]:
                return False
    else:
        for i in range(len(x)):
            if (L >> x[i][0]) & x[i][1]:
                return False
    return True


N = int(input())
x = []
for _ in range(N):
    A = int(input())
    y = []
    for _ in range(A):
        xi, yi = map(int, input().split())
        y.append([xi-1, yi])
    x.append(y)
result = []
for i in range(1 << N):
    for j in range(N):
        if not get(i, x[j], i >> j & 1):
            break
    else:
        result.append(i)
maxCount = 0
for i in result:
    count = 0
    for j in range(N):
        if i >> j & 1:
            count += 1
    maxCount = max(maxCount, count)

print(maxCount)

Submission status: Wrong Answer

Solution code:
N = int(input())

X = [[-1]*N for i in range(N)]
for i in range(N):
    a = int(input())
    for j in range(a):
        b, c = map(int, input().split())
        X[i][b-1] = c
ans = 0
for i in range(2**N):
    Y = [0]*(N)
    for j in range(N):
        if ((i >> j) & 1):
            Y[j] = 1
    for j in range(N):
        if Y[j] == 1:
            for k in range(N):
                if X[j][k] == -1:
                    continue
                if X[j][k] != Y[j]:
                    Y[j] = 0
    ans = max(ans, sum(Y))

print(ans)

Submission status: Wrong Answer

Solution code:
def is_consistent(bit, testimony):
    all_consistence = True
    for shift in range(n):
        mask, tf = testimony[shift]
        if (bit & mask) != (tf & mask):
            all_consistence = False
    if all_consistence:
        return True
    else:
        return False

n = int(input())
testimony = [0] * n
for i in range(n):
    mask, tf = 0, 0
    for j in range(int(input())):
        x, y = map(int, input().split())
        mask += 1 << (x - 1)
        tf += y << (x - 1)
    testimony[i] = (mask, tf)

max_honest = 0
for bit in range(1 << n):
    if is_consistent(bit, testimony) and (max_honest < bin(bit).count('1')):
        max_honest = bin(bit).count('1')
print(max_honest)

Submission status: Wrong Answer

Solution code:
def is_consistent(bit, t_tuple):
    mask, tf = t_tuple
    if (bit & mask) == (tf & mask):
        return True
    else:
        return False

n = int(input())
testimony = [0] * n
for i in range(n):
    mask, tf = 0, 0
    for j in range(int(input())):
        x, y = map(int, input().split())
        mask += 1 << (x - 1)
        tf += y << (x - 1)
    testimony[i] = (mask, tf)

max_honest = 0
for bit in range(1 << n):
    honest = 0
    for shift in range(n):
        if ((bit >> shift) & 1):
            if is_consistent(bit, testimony[shift]):
                honest += 1
            else:
                break
    if max_honest < honest:
        max_honest = honest
print(max_honest)

Submission status: Wrong Answer

Solution code:
def is_consistent(bit, t_tuple):
    mask, tf = t_tuple
    if (bit & mask) == (tf & mask):
        return True
    else:
        return False

n = int(input())
testimony = [0] * n
for i in range(n):
    mask, tf = 0, 0
    for j in range(int(input())):
        x, y = map(int, input().split())
        mask += 1 << (x - 1)
        tf += y << (x - 1)
    testimony[i] = (mask, tf)

max_honest = 0
for bit in range(1 << n):
    honest = 0
    for shift in range(n):
        if ((bit >> shift) & 1):
            if is_consistent(bit, testimony[shift]):
                honest += 1
            else:
                break
    if max_honest < honest:
        max_honest = honest
        print(bin(bit))
print(max_honest)

Submission status: Wrong Answer

Solution code:
def is_contradictory(bit, t_tuple):
    mask, tf = t_tuple
    if (bit & mask) == (tf & mask):
        return True
    else:
        return False

n = int(input())
testimony = [0] * n
for i in range(n):
    mask, tf = 0, 0
    for j in range(int(input())):
        x, y = map(int, input().split())
        mask += 1 << (x - 1)
        tf += y << (x - 1)
    testimony[i] = (mask, tf)

max_honest = 0
for bit in range(1 << n):
    honest = 0
    for shift in range(n):
        if ((bit >> shift) & 1):
            if is_contradictory(bit, testimony[shift]):
                break
            else:
                honest += 1
    if max_honest < honest:
        max_honest = honest
print(max_honest)