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:
import itertools
N = int(input())
lis_hl = list(itertools.product('01',repeat = N))
#1正直者 　0嘘つき
A = []
X = []
for i in range(N):
    A.append(int(input()))
    Y =[]
    for j in range(A[-1]):
        Y.append(list(map(int,input().split())))
    X.append(Y)
honesty = 0
for hl in lis_hl:#honesty laier list
    #print(" ")
    #print(" ")
    #print("仮定検証：hl:" + str(hl))
    #print(" ")
    flag = 0
    for i in range(N):#人について探査
        if flag == 0:
            is_hl = hl[i]# これから証言するひとは正直者か
            if is_hl == '1':
                pluse= 0
            else:
                pluse = 1
                
            for xi in X[i]:#証言を全探索
                #print(' X[i]:' + str(X[i]) +' xi:' + str(xi) + ' hl:' + str(hl) + ' i:' + str(i))
                #print(' xi[0]:' + str(xi[0]) + ' xi[1]:' + str(xi[1]) + ' xi[1] + pluse)%2:' + str((xi[1] + pluse)%2) +' hl[xi[0]-1]:' + str(hl[xi[0]-1]))
                #print(' ')
                if ((xi[1] + pluse)%2)!= int(hl[xi[0]-1]):
                    #print('証言が仮定に反します')
                    #print(' ')
                    flag = 1
                    break
    #print("flag:" +str(flag))
    #print(" ")
    if flag == 0:
        #print("hl:" +str(hl))
        honesty = max(honesty,hl.count('1'))
        #print("honesty:" +str(honesty) + " hl.count('1'):" +str(hl.count('1')))
        #print(' ')
print(honesty)

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
lis_hl = list(itertools.product('01',repeat = N))
A = []
X = []
for i in range(N):
    A.append(int(input()))
    Y =[]
    for j in range(A[-1]):
        Y.append(list(map(int,input().split())))
    X.append(Y)
honesty = 0
for hl in lis_hl:#honesty laier list
    print(" ")
    print(" ")
    print("仮定検証：hl:" + str(hl))
    print(" ")
    flag = 0
    for i in range(N):#人について探査
        if flag == 0:
            is_hl = hl[i]# これから証言するひとは正直者か
            if is_hl == '1':
                pluse= 0
            else:
                pluse = 1
                
            for xi in X[i]:#証言を全探索
                if ((xi[1] + pluse)%2)!= int(hl[xi[0]-1]):
                    print('証言が仮定に反します')
                    print(' ')
                    flag = 1
                    break
    if flag == 0:
        #print("hl:" +str(hl))
        honesty = max(honesty,hl.count('1'))
print(honesty)

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
lis_hl = list(itertools.product('01',repeat = N))
A = []
X = []
for i in range(N):
    A.append(int(input()))
    Y =[]
    for j in range(A[-1]):
        Y.append(list(map(int,input().split())))
    X.append(Y)
honesty = 0
for hl in lis_hl:#honesty laier list
    flag = 0
    for i in range(N):#人について探査
        if flag == 0:
            is_hl = hl[i]# これから証言するひとは正直者か
            if is_hl == '1':
                pluse= 0
            else:
                pluse = 1
                
            for xi in X[i]:#証言を全探索
                if ((xi[1] + pluse)%2)!= int(hl[xi[0]-1]):
                    flag = 1
                    break
    if flag == 0:
        #print("hl:" +str(hl))
        honesty = max(honesty,hl.count('1'))
print(honesty)

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
lis_hl = list(itertools.product('01',repeat = N))
#1正直者 　0嘘つき
A = []
X = []
for i in range(N):
    A.append(int(input()))
    Y =[]
    for j in range(A[-1]):
        Y.append(list(map(int,input().split())))
    X.append(Y)
honesty = 0
for hl in lis_hl:#honesty laier list
    flag = 0
    for i in range(N):#人について探査
        is_hl = hl[i]# これから証言するひとは正直者か
        if is_hl == '1':
            pluse= 0
        else:
            pluse = 1
            
        for xi in X[i]:#証言を全探索
            #print(' X[i]:' + str(X[i]) + ' lis_hl[hl]:' + str(hl) + ' i:' + str(i))
            #print(' i:' + str(i) + ' X[i][xi][1]:' + str(xi[1]) + ' hl[xi[0]-1]:' + str(hl[xi[0]-1]))
            #print(' ')
            if ((xi[1] + pluse)%2)!= int(hl[xi[0]-1]):
                #print('証言が仮定に反します')
                #print(' ')
                flag = 1
    #print("flag:" +str(flag))
    if flag == 0:
        #print("hl:" +str(hl))
        honesty = max(honesty,hl.count('1'))
print(honesty)

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
lis_hl = list(itertools.product('01',repeat = N))
#1正直者 　0嘘つき
A = []
X = []
for i in range(N):
    A.append(int(input()))
    Y =[]
    for j in range(A[-1]):
        Y.append(list(map(int,input().split())))
    X.append(Y)
honesty = 0
for hl in lis_hl:#honesty laier list
    flag = 0
    for i in range(N):#人について探査
        is_hl = hl[i]# これから証言するひとは正直者か
        if is_hl == '1':
            pluse= 0
        else:
            pluse = 1
            
        for xi in X[i]:#証言を全探索
            #print(' X[i]:' + str(X[i]) + ' lis_hl[hl]:' + str(hl) + ' i:' + str(i))
            #print(' i:' + str(i) + ' X[i][xi][1]:' + str(xi[1]) + ' hl[xi[0]-1]:' + str(hl[xi[0]-1]))
            #print(' ')
            if ((xi[1] + pluse)%2)!= int(hl[xi[0]-1]):
                #print('証言が仮定に反します')
                #print(' ')
                flag = 1
                break
    #print("flag:" +str(flag))
    if flag == 0:
        #print("hl:" +str(hl))
        honesty = max(honesty,hl.count('1'))
print(honesty)

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
lis_hl = list(itertools.product('01',repeat = N))
#1正直者 　0嘘つき
A = []
X = []
for i in range(N):
    A.append(int(input()))
    Y =[]
    for j in range(A[-1]):
        Y.append(list(map(int,input().split())))
    X.append(Y)
honesty = 0
for hl in range(len(lis_hl)):#honesty laier list
    flag = 0
    for i in range(N):#人について探査
        is_hl = lis_hl[hl][i]# これから証言するひとは正直者か
        if is_hl == '1':
            pluse= 0
        else:
            pluse = 1
            
        for xi in range(len(X[i])):#証言を全探索
            #print(' X[i]:' + str(X[i]) + ' lis_hl[hl]:' + str(lis_hl[hl]) + ' i:' + str(i))
            #print(' i:' + str(i) + ' X[i][xi][1]:' + str(X[i][xi][1]) + ' lis_hl[hl][X[i][xi][0]-1:' + str(lis_hl[hl][X[i][xi][0]-1]))
            #print(' ')
            if ((X[i][xi][1] + pluse)%2)!= int(lis_hl[hl][X[i][xi][0]-1]):
                #print('証言が仮定に反します')
                #print(' ')
                flag = 1
                break
    #print("flag:" +str(flag))
    if flag == 0:
        #print("lis_hl[hl]:" +str(lis_hl[hl]))
        honesty = max(honesty,lis_hl[hl].count('1'))
print(honesty)

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
xys=[]
for i in range(N):
    A = int(input())
    xy = []
    for i in range(A):
        xy.append(list(map(int,input().split())))
    xys.append(xy)
#print('xys:', xys)  ############


#正直者1,  不親切0
a = [0,1]
Ls = list(itertools.product(a, repeat=N))
#print('Ls:', Ls)  ###########

mujun=[0]*(N+1)
count=0
ans=0
for L in Ls:
    #print('L:        ', L)  ###########
    hito=1
    count=0
    mujun=[0]*(N+1)
    for i in L:

        #print('i:', i)    ###########
        if i==1:
            for xy in xys[hito-1]:
                #print('xy:', xy)  #########
                if xy[1] == 1:
                    count+=1
                    mujun[xy[0]]=1
                else:
                    if mujun[xy[0]]==1:
                        count=0
                        #print('mujuuuuuuuuuuuuuuuuuuuun!')   ###########
                        break
                #print('count:', count)  ###########
                #print('mujun:', mujun)  ###########
            ans=max(ans,count)
            #print('ans:', ans)  ###########

        hito+=1

#print('ans:', ans) ###########
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
xy=[[] for i in range(n)]
for i in range(n):
  a=int(input())
  for j in range(a):
    x,y=map(int,input().split())
    x-=1
    xy.append((x,y))
ans=0
for i in range(1<<n):
  cnt=bin(i).count("1")
  if cnt<=ans:continue
  for j in range(n):
    if i&(1<<j):
      for x,y in xy[j]:
        if y==1 and i&(1<<x):continue
        if y==0 and i&(1<<x)==0:continue
        break
      else:
        continue
      break
  else:
    ans=cnt
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

a_list = []
for _ in range(n):
  mini_list = []
  a = int(input())
  for _ in range(a):
    mini_list.append(list(map(int, input().split())))
  a_list.append(mini_list)

ans = 0
for i in range(n**2):
  ans_list = [0]*n
  while i!=0:
    ans_list[i%2] = 1
    i//=2
  flg = True
  for j, syogens in enumerate(a_list):
    if ans_list[j]!=0:
      pass
    else:
      for syogen in syogens:
        person = syogen[0]-1
        status = syogen[1]
        if ans_list[person] != status:
          flg=False
  if flg:
    ans = max(ans,sum(ans_list))
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
xy=[[]for i in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        x-=1
        xy[i].append([x,y])
ans=0
for i in range(2**n):
    flg=True
    tmp=[-1 for i in range(n)]
    tt=0
    for j in range(n):
        if (i>>j)&1:
            tmp[j]=1
            tt+=1
            for x,y in xy[j]:
                if tmp[x]==-1:
                    tmp[x]=y
                else: 
                    if tmp[x]!=y:
                        flg=False
    if flg:
        if tt>ans:
            ans=tt
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


def do_code():
    num = int(input())
    matrix = [[2] * (num + 1) for _ in range(num + 1)]
    honests = [set() for _ in range(num + 1)]
    unkinds = [set() for _ in range(num + 1)]
    # 人iは1〜Nのためインデックス0は使わずに1~Nで使うようにする
    for n in range(1, num + 1):
        u = set()
        h = set()
        ans = int(input())
        for a in range(ans):
            x, y = map(int, input().split(" "))
            if y == 1:
                h.add(x)
            else:
                u.add(x)
        honests[n] = h
        unkinds[n] = u
    count = 0
    for j in range(1, num + 1):
        # 1~Nまで順番に1人ずつ正直者であると仮定して、他の組み合わせすべてを試す
        u = unkinds[j]
        h = honests[j]
        contradiction = True
        # jを除く各人について、正直者であると仮定したときに矛盾が生じるかどうかをチェックする
        for i in range(1, num + 1):
            if i == j:
                continue
            tu = set()
            th = set()
            th.add(i)
            isOk = True
            queue = deque(honests[i])
            visited = {i}
            while len(queue) > 0:
                t = queue.popleft()
                if t in visited:
                    continue
                visited.add(t)
                if t in th or t in h:
                    continue
                if t in tu or t in u:
                    # 現在の仮定と矛盾するため、人物iをhonestと仮定できない
                    isOk = False
                    break
                queue.extend(honests[t])
                th |= honests[t]
                tu |= unkinds[t]
            if not isOk:
                continue
            for unkind in unkinds[i]:
                # iを正直者と仮定するため、unkindと証言している人物はunkindであると仮定する
                # ただし現在の仮定と矛盾する場合は人物iをhonestとすると矛盾が生じる
                # unkindについてはunkindと証言されている人物の発言までチェックする必要はない
                if unkind not in th and unkind not in h:
                    tu.add(unkind)
                else:
                    isOk = False
                    break
            if isOk:
                contradiction = False
                h |= th
                u |= tu
        if not contradiction:
            count = max(count, len(h))
    print(count)


if __name__ == '__main__':
    do_code()

Submission status: Wrong Answer

Solution code:
from collections import deque


def do_code():
    num = int(input())
    matrix = [[2] * (num + 1) for _ in range(num + 1)]
    honests = [set() for _ in range(num + 1)]
    unkinds = [set() for _ in range(num + 1)]
    # 人iは1〜Nのためインデックス0は使わずに1~Nで使うようにする
    for n in range(1, num + 1):
        u = set()
        h = set()
        ans = int(input())
        for a in range(ans):
            x, y = map(int, input().split(" "))
            if y == 1:
                h.add(x)
            else:
                u.add(x)
        honests[n] = h
        unkinds[n] = u
    count = 0
    for j in range(1, num + 1):
        # 1~Nまで順番に1人ずつ正直者であると仮定して、他の組み合わせすべてを試す
        u = unkinds[j]
        h = honests[j]
        contradicction = True
        # jを除く各人について、正直者であると仮定したときに矛盾が生じるかどうかをチェックする
        for i in range(1, num + 1):
            if i == j:
                continue
            tu = set()
            th = set()
            th.add(i)
            isOk = True
            queue = deque(honests[i])
            visited = {i}
            while len(queue) > 0:
                t = queue.popleft()
                if t in visited:
                    continue
                visited.add(t)
                if t in th or t in h:
                    continue
                if t in tu or t in u:
                    isOk = False
                    break
                if honests[t].isdisjoint(tu) or unkinds[t].isdisjoint(th) or honests[t].isdisjoint(u) or unkinds[t].isdisjoint(h):
                    isOk = False
                    break
                queue.extend(honests[t])
                th |= honests[t]
                tu |= unkinds[t]
            if not isOk:
                continue
            for unkind in unkinds[i]:
                if unkind not in th and unkind not in h:
                    tu.add(unkind)
                else:
                    isOk = False
                    break
            if isOk:
                contradicction = False
                h |= th
                u |= tu
        if not contradicction:
            count = max(count, len(h))
    print(count)


if __name__ == '__main__':
    do_code()

Submission status: Wrong Answer

Solution code:
from collections import deque


def do_code():
    num = int(input())
    matrix = [[2] * (num + 1) for _ in range(num + 1)]
    honests = [set() for _ in range(num + 1)]
    unkinds = [set() for _ in range(num + 1)]
    # 人iは1〜Nのためインデックス0は使わずに1~Nで使うようにする
    for n in range(1, num + 1):
        u = set()
        h = set()
        ans = int(input())
        for a in range(ans):
            x, y = map(int, input().split(" "))
            if y == 1:
                h.add(x)
            else:
                u.add(x)
        honests[n] = h
        unkinds[n] = u
    count = 0
    for j in range(1, num + 1):
        u = unkinds[j]
        h = honests[j]
        contradicction = True
        for i in range(1, num + 1):
            if i == j:
                continue
            tu = set()
            th = set()
            th.add(i)
            isOk = True
            queue = deque(honests[i])
            visited = {i}
            while len(queue) > 0:
                t = queue.popleft()
                if t in visited:
                    continue
                visited.add(t)
                if t in th:
                    continue
                if t in tu:
                    isOk = False
                    break
                if honests[t].isdisjoint(tu) or unkinds[t].isdisjoint(th):
                    isOk = False
                    break
                queue.extend(honests[t])
                th |= honests[t]
                tu |= unkinds[t]
            if not isOk:
                continue
            for unkind in unkinds[i]:
                if unkind not in th and unkind not in h:
                    tu.add(unkind)
                else:
                    isOk = False
                    break
            if isOk:
                contradicction = False
                h |= th
                u |= tu
        if not contradicction:
            count = max(count, len(h))
    print(count)


if __name__ == '__main__':
    do_code()

Submission status: Wrong Answer

Solution code:
from collections import deque


def do_code():
    num = int(input())
    matrix = [[2] * (num + 1) for _ in range(num + 1)]
    honests = [set() for _ in range(num + 1)]
    unkinds = [set() for _ in range(num + 1)]
    # 人iは1〜Nのためインデックス0は使わずに1~Nで使うようにする
    for n in range(1, num + 1):
        u = set()
        h = set()
        ans = int(input())
        for a in range(ans):
            x, y = map(int, input().split(" "))
            if y == 1:
                h.add(x)
            else:
                u.add(x)
        honests[n] = h
        unkinds[n] = u
    count = 0
    for j in range(1, num + 1):
        u = unkinds[j]
        h = honests[j]
        contradicction = True
        for i in range(1, num + 1):
            tu = set()
            th = set()
            th.add(i)
            isOk = True
            queue = deque(honests[i])
            visited = {i}
            while len(queue) > 0:
                t = queue.popleft()
                if t in visited:
                    continue
                visited.add(t)
                if honests[t].isdisjoint(tu) or unkinds[t].isdisjoint(th):
                    isOk = False
                    break
                queue.extend(honests[t])
                th |= honests[t]
                tu |= unkinds[t]
            if not isOk:
                continue
            for unkind in unkinds[i]:
                if unkind not in th and unkind not in h:
                    tu.add(unkind)
                else:
                    isOk = False
                    break
            if isOk:
                contradicction = False
                h |= th
                u |= tu
        if not contradicction:
            count = max(count, len(h))
    print(count)


if __name__ == '__main__':
    do_code()

Submission status: Wrong Answer

Solution code:
import copy
n = int(input())
tst = [[] for i in range(n)]
for i in range(n):
  a = int(input())
  for j in range(a):
    x,y = map(int,input().split())
    tst[i].append([x,y])
ans = 0
for bit in range(1<<n):
  liars = [0]*n
  conds = copy.deepcopy(tst)
  check = 1
  for i in range(n):
    if (bit>>i)&1:
      liars[-1-i] = 1
      continue
    for l in conds[-1-i]:
      l[1] = not l[1]
  for tests in conds:
    for l in tests:
      if l[1] != liars[l[0]-1]:
        check = 0
  temp = 0
  if check:
    temp = sum(liars)
  ans = max(ans,temp)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

testimonies = []
for idx1 in range(n):
    testimony = []
    count = int(input())
    for idx2 in range(count):
        x,y = map(int, input().split())
        testimony.append((x-1, y)) 
    testimonies.append(testimony)

output = 0
for combination in range(2 ** n):
    consistent = True
    for index in range(n):
        if (combination >> index) & 1 == 0:
            continue
        for x,y in testimonies[index]:
            if (index >> x) & 1 != y:
                consistent = False
                break
        if not consistent:
            break
    if consistent:
        output = max(output, bin(combination)[2:].count("1"))
print(output)

Submission status: Wrong Answer

Solution code:
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N = I()
A = []
xy = [[] for i in range(N)]
for i in range(N):
    A.append(I())
    for j in range(A[i]):
        x,y = LI()
        xy[i].append([x-1,y])

# 人は0-index
# 各人が正直者か不親切な人かで全探索、1…正直者、0…不親切な人

ans = 0
for i in range(2**N):
    B = [[] for _ in range(N)]
    a = 0  # 正直者の人数
    for j in range(N):
        if (i>>j) & 1:
            B[j].append(1)
            a += 1
            for k in range(A[j]):
                B[xy[j][k][0]].append(xy[j][k][1])
        else:
            B[j].append(0)
            for k in range(A[j]):
                B[xy[j][k][0]].append(1-xy[j][k][1])
    if sum(len(set(B[j])) for j in range(N)) != N:  # この場合矛盾
        continue
    else:
        ans = max(ans,a)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
evidence = [[] for _ in range(N)]
for i in range(N):
  A = int(input())
  for _ in range(A):
    x,y = map(int,input().split())
    evidence[i].append((x-1,y))
result = 0
for j in range(1,2**N):
  consistent = True
  for k in range(N):
    if (j >> k) & 1 == 0:
      continue
    for x,y in evidence[k]:
      if (j >> x) & 1 != y:
        consistent = 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())
evidence = [[] for _ in range(N)]
for i in range(N):
  A = int(input())
  for _ in range(A):
    x,y = map(int,input().split())
    evidence[i].append((x-1,y))
result = 0
for j in range(1,2**N):
  consistent = True
  for k in range(N):
    if (j >> k) & 1 == 0:
      continue
    for x,y in evidence[k]:
      if (j >> x) & 1 != y:
        consistent = False
        break
    if not consistent:
      break
  else:
    result = max(result, bin(i)[2:].count("1"))
print(result)

Submission status: Wrong Answer

Solution code:
from itertools import product
N = int(input())
A = []
shougen = []
for i in range(N):
    a = int(input())
    A.append(a)
    ls = []
    for j in range(a):
        ls.append([int(k) for k in input().split()])
    shougen.append(ls)
truth = [0, 1]
ans = 0
for x in product(truth, repeat=N):
    num = 0
    for i, y in enumerate(x):
        if y == 1:
            cur = 0
            for z in shougen[i]: 
                if x[z[0]-1] == z[1]:
                    cur += 1
            if cur == A[i]:
                num += 1
    ans = max(ans, num)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product
N = int(input())
A = []
shougen = []
for i in range(N):
    a = int(input())
    A.append(a)
    ls = []
    for j in range(a):
        ls.append([int(k) for k in input().split()])
    shougen.append(ls)
truth = [0, 1]
ans = 0
for x in product(truth, repeat=N):
    num = 0
    for i, y in enumerate(x):
        if y == 1:
            for z in shougen[i]:
                if x[z[0]-1] != z[1]:
                    break
                num += 1
    ans = max(ans, num)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
from collections import defaultdict
A = dict()
xy = []
for i in range(N):
    A = int(input())
    xy_tmp = [input().split() for i in range(A)]
    xy.append(xy_tmp)

# print(xy)

# 全探索でいけそう
# 矛盾した時点で切る
import copy
ans = [0]

def dfs(tmp_dict,index,cnt):
    # print(tmp_dict,cnt)
        
    if index == N:
        # sum_ = 0
        # for value in list(tmp_dict.values()):
        #     sum_ += int(value)
            

        ans[0] = max(ans[0],cnt)
        return ans
    
    # 本当だった場合
    true_dict = tmp_dict.copy()
    flag = True
    if str(index + 1) in true_dict:
        if true_dict[str(index + 1)] != "1":
            flag = False
    
    else:
        true_dict[str(index + 1)] = "1"
    for ele in xy[index]:
        if ele[0] in true_dict:
            if true_dict[ele[0]] != ele[1]:
                flag = False
                break
        else:
            true_dict[ele[0]] = ele[1]


    if flag:
        dfs(true_dict,index+1,cnt+1)

    # 嘘だった場合
    false_dict = tmp_dict.copy()
    flag = True
    if str(index + 1) in false_dict:
        if false_dict[str(index + 1)] != "0":
            flag = False
            
    else:
        false_dict[str(index + 1)] = "0"
        
    for ele in xy[index]:
        if ele[0] in false_dict:
            if false_dict[ele[0]] == ele[1]:
                flag = False
                break
        else:
            if ele[1]=="1":
                false_dict[ele[0]] = "0"
            else:
                false_dict[ele[0]] = "1"


    if flag:
        dfs(false_dict,index+1,cnt)



    return 
    

tmp_dict = dict()

dfs(tmp_dict,0,0)

print(ans[0])

Submission status: Wrong Answer

Solution code:
N = int(input())
from collections import defaultdict
A = dict()
xy = []
for i in range(N):
    A = int(input())
    xy_tmp = [input().split() for i in range(A)]
    xy.append(xy_tmp)

# print(xy)

# 全探索でいけそう
# 矛盾した時点で切る
import copy
ans = [0]

def dfs(tmp_dict,index,cnt):
    # print(tmp_dict,cnt)
        
    if index == N:
        # sum_ = 0
        # for value in list(tmp_dict.values()):
        #     sum_ += int(value)
            

        ans[0] = max(ans[0],cnt)
        return ans
    
    # 本当だった場合
    true_dict = tmp_dict.copy()
    flag = True
    for ele in xy[index]:
        if ele[0] in true_dict:
            if true_dict[ele[0]] != ele[1]:
                flag = False
                break
        else:
            true_dict[ele[0]] = ele[1]
    if str(index + 1) in true_dict:
        if true_dict[str(index + 1)] != "1":
            flag = False
    
    else:
        true_dict[str(index + 1)] = "1"

    if flag:
        dfs(true_dict,index+1,cnt+1)

    # 嘘だった場合
    false_dict = tmp_dict.copy()
    flag = True
    for ele in xy[index]:
        if ele[0] in false_dict:
            if false_dict[ele[0]] == ele[1]:
                flag = False
                break
        else:
            if ele[1]=="1":
                false_dict[ele[0]] = "0"
            else:
                false_dict[ele[0]] = "1"
    if str(index + 1) in false_dict:
        if false_dict[str(index + 1)] != "0":
            flag = False
            
    else:
        false_dict[str(index + 1)] = "0"

    if flag:
        dfs(false_dict,index+1,cnt)



    return 
    

tmp_dict = dict()

dfs(tmp_dict,0,0)

print(ans[0])

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit
setrecursionlimit(10**6)
from copy import deepcopy

def S(): return stdin.readline().rstrip()
def I(): return int(stdin.readline().rstrip())
def LS(): return list(stdin.readline().rstrip().split())
def LI(): return list(map(int,stdin.readline().rstrip().split()))
def R(x):
    r = round(x)
    if r+0.5 <= x:
        r += 1
    return r

def BFS(table, honest, next):
    p = next.pop(0)
    swt = 1
    for i in range(len(table[p])):
        q = table[p][i]
        if q!=-1:         
            if honest[i]!=-1:
                if honest[p]:
                    if q^honest[i]:
                        return False
                else:
                    if swt:
                        if not q^honest[i]:
                            honest[p] = 1
                        else:
                            honest[p] = 0
                            swt = 0
            else:
                next.append(i)
                honest[i] = q
    if 0<len(next):
        return BFS(table,honest,next)
    else:
        for i,h in enumerate(honest):
            if h==-1:
                return BFS(table,honest,[i]) 
        return True

n = I()
a = []
table = [[-1]*n for _ in range(n)]
for i in range(n):
    A = I()
    a.append(A)
    for _ in range(A):
        tmp = LI()
        table[i][tmp.pop()-1] = tmp.pop()

ans = 0
for i in range(n):
    honest = [-1]*n
    honest[i] = 1
    tmp = BFS(deepcopy(table),honest,[i])
    if tmp:
    #if BFS(deepcopy(table),honest,[i]):
        x = honest.count(1)
        if ans<x:
            ans = x
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit
setrecursionlimit(10**6)
from copy import deepcopy

def S(): return stdin.readline().rstrip()
def I(): return int(stdin.readline().rstrip())
def LS(): return list(stdin.readline().rstrip().split())
def LI(): return list(map(int,stdin.readline().rstrip().split()))
def R(x):
    r = round(x)
    if r+0.5 <= x:
        r += 1
    return r

def BFS(table, honest, next):
    p = next.pop(0)
    swt = 1
    for i in range(len(table[p])):
        q = table[p][i]
        if q!=-1:         
            if honest[i]!=-1:
                if honest[p]:
                    if q^honest[i]:
                        return False
                else:
                    if swt:
                        if not q^honest[i]:
                            honest[p] = 1
                        else:
                            honest[p] = 0
                            swt = 0
            else:
                next.append(i)
                honest[i] = q
    if 0<len(next):
        return BFS(table,honest,next)
    else:
        return True

n = I()
a = []
table = [[-1]*n for _ in range(n)]
for i in range(n):
    A = I()
    a.append(A)
    for _ in range(A):
        tmp = LI()
        table[i][tmp.pop()-1] = tmp.pop()

max = 0
ans = 0
for i in range(n):
    honest = [-1]*n
    honest[i] = 1
    tmp = BFS(deepcopy(table),honest,[i])
    if tmp:
        x = honest.count(1)
        if max<x:
            max = x
            ans = max
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit
setrecursionlimit(10**6)
from copy import deepcopy

def S(): return stdin.readline().rstrip()
def I(): return int(stdin.readline().rstrip())
def LS(): return list(stdin.readline().rstrip().split())
def LI(): return list(map(int,stdin.readline().rstrip().split()))
def R(x):
    r = round(x)
    if r+0.5 <= x:
        r += 1
    return r

def BFS(table, honest, next):
    p = next.pop(0)
    swt = 1
    for i in range(len(table[p])):
        q = table[p][i]
        if q!=-1:            
            if honest[i]!=-1:
                if q:
                    if q^honest[i]:
                        return False
                else:
                    if swt:
                        if not q^honest[i]:
                            honest[p] = 1
                        else:
                            honest[p] = 0
                            swt = 0

            else:
                next.append(i)
                honest[i] = q
    if 0<len(next):
        return BFS(table,honest,next)
    else:
        return True

n = I()
a = []
table = [[-1]*n for _ in range(n)]
for i in range(n):
    A = I()
    a.append(A)
    for _ in range(A):
        tmp = LI()
        table[i][tmp.pop()-1] = tmp.pop()

max = 0
ans = 0
for i in range(n):
    honest = [-1]*n
    honest[i] = 1
    if BFS(deepcopy(table),honest,[i]):
        x = honest.count(1)
        if max<x:
            max = x
            ans = max
print(ans)