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:
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    A_arr = []
    x_y_arr = []
    line = 1
    for i in range(N):
        _ = int(_in[line])  # type:int
        A_arr.append(_)
        tmp = {}
        for j in range(_):
            x,y = list(map(int,_in[line+j+1].split(' ')))  # type:list(int)
            tmp[x] = y
        x_y_arr.append(tmp)
        line += _+1
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = 0
    for bit in range(1<<N):
        # bit = 0: Unkind, 1: Honest
        for i in range(N):
            if bit&(1<<i): # Honest
                for k,v in x_y_arr[i].items():
                    if bit&(1<<(k-1))!=y:
                        break
                else:
                    continue
                break
            else: # Unkind
                for k,v in x_y_arr[i].items():
                    if bit&(1<<(k-1))==y:
                        break
                else:
                    continue
                break
        else:
            _ = bin(bit).count('1')
            cnt = max(cnt,_)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

Submission status: Wrong Answer

Solution code:
from itertools import product
n=int(input())
li=[[] for _ in range(n)]
A=[]
for i in range(n):
    a=int(input())
    A.append(a)
    for _ in range(a):
        x,y=map(int,input().split())
        li[i].append([x,y])
ans=0
for p in product([0, 1], repeat = n):
    f = 0
    for i in range(n):
        if f==0:
            for j in range(A[i]):
                if p[i]==1 and li[i][j][1] == 0:
                    if p[li[i][j][0] - 1] == 1:
                        f = 1
                        break
                elif p[i]==1 and li[i][j][1] == 1:
                    if p[li[i][j][0] - 1] == 0:
                        f = 1
                        break
                elif p[i]==0 and li[i][j][1] == 1:
                    if p[li[i][j][0] - 1] == 1:
                        f=1
                        break
                else:
                    if p[li[i][j][0] - 1] == 0:
                        f=1
                        break
        else:
            break
    if f==0:
        ans=max(ans,p.count(1))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list()
xy = list()
flag = True
num = 0
output=0
for i in range(N):
  A.append(int(input()))
  xy.append([list(map(int,input().split())) for _ in range(A[i])])
  
for i in range(2**N):
  flag = True
  num = str(format(i, 'b').zfill(N))
  for j in range(N):
    if ((i>>j)&1) == 1:
      for k in range(len(xy[N-j-1])):
        if int(num[xy[N-1-j][k][0]-1]) !=  xy[N-1-j][k][1]:
          flag = False
          break
    elif ((i>>j)&1) == 0:
      for k in range(len(xy[N-j-1])):
        if int(num[xy[N-1-j][k][0]-1]) ==  xy[N-1-j][k][1]:
          flag = False
          break
    if flag == False:
      break
  if flag == True and output <= str(bin(i)).count('1') :
    output = str(bin(i)).count('1')
print(output)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list()
xy = list()
flag = True
num = 0
output=0
for i in range(N):
  A.append(int(input()))
  xy.append([list(map(int,input().split())) for _ in range(A[i])])
for i in range(2**len(A)):
  flag = True
  num = str(format(i, 'b').zfill(len(A)))
  for j in range(len(A)):
    if ((i>>j)&1) == 1:
      for k in range(len(xy[len(A)-j-1])):
        if int(num[xy[len(A)-1-j][k][0]-1]) !=  xy[len(A)-1-j][k][1]:
          flag = False
    elif ((i>>j)&1) == 0:
      for k in range(len(xy[len(A)-j-1])):
        if int(num[xy[len(A)-1-j][k][0]-1]) ==  xy[len(A)-1-j][k][1]:
          flag = False
  if flag == True and output <= str(bin(i)).count('1') :
    output = str(bin(i)).count('1')
print(output)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list()
xy = list()
flag = True
output=0
for i in range(N):
  A.append(int(input()))
  xy.append([list(map(int,input().split())) for _ in range(A[i])])
for i in range(2**len(A)):
  flag = True
  for j in range(len(A)):
    if ((i>>j)&1) == 1:
      for k in range(len(xy[j])):
        if A[xy[j][k][0]-1] !=  xy[j][k][1]:
          flag = False
    elif ((i>>j)&1) != 1:
      for k in range(len(xy[j])):
        if A[xy[j][k][0]-1] ==  xy[j][k][1]:
          flag = False
  if flag == True and output <= str(bin(i)).count('1') :
    output = str(bin(i)).count('1')
print(output)

Submission status: Wrong Answer

Solution code:
N = int(input())
testimony = [[] for _ in range(N)]
ans = 0
for n in range(N):
    A = int(input())
    for _ in range(A):
        x,y = map(int,input().split())
        testimony[n].append([x-1,y]) # 人のナンバリングを0startにする
print(testimony)
for bit in range(2**N):
#     print("bit",bit)
    honest_cnt = 0
    for j in range(N):
#         print("j",j)
        if (bit>>j) & 1:
            honest_cnt += 1
            for t in testimony[j]:
                if (bit>>t[0])&1 != t[1]:
#                     print("break")
                    break
            else:
#                 print("continue")
                continue
#             print("break")
            break
    else:
#         print("new_ans")
        ans = max(ans,honest_cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
testimony = [[] for _ in range(N)]
ans = 0
for n in range(N):
    A = int(input())
    for _ in range(A):
        x,y = map(int,input().split())
        testimony[n].append([x-1,y]) # 人のナンバリングを0startにする
for bit in range(1<<n):
    honest_cnt = 0
    for j in range(N):
        if (bit>>j) & 1:
            honest_cnt += 1
            for t in testimony[j]:
                if (bit>>t[0])&1 != t[1]:
                    break
            else:
                continue
            break
    ans = max(ans,honest_cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
testimony = [[] for _ in range(N)]
ans = 0
for n in range(N):
    A = int(input())
    for _ in range(A):
        x,y = map(int,input().split())
        testimony[n].append([x-1,y]) # 人のナンバリングを0startにする
# peopleの正直、嘘つきの組み合わせ作成
for bit in range(1<<n):
    honest_cnt = 0
    people = [0]*N
    for j in range(N):
        if bit & (1<<j):

# people組み合わせ作成ここまで
            honest_cnt += 1
            for t in testimony[j]:
                if bit & 1<<(t[0]) != t[1]:
                    break
            else:
                ans = max(ans,honest_cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
testimony = [[] for _ in range(N)]
ans = 0
for n in range(N):
    A = int(input())
    for _ in range(A):
        x,y = map(int,input().split())
        testimony[n].append([x-1,y]) # 人のナンバリングを0startにする
# peopleの正直、嘘つきの組み合わせ作成
for bit in range(1<<n):
    honest_cnt = 0
    people = [0]*N
    for j in range(N):
        if bit & (1<<j):
            
# people組み合わせ作成ここまで
            honest_cnt += 1
            for t in testimony[j]:
                if 1<<(t[0]) != t[1]:
                    break
            else:
                ans = max(ans,honest_cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
testimony = [[] for _ in range(N)]
ans = 0
for n in range(N):
    A = int(input())
    for _ in range(A):
        x,y = map(int,input().split())
        testimony[n].append([x-1,y]) # 人のナンバリングを0startにする
# peopleの正直、嘘つきの組み合わせ作成
for bit in range(1<<n):
    honest_cnt = 0
    people = [0]*N
    for j in range(N):
        if bit & (1<<j):
            people[j] = 1
# people組み合わせ作成ここまで
            honest_cnt += 1
            for t in testimony[j]:
                if people[t[0]] != t[1]:
                    break
            else:
                ans = max(ans,honest_cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
testimony = [[] for _ in range(N)]
ans = 0
for n in range(N):
    honest_cnt = 0
    A = int(input())
    for _ in range(A):
        x,y = map(int,input().split())
        testimony[n].append([x-1,y]) # 人のナンバリングを0startにする
# peopleの正直、嘘つきの組み合わせ作成
for i in range(2**N):
    people = [0]*N
    for j in range(N):
        if (i>>j)&1:
            people[j] = 1
# people組み合わせ作成ここまで
    for n in range(N): # 証言との整合性をみる
        for t in testimony[n]:
            if people[t[0]] == t[1]^people[n]:
                break
        else:
            continue
        break
    else:
        honest_cnt = people.count(1)
        ans = max(ans,honest_cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools 
n=int(input())
g=[[-1 for _ in range(15)] for _ in range(15)]
for i in range(n):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        g[i][x-1]=y
ans=0

for i in range(2**n):
    honests = [0 for _ in range(n)]
    for j in range(n):
        if(i>>j)&1:
            honests[j]=1
    print(honests)
    ok=True
    for j in range(n):
        if honests[j]:
            for k in range(n):
                if g[j][k]==-1: continue
                if g[j][k]!=honests[k]: ok=False
    if ok:
        ans=max(ans,honests.count(1))
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

n = int(input())
ans = 0
x = [[0 for i in range(15)] for j in range(n)]
y = [[0 for i in range(15)] for j in range(n)]
a = [0 for i in range(n)]
for i in range(n):
    a[i] = int(input())
    for j in range(a[i]):
        tmpx, tmpy = map(int, input().split())
        x[i][j] = tmpx - 1
        y[i][j] = tmpy

person = [i for i in range(n)]
## i:正直と仮定する人の人数
for i in range(1,n + 1):
    ## j:i人正直と仮定したときの全ての組み合わせ
    for j in itertools.combinations(person,i):
        truth = [0 for i in range(n)]
        flag = True
        ##正直な人の処理 k:正直と仮定した人の番号
        for k in j:
            ##正直と仮定した人が他の正直者によって：嘘つきと言われていたら矛盾
            if truth[k] == -1:
                flag = False
                break
            ##k番目の人は正直とする
            truth[k] = 1
            ##正直な人の証言を信用 l:番号kのl番目の情報
            for l in range(a[k]):
                ##嘘つきの情報があれば
                if y[k][l] == 0:
                    ##すでに正直者と決まっていたら矛盾
                    if truth[x[k][l]] == 1 or x[k][l] in j:
                        flag = False
                        break
                    else:
                        truth[x[k][l]] = -1
                ##正直者の情報があれば
                else:
                    if truth[x[k][l]] == -1 or not (x[k][l] in j): 
                        flag = False
                        break
                    else:
                        truth[x[k][l]] = 1
            ##矛盾が生じたら
            if not flag: break
        ##l:嘘つきと仮定した人の番号
        for k in list(set(person) - set(j)):
            ##嘘つきと仮定した人が正直と言われていたら矛盾
            if truth[k] == 1:
                flag = False
                break
            ##k番目の人は嘘つきとする
            truth[k] = -1
            ##嘘つきの証言は嘘 l:番号kのl番目の情報
            for l in range(a[k]):
                ##嘘つきの情報があれば
                if y[k][l] == 0:
                    ##すでに嘘つきと決まっていたら矛盾
                    if truth[x[k][l]] == -1 or x[k][l] in list(set(person) - set(j)):
                        flag = False
                        break
                    else:
                        truth[x[k][l]] = 1
                ##正直者の情報があれば
                else:
                    if truth[x[k][l]] == 1 or not (x[k][l] in list(set(person) - set(j))):
                        flag = False
                        break
                    else:
                        truth[x[k][l]] = -1
            ##矛盾が生じたら
            if not flag: break
        if not flag:continue
        ##矛盾が一切無ければ
        ans = i
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

n = int(input())
ans = 0
x = [[0 for i in range(15)] for j in range(n)]
y = [[0 for i in range(15)] for j in range(n)]
a = [0 for i in range(n)]
for i in range(n):
    a[i] = int(input())
    for j in range(a[i]):
        tmpx, tmpy = map(int, input().split())
        x[i][j] = tmpx - 1
        y[i][j] = tmpy

person = [i for i in range(n)]
## i:正直と仮定する人の人数
for i in range(1,n + 1):
    ## j:i人正直と仮定したときの全ての組み合わせ
    for j in itertools.combinations(person,i):
        truth = [0 for i in range(n)]
        flag = True
        ##正直な人の処理 k:正直と仮定した人の番号
        for k in j:
            ##正直と仮定した人が他の正直者によって：嘘つきと言われていたら矛盾
            if truth[k] == -1:
                flag = False
                break
            ##k番目の人は正直とする
            truth[k] = 1
            ##正直な人の証言を信用 l:番号kのl番目の情報
            for l in range(a[k]):
                ##嘘つきの情報があれば
                if y[k][l] == 0:
                    ##すでに正直者と決まっていたら矛盾
                    if truth[x[k][l]] == 1 or x[k][l] in j:
                        flag = False
                        break
                    else:
                        truth[x[k][l]] = -1
                ##正直者の情報があれば
                else:
                    if truth[x[k][l]] == -1 or not (x[k][l] in j): 
                        flag = False
                        break
                    else:
                        truth[x[k][l]] = 1
            ##矛盾が生じたら
            if not flag: break
        ##l:嘘つきと仮定した人の番号
        for k in list(set(person) - set(j)):
            ##嘘つきと仮定した人が正直と言われていたら矛盾
            if truth[k] == 1:
                flag = False
                break
            ##k番目の人は嘘つきとする
            truth[k] = -1
            ##嘘つきの証言は嘘 l:番号kのl番目の情報
            for l in range(a[k]):
                ##嘘つきの情報があれば
                if y[k][l] == 0:
                    ##すでに嘘つきと決まっていたら矛盾
                    if truth[x[k][l]] == -1 or x[k][l] in list(set(person) - set(j)):
                        flag = False
                        break
                    else:
                        truth[x[k][l]] = 1
                ##正直者の情報があれば
                else:
                    if truth[x[k][l]] == 1 or not (x[k][l] in list(set(person) - set(j))):
                        flag = False
                        break
                    else:
                        truth[x[k][l]] = -1
            ##矛盾が生じたら
            if not flag: break
        if not flag:continue
        ##矛盾が一切無ければ
        ans = max(ans,i)
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

n = int(input())
ans = 0
x = [[0 for i in range(15)] for j in range(n)]
y = [[0 for i in range(15)] for j in range(n)]
a = [0 for i in range(n)]
for i in range(n):
    a[i] = int(input())
    for j in range(a[i]):
        tmpx, tmpy = map(int, input().split())
        x[i][j] = tmpx - 1
        y[i][j] = tmpy

person = [i for i in range(n)]
## i:正直と仮定する人の人数
for i in range(1,n + 1):
    ## j:i人正直と仮定したときの全ての組み合わせ
    for j in itertools.combinations(person,i):
        truth = [0 for i in range(n)]
        flag = True
        ##正直な人の処理 k:正直と仮定した人の番号
        for k in j:
            ##正直と仮定した人が他の正直者によって：嘘つきと言われていたら矛盾
            if truth[k] == -1:
                flag = False
                break
            ##k番目の人は正直とする
            truth[k] = 1
            ##正直な人の証言を信用 l:番号kのl番目の情報
            for l in range(a[k]):
                ##嘘つきの情報があれば
                if y[k][l] == 0:
                    ##すでに正直者と決まっていたら矛盾
                    if truth[x[k][l]] == 1 or x[k][l] in j:
                        flag = False
                        break
                    else:
                        truth[x[k][l]] = -1
                ##正直者の情報があれば
                else:
                    if truth[x[k][l]] == -1: 
                        flag = False
                        break
                    else:
                        truth[x[k][l]] = 1
            ##矛盾が生じたら
            if not flag: break
        ##l:嘘つきと仮定した人の番号
        for k in list(set(person) - set(j)):
            ##嘘つきと仮定した人が正直と言われていたら矛盾
            if truth[k] == 1:
                flag = False
                break
            ##k番目の人は嘘つきとする
            truth[k] = -1
            ##嘘つきの証言は嘘 l:番号kのl番目の情報
            for l in range(a[k]):
                ##嘘つきの情報があれば
                if y[k][l] == 0:
                    ##すでに嘘つきと決まっていたら矛盾
                    if truth[x[k][l]] == -1 or x[k][l] in list(set(person) - set(j)):
                        flag = False
                        break
                    else:
                        truth[x[k][l]] = 1
                ##正直者の情報があれば
                else:
                    if truth[x[k][l]] == 1:
                        flag = False
                        break
                    else:
                        truth[x[k][l]] = -1
            ##矛盾が生じたら
            if not flag: break
        if not flag:continue
        ##矛盾が一切無ければ
        ans = max(ans,i)
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

n = int(input())
ans = 0
x = [[0 for i in range(15)] for j in range(n)]
y = [[0 for i in range(15)] for j in range(n)]
a = [0 for i in range(n)]
for i in range(n):
    a[i] = int(input())
    for j in range(a[i]):
        tmpx, tmpy = map(int, input().split())
        x[i][j] = tmpx - 1
        y[i][j] = tmpy

person = [i for i in range(n)]
## i:正直と仮定する人の人数
for i in range(1,n + 1):
    ## j:i人正直と仮定したときの全ての組み合わせ
    for j in itertools.combinations(person,i):
        truth = [0 for i in range(n)]
        flag = True
        ##正直な人の処理 k:正直と仮定した人の番号
        for k in j:
            ##正直と仮定した人が他の正直者によって：嘘つきと言われていたら矛盾
            if truth[k] == -1:break
            ##k番目の人は正直とする
            truth[k] = 1
            ##正直な人の証言を信用 l:番号kのl番目の情報
            for l in range(a[k]):
                ##嘘つきの情報があれば
                if y[k][l] == 0:
                    ##すでに正直者と決まっていたら矛盾
                    if truth[x[k][l]] == 1 or x[k][l] in j:
                        flag = False
                        break
                    else:
                        truth[x[k][l]] = -1
                ##正直者の情報があれば
                else:
                    if truth[x[k][l]] == -1: 
                        flag = False
                        break
                    else:
                        truth[x[k][l]] = 1
            ##矛盾が生じたら
            if not flag: break
        ##l:嘘つきと仮定した人の番号
        for k in list(set(person) - set(j)):
            ##嘘つきと仮定した人が正直と言われていたら矛盾
            if truth[k] == 1:
                flag = False
                break
            ##k番目の人は嘘つきとする
            truth[k] = -1
            ##嘘つきの証言は嘘 l:番号kのl番目の情報
            for l in range(a[k]):
                ##嘘つきの情報があれば
                if y[k][l] == 0:
                    ##すでに嘘つきと決まっていたら矛盾
                    if truth[x[k][l]] == -1:
                        flag = False
                        break
                    else:
                        truth[x[k][l]] = 1
                ##正直者の情報があれば
                else:
                    if truth[x[k][l]] == 1:
                        flag = False
                        break
                    else:
                        truth[x[k][l]] = -1
            ##矛盾が生じたら
            if not flag: break
        if not flag:continue
        ##矛盾が一切無ければ
        ans = max(ans,i)
        break

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = []
ans = 0
for i in range(n):
    x =int(input())
    lists = [list(map(int,input().split())) for j in range(x)]
    A.append(lists)

for i in range(2**n):
    honesty = [0]*n
    for j in range(n):
        if (i>>j) & 1:
            honesty[j] = 1
    true = 1
    for j in range(n):
        if honesty[j] == 1:
            for k in range(len(A[j])):
                x,y = A[j][k]
                if not honesty[x-1] == y:
                    true = 0
                    break
    if true == 1:
        ans = max(ans,sum(honesty))
print(ans)
print(A)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [0] * n
xy = []
for i in range(n):
    a[i] = int(input())
    x_y = []
    for j in range(a[i]):
        x_y.append(list(map(int,input().split())))
    xy.append(x_y)
ans = n
li0 = [0] * n
li1 = [0] * n
for i in range(len(a)):
    for j in range(a[i]):
        if xy[i][j][1] == 0:
            li0[xy[i][j][0]-1] = -1
        else:
            li1[xy[i][j][0]-1] = 1
flg = True
for i in range(n):
    if li0[i] == -1 and li1[i] == 1:
        ans -= 1
        flg= False
if flg:
    print(ans-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
xy = []

if N == 1:
  print(0)
  exit()

for _ in range(N):
  a = int(input())
  tmp = [list(map(int, input().split())) for _ in range(a)]
  xy += [tmp]

ans = 0
for i in range(2**N):
  d = {i:-1 for i in range(1, N+1)}
  flag = True
  tmp = 0
  #print("---i---", i)
  for j in range(N):
    #print(d, j)
    if (i>>j)&1: # 正直
      tmp += 1
      d[j+1] = 1
      for x, y in xy[j]:
        if d[x] == -1:
          d[x] = y
        else:
          if d[x] != y:
            flag = False
            break
    else:
      if d[j+1] == 1:
        flag = False
        break
      d[j+1] = 0
    
  if flag:
    ans = max(tmp, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
xy = []

for _ in range(N):
  a = int(input())
  tmp = [list(map(int, input().split())) for _ in range(a)]
  xy += [tmp]
ans = 0
for i in range(2**N):
  d = {i:-1 for i in range(1, N+1)}
  flag = True
  tmp = 0
  for j in range(N):
    if (i>>j)&1: # 正直
      tmp += 1
      d[j+1] = 1
      for x, y in xy[j]:
        if d[x] == -1:
          d[x] = y
        else:
          if d[x] != y:
            flag = False
            break
    else:
      if d[j+1] == 1:
        flag = False
        break
      d[j+1] = 0

  if flag:
    ans = max(tmp, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
xy = []

for _ in range(N):
  a = int(input())
  tmp = [list(map(int, input().split())) for _ in range(a)]
  xy += [tmp]
ans = 0
for i in range(2**N):
  d = {i:-1 for i in range(1, N+1)}
  flag = True
  tmp = 0
  for j in range(N):
    if (i>>j)&1: # 正直
      tmp += 1
      d[j+1] = 1
      for x, y in xy[j]:
        if d[x] == -1:
          d[x] = y
        else:
          if d[x] != y:
            flag = False
            break

  if flag:
    ans = max(tmp, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
xy = []

for _ in range(N):
  a = int(input())
  tmp = [list(map(int, input().split())) for _ in range(a)]
  xy += [tmp]
ans = 0
for i in range(2**N):
  d = {i:-1 for i in range(1, N+1)}
  flag = True
  tmp = 0
  for j in range(N):
    #print(d, j)
    if (i>>j)&1: # 正直
      tmp += 1
      d[j+1] = 1
      for x, y in xy[j]:
        #print(d, i, j)
        if d[x] == -1:
          d[x] = y
        else:
          if d[x] != y:
            flag = False
            break
    else: # 不親切
      if d[j+1] == 1:
        flag = False
        break
      for x, y in xy[j]:
        if d[x] == -1:
          d[x] = abs(1-y)
        else:
          if d[x] != abs(1-y):
            flag = False
            break

  if flag:
    ans = max(tmp, ans)
  #print(d, i, tmp)
  #print()
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n = int(input())
x = [[2]*n]*n
y = [[2]*n]*n
a = [0]*n
c = 0
for i in range(n):
	a[i] = int(input())
	for j in range(a[i]):
		x[i][j],y[i][j] = map(int,input().split())

for l in range(1,n+1):
	for T in itertools.combinations(range(1,n+1),l):
		for k in range(l):
			if set(T) != set([x[T[k]-1][j] for j in range(n) if y[T[k]-1][j] == 1]) or set(range(1,n+1))-set(T) != set([x[T[k]-1][j] for j in range(n) if y[T[k]-1][j] == 0]):
				c += 1
	if c == l:
		break
	else:
		c = 0
print(l-1)

Submission status: Wrong Answer

Solution code:
N = int(input())
t = []
for _ in range(N):
    A = int(input())
    tt = []
    for _ in range(A):
        tt.append(list(map(int, input().split())))
    t.append(tt)
ans = 0
for b in range(1 << N):
    f = True
    c = 0
    for i, tt in enumerate(t):
        for x, y in tt:
            if b & 1 << i:
                c += 1
                if b >> (x - 1) & 1 != y:
                    f = False
                    break
    if f:
        ans = max(ans, c)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
t = []
for _ in range(N):
    A = int(input())
    tt = []
    for _ in range(A):
        tt.append(list(map(int, input().split())))
    t.append(tt)
ans = 0
for b in range(1 << N):
    f = True
    for i, tt in enumerate(t):
        for x, y in tt:
            if b & 1 << i:
                if (b & 1 << (x - 1)) >> (x - 1) != y:
                    f = False
                    break
            else:
                if (b & 1 << (x - 1)) >> (x - 1) == y:
                    f = False
                    break
    if f:
        ans = max(ans, bin(b).count('1'))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

n = int(input())

from collections import defaultdict
d = defaultdict(list)

for i in range(n):
    a = int(input())
    for _ in range(a):
        x, y = [int(x) for x in input().split()]
        d[i].append((x - 1, y))
ans = 0
for k in range(2**n):
    res = 0
    j = bin(k)[2:].zfill(n)
    for i in range(n):
        if j[i] == "0":
            continue
        flag = 1
        for x, y in d[i]:
            if int(j[x]) != int(y):
                flag = 0
                break
        for l in range(n):
            if j[l] == "1" and (i, 0) in d[l]:
                flag = 0
                break
        if flag:
            res += 1
    ans = max(ans, res)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product
import copy
N = int(input())
if N==1:
    cmax = 1
else:
    A = [[-1 for _ in range(N+1)] for _ in range(N+1)]
    for i in range(1,N+1):
        k = int(input())
        for _ in range(k):
            x,y = map(int,input().split())
            A[i][x] = y
    cmax = 0
    for z in product((0,1),repeat=N):
        B = copy.deepcopy(A)
        for i in range(N):
            if z[i]==0:
                for j in range(1,N+1):
                    if B[i+1][j]>=0:
                        B[i+1][j] = 1-B[i+1][j]
            B[i+1][i+1] = z[i]
        flag = 0
        for j in range(1,N+1):
            c0 = 0
            c1 = 0
            for i in range(1,N+1):
                if B[i][j]==0:
                    c0 += 1
                elif B[i][j]==1:
                    c1 += 1
            if c0>0 and c1>0:
                flag = 1
                break
        if flag==0:
            cmax = max(cmax,sum(z))
print(cmax)

Submission status: Wrong Answer

Solution code:
from itertools import product
import copy
N = int(input())
A = [[-1 for _ in range(N+1)] for _ in range(N+1)]
for i in range(1,N+1):
    k = int(input())
    for j in range(k):
        x,y = map(int,input().split())
        A[i][x] = y
cmax = 0
for z in product((0,1),repeat=N):
    B = copy.deepcopy(A)
    for i in range(N):
        if z[i]==0:
            for j in range(1,N+1):
                if B[i+1][j]>=0:
                    B[i+1][j] = 1-B[i+1][j]
            B[i+1][i+1] = 0
        else:
            B[i+1][i+1] = 1
    flag = 0
    for j in range(1,N+1):
        c0 = 0
        c1 = 0
        for i in range(1,N+1):
            if B[i][j]==0:
                c0 += 1
            elif B[i][j]==1:
                c1 += 1
        if c0>0 and c1>0:
            flag = 1
            break
    if flag==0:
        cmax = max(cmax,sum(z))
print(cmax)

Submission status: Wrong Answer

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

for i in range(n):
    ai=int(input())
    axy.append([])
    for j in range(ai):
        axy[-1].append(list(map(int,input().split())))

ans=0
pat=2**n
#print(axy)
for p in range(pat):
    bin_p=list(map(int,bin(p)[2:].zfill(n)))

    flag=False
#    print(bin_p)
    for i in range(n):

        for axyi in axy[i]:
#            print(axyi)
            if(bin_p[i]==1 and bin_p[axyi[0]-1] != axyi[1]):
                flag=True
                break

            if(bin_p[i]==0 and bin_p[axyi[0]-1] == axyi[1]):
                flag=True
                break


        if(flag):
            break
    else:
#        print(bin_p,flag)
        ans=max(ans,bin_p.count(1))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

n = int(input())

from collections import defaultdict
d = defaultdict(list)

for i in range(n):
    a = int(input())
    for _ in range(a):
        x, y = [int(x) for x in input().split()]
        d[i].append((x - 1, y))
ans = 0
for k in range(2**n):
    res = 0
    j = bin(k)[2:].zfill(n)
    for i in range(n):
        if j[i] == "0":
            continue
        flag = 1
        for x, y in d[i]:
            if int(j[x]) != int(y):
                flag = 0
                break
            elif int(j[x]) == 1 and (i, 0) in d[x]:
                flag = 0
                break
        if flag:
            res += 1
    ans = max(ans, res)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n=int(input())
    A=[0]*n
    st=[[] for _ in range(n)]
    for i in range(n):
        a=int(input())
        for j in range(a):
            x,y=map(int,input().split())
            st[i].append((x,y))

    
    # bit全探索    
    # https://qiita.com/gogotealove/items/11f9e83218926211083a#%E4%BE%8B%E9%A1%8C-1
    # 昇順での探索だよ
    ans=0
    for i in range(2 ** n):
        inconsistent=False
        cnt=0
        for j in range(n):  # このループが一番のポイント
            if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
                cnt+=1
                for p in st[j]:
                    if p[1]==1 and not ((i >> (p[0]-1) & 1)):
                        inconsistent=True
                    elif p[1]==0 and not not ((i >> (p[0]-1) & 1)):
                        inconsistent=True
            else:
                for p in st[j]:
                    if p[1]==1 and not not ((i >> (p[0]-1) & 1)):
                        inconsistent=True
                    elif p[1]==0 and not not not((i >> (p[0]-1) & 1)):
                        inconsistent=True
            

        if not inconsistent:
            ans=max(ans,cnt)
    print(ans)
    

    
resolve()