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: Accepted

Solution code:
from itertools import product
N = int(input())
A = []
XY = []
for i in range(N):    
    a = int(input())
    A.append(a)
    xy = [list(map(int,input().split())) for _ in range(a)]
    XY.append(xy)
flag = 0
ans = 0
for i in product((0,1), repeat=N):
    for idx, j in enumerate(i):
        if j:
            for x, y in XY[idx]:
                if i[x-1] != y:
                    flag = 1
                if flag:
                    break
        if flag:
            break
    if flag == 0:
        ans = max(ans, sum(i))
    if flag:
        flag = 0
print(ans)

Submission status: Accepted

Solution code:
#0-indexed
n = int(input())
L = [[]*n 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
        L[i].append((x,y))
#print(L)
ans = 0
for i in range(1<<n):
    bit = [(i>>j)&1 for j in range(n)]
    #print(bit)
    flag = True
    for j in range(n):
        if bit[j]:
            for x,y in L[j]:
                if bit[x] != y:
                    flag = False
                    break
            if not flag:
                break
    if flag:
        ans = max(ans,sum(bit))
print(ans)

Submission status: Accepted

Solution code:

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

    X.append(a)
    Y.append(tmp)

ans = 0
for bit in range(2 ** N):
    flag = True
    for i in range(N):
        if bit >> i & 1:
            for x, y in Y[i]:
                flag &= (bit >> (x - 1) & 1) == y

    if flag:
        ans = max(ans, bin(bit).count("1"))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = []
xy = []
for i in range(n):
    a.append(int(input()))
    xy.append([list(map(int, input().split())) for i in range(a[-1])])
ans = 0
for i in range(2**n):
    x = [1] * n
    for j in range(n):
        if (i>>j)&1:
            x[j] = 0
    flag = False
    for j in range(n):
        for k in range(a[j]):
            if x[j] == 1:
                if x[xy[j][k][0]-1] != xy[j][k][1]:
                    flag = True
                    break
        if flag:
            break
    if flag:
        continue
    ans = max(ans, x.count(1))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

N=int(input())
datas=[]
for i in range(N):
    A=int(input())
    for j in range(A):
        x,y=map(int,input().split())
        datas.append((i,x-1,y)) #誰が　誰に　どう判断した？

#print(datas)

ans=0
for i in product([0,1],repeat=N):
    ok=True
    for j in datas:
        if i[j[0]]==1 and i[j[1]]!=j[2]:
            ok=False
            break
    if ok:
        ans=max(ans,sum(i))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

#print(datas)

ans=0
for i in product([0,1],repeat=N):
    ok=True
    for j in datas:
        if (i[j[0]]==1 and i[j[1]]!=j[2]):
            ok=False
            break
    if ok:
        ans=sum(i)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
# [[1番の人の証言], [2番の人の証言], ..., [N番の人の証言]]
l = [[-1 for i in range(N)] for j in range(N)]
# N人についてそれぞれ証言をまとめる
for i in range(N):
    # 証言の数
    a = int(input())
    # 各証言をlに格納
    for _ in range(a):
        x, y = map(int, input().split())
        l[i][x - 1] = y

ans = 0

# bit全探索
# N人について聖人/狂人の計2**N通り
for i in range(2**N):
    # iをN桁2bitに変換, 1が聖人に対応
    d = [0 for _ in range(N)]
    # 下からj桁目のbitが立っているか否か
    for j in range(N):
        if i >> j & 1:
            d[j] = 1
    """
    ex. N=3の時、
    i = 0,1,2,3,4,5,6,7 この時、dはそれぞれ 
    [0, 0, 0],[1, 0, 0],[0, 1, 0],[1, 1, 0],
    [0, 0, 1],[1, 0, 1],[0, 1, 1],[1, 1, 1]
    """

    flag = True

    # dの中身を左から順に見ていく
    for j in range(N):
        # jの全員に対する証言について
        for k in range(N):
            # 狂人(d[j]==0)の証言は意味がないので無視して良い
            if d[j] == 1:
                # l[j][k] == -1 なら、その人に対する証言は存在しない
                if l[j][k] == -1:
                    continue
                # kについての証言と、kの実情が異なる場合（矛盾）
                if l[j][k] != d[k]:
                    flag = False
                    break

    # 一つも矛盾が存在しなかった場合
    # sum(d)は聖人の総数を表す
    if flag == True:
        ans = max(ans, sum(d))

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
datas=[]
num=0

N=int(input())
for i in range(N):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        datas.append((num,x-1,y))
    num+=1
#print(datas)

ans=0
for i in product([0,1],repeat=N):
    ok=True
    cnt=0
    for j in datas:
        if (i[j[0]]==1 and i[j[1]]!=j[-1]):
            ok=False
            break
    if ok:
        cnt=sum(i)
        ans=max(ans,cnt)
    
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

numbers_of_testimonies =[]
contents_of_testimonies =[]

for n in range(N):
  testimony = []
  x = int(input())
  numbers_of_testimonies.append(x)
  for _ in range(x):
    testimony.append(list(map(int,input().split())))
  contents_of_testimonies.append(testimony)

numbers_of_testimonies.insert(0,"x")
contents_of_testimonies.insert(0,"x")
ans = 0

for i in range(2**N):
  hypothesis = [0 for _ in range(N)]
  
  for j in range(N):
    if (i>>j) & 1:
      hypothesis[j] = 1
  hypothesis.insert(0,9)
  flag = True
  

  for k in range(1,N+1):
    if hypothesis[k] == 1:

      for l in range(numbers_of_testimonies[k]):
        if contents_of_testimonies[k][l][1] != hypothesis[contents_of_testimonies[k][l][0]]:
          flag = False

  if flag == True:
    ans = max(ans,hypothesis.count(1))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

N=int(input())
data=[]
for i in range(N):
    for j in range(int(input())):
        x,y=map(int,input().split())
        data.append((i,x-1,y)) #iさんがx-1さんに嘘(0)or正直(1)


ans=0
for i in product([0,1],repeat=N):
    ok=True
    for j in data:
        if i[j[0]]==1 and i[j[1]]!=j[2]:
            ok = False
            break
    if ok:
        ans=max(ans,sum(i))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=[[-1 for i in range(n)] for j in range(n)]
for i in range(n):
  a=int(input())
  for j in range(a):
    x,y = map(int,input().split())
    l[i][x-1]=y

ans=0
for i in range(2**n):
  d=[0 for x in range(n)]
  for j in range(n):
    if i>>j & 1:
      d[j]=1

  flag=1

  for j in range(n):
    for s in range(n):
      if d[j]==1:
        if l[j][s]==-1:
          continue
        
        if l[j][s]!=d[s]:
          flag=0
          break
          
  if flag:
    ans=max(ans,sum(d))

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys

    def input(): return sys.stdin.readline().rstrip()

    n = int(input())

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

    ans = 0
    for i in range(1 << n):
        tmp = format(i, 'b').count('1')
        for j in range(n):
            if (i>>j)&1:
                for x, y in tf[j]:
                    if (i>>x)&1 != y:
                        break
                else:
                    continue
                break
        else:
            ans = max(ans, tmp)
    print(ans)


            



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import itertools
n = int(input())
ixy = []
for i in range(n):
    a = int(input())
    for j in range(a):
        x,y = map(int, input().split())
        ixy.append([i,x-1,y])

ans = 0
ixy = np.array(ixy)
p = itertools.product([True,False], repeat=n)
for p_i in p:
    f = True
    for i,x,y in ixy:
        if not p_i[i]:
            continue
        else:
            if p_i[x] != y:
                f = False
                break
    if f:
        ans = max(sum(p_i), ans)
print(ans)

Submission status: Accepted

Solution code:
(n,),*axy = [list(map(int, s.split())) for s in open(0)]

from itertools import product
from collections import defaultdict
d = defaultdict(defaultdict)

i = 0
for elm in axy:
    if len(elm) == 1:
        i += 1
    else:
        x,y = elm
        d[i][x] = y
del i

ans = 0
for flgs in product([0,1], repeat=n):
    honest = [i for i, v in zip(range(1, n+1), flgs) if v]
    valid = True
    for i in honest:
        if not valid:
            break
        if not i in d:
            continue
        for j in d[i]:
            if (j in honest and not d[i][j]) or (j not in honest and d[i][j]):
                valid = False
                break
    if valid:
        ans = max(ans, len(honest))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
m = []
a = [[] for i in range(n)]
for i in range(n):
    tmp = int(input())
    m.append(tmp)
    for j in range(tmp):
        a[i].append(list(map(int,input().split())))

ans = 0

for i in range(2**n):
    cnt = 0
    for j in range(n):
        flg = True
        if i >> j & 1:
            cnt += 1
            for k in range(m[j]):
                kj = (i >> (a[j][k][0]-1)) & 1
                if a[j][k][1] != kj:
                    flg = False
                    break
            if not flg:
                break
    if flg:
        ans = max(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
def max2(x,y):
    return x if x > y else y

def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

N = int(input())
data = [[] for _ in range(N)]
res = 0
for i in range(N):
    for _ in range(int(input())):
        data[i].append(tuple(map(int, input().split())))
for n in range(1 << N):
    flg = False
    for i in range(N):
        for x, y in data[i]:
            x -= 1
            if (n>>i)&1 == 1:
                if (n>>x)&1 != y:
                    flg = True
                    break
        if flg:
            break
        if i == N-1:
            res = max2(res, popcnt(n))
print(res)

Submission status: Accepted

Solution code:
from itertools import product

N = int(input())
testimony_by = []   # i番目の人の発言を格納する(3次元リスト)
for i in range(N):
    a = int(input())
    li = []   # 発言一つ分のリスト
    for j in range(a):
        li.append(list(map(int, input().split())))
    testimony_by.append(li)
ans = 0
for bit_li in product([0, 1], repeat=N):
    is_ok = True    # 矛盾がないか
    for i in range(N):
        if bit_li[i] == 1:
            for li in testimony_by[i]:
                x, y = li
                x -= 1
                if bit_li[x] != y:
                    is_ok = False
                    break

        if not is_ok:
            break
    if is_ok:
        ans = max(ans, sum(bit_li))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

def max2(x,y):
    return x if x > y else y

N = int(input())
data = [[] for _ in range(N)]
res = 0
for i in range(N):
    for _ in range(int(input())):
        data[i].append(tuple(map(int, input().split())))
for a in product((0,1), repeat=N):
    flg = False
    for i in range(N):
        for x, y in data[i]:
            x -= 1
            if a[i] == 1:
                if a[x] != y:
                    flg = True
                    break
        if flg:
            break
        if i == N-1:
            res = max2(res, sum(a))
print(res)

Submission status: Accepted

Solution code:
n=int(input())
said=[]
for i in range(n):
    a=int(input())
    said.append([list(map(int,input().split())) for _ in range(a)])
ans=0
for i in range(2**n):
    l=[0]*n
    for j in range(n):
        if (i>>j&1):
            l[j]=1
    flag=True
    for k in range(n):
        if l[k]==1 and (not all(said[k][x][1]==l[said[k][x][0]-1] for x in range(len(said[k])))):
            flag=False
            break
    if flag==True and l.count(1)>ans:
        ans=l.count(1)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
XY = [[] for _ in range(n)]
ans = 0

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

for i in range(2**n):
    correct = [False]*n
    tmp_cnt = 0
    flag = True

    for j in range(n):
        if i&(1<<j):
            correct[j] = True
            tmp_cnt += 1

    for j in range(n):
        if correct[j]:
            for x, y in XY[j]:
                if (y==0 and correct[x]) or (y==1 and not correct[x]):
                    flag = False
    if flag:
        ans = max(tmp_cnt, ans)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
g = [[-1 for _ in range(15)] for _ in range(15)]
for i in range(n) :
    m = int(input())
    for j in range(m) :
        x,y = map(int, input().split())
        #人iが「人xはyである」と証言している
        g[i][x-1] = y

ans = 0
for i in range(1<<n) :
    honests = [0] * n
    for j in range(n) :
        if (i>>j) & 1 :
            honests[j] = 1
    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: Accepted

Solution code:
n = int(input())
a = []
xy = [list() for _ in range(n)]

for i in range(n):
    a += [int(input())]
    for j in range(a[i]):
        xy[i] += [list(map(int,input().split()))]


honestnum = []

for i in range(2**n):
    flag = True
    #(if bin(i).count("1") == _:)
    #print("次のiいくよー"+"i:"+str(i)+",2進法で"+str(bin(i))[2:])
    for j in range(n):
        if (i>>j)&1 == 1:
            #print("下から"+str(j+1)+"桁目は1,つまり,index"+str(j)+"が1だね")
            for k in range(a[j]):
                if xy[j][k][1] != (i>>(xy[j][k][0]-1)&1):
                    flag = False
                    break
        
    if flag:
        #print("わーい")
        honestnum += [bin(i).count("1")]
print(max(honestnum))

Submission status: Accepted

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

for i in range(n):
    syougen_num = int(input())
    ai = []
    for j in range(syougen_num):
        xi_yi = list(map(int, input().split()))
        ai.append(xi_yi)
    a.append(ai)

res = 0
for i_bin in range(1 << n):
    syougen_list = [[0, 0] for i in range(n)]
    one_counter = 0
    for keta in range(n):
        # 1を正直者にした
        if i_bin >> keta & 1 == 1:
            one_counter += 1
            for i_syougen in a[keta]:
                #yi :0は不親切 :1は正直者 
                xi, yi = i_syougen
                syougen_list[xi - 1][yi] += 1
    for i_syougen in range(n):
        if syougen_list[i_syougen][0] >= 1 and syougen_list[i_syougen][1] >= 1:
            break
        elif syougen_list[i_syougen][0] >= 1 and i_bin >> i_syougen & 1 == 1:
            break
        elif syougen_list[i_syougen][1] >= 1 and i_bin >> i_syougen & 1 == 0:
            break
    else:
        res = max(res, one_counter)
        flag = i_bin
    # print(syougen_list, i_bin, one_counter, flag)
print(res)

Submission status: Accepted

Solution code:
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))

ans = 0
for i in range(1, 2 ** 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:
                consistent = False
                break
        #if not consistent:
            #break
    if consistent:
        ans = max(ans, bin(i)[2:].count('1'))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = []
for _ in range(n):
    a.append([list(map(int,input().split())) for __ in range(int(input()))])
l = []
for i in range(2**n):
    flag2 = 0
    for j in range(n):
        if i >> j & 1 == 1:
            flag1 = 0
            for k in a[j]:
                if i >> (k[0]-1) & 1 != k[1]:
                    flag1 = 1
                    flag2 += 1
                    break
            if flag1 : break
        
    if flag2 == 0 :l.append(list(bin(i)).count('1'))
print(max(l))

Submission status: Accepted

Solution code:
import itertools

n = int(input())
lst = []
for _ in range(n):
  m = int(input())
  lst_s = []
  for _ in range(m):
    evi = list(map(int, input().split()))
    lst_s.append(evi)
  lst.append(lst_s)
#print(lst)

truth = [0, 1]
all_lists = list(itertools.product(truth, repeat=n))
#print(all_lists)
max_count = 0
for each in all_lists:
  flag = True
  count = 0
  #print(each)
  for i in range(n):
    trust = each[i]
    #print(trust)
    evis = lst[i]
    for evid in evis:
      #print(evid)
      person_ind = evid[0] - 1
      person_trust = evid[1]
      if trust == 1:
        if person_trust != each[person_ind]:
          flag = False
          break
    if not flag:
      break
    if trust == 1:
      count += 1
  if (count > max_count) and flag:
    max_count = count
print(max_count)

Submission status: Accepted

Solution code:
import itertools 
n = int(input())
a = []
shogen =[]
for i in range(n):
    a.append(int(input()))
    temp = []
    for j in range(a[i]):
        x,y = map(int,input().split())
        temp.append([x,y])
        
    shogen.append(temp)

pattern = list(itertools.product([0,1], repeat = n))
result = 0

#print('a',a)
#print('shogen',shogen)
for i in range(len(pattern)):
    flg = True
    check = [-1 for _ in range(n)]
    #j人目について考える
    for j in range(n):
        #正直者のとき
        if pattern[i][j] == 1:
            #全ての証言について考える
            for k in range(a[j]):
                #checkが更新されていないとき
                if check[shogen[j][k][0]-1] == -1:
                    check[shogen[j][k][0]-1] = shogen[j][k][1]
                else:
                    if check[shogen[j][k][0]-1] != shogen[j][k][1]:
                        flg = False
                        #print('break') 
                        break


    for l in range(n):
        if (pattern[i][l] == 1 and check[l] == 0) or (pattern[i][l] == 0 and check[l] == 1):
            flg = False
            break

    if flg:
        #print('pattern',pattern[i])
        result = max(result, sum(pattern[i]))

print(result)

Submission status: Accepted

Solution code:
def resolve():
    N = int(input())
    XY = []
    for i in range(N):
        A = int(input())
        xy = [list(map(int, input().split())) for _ in range(A)]
        XY.append(xy)
    
    ans = 0
    for _bits in range(1<<N):
        bits = list(map(int, bin(_bits)[2:].zfill(N)))
        unmatch = False
        for i in range(N):
            if bits[i] == 0:
                continue
            for x, y in XY[i]:
                if bits[x-1] != y:
                    unmatch = True
                    break
            if unmatch:
                break
        else:
            ans = max(ans, bin(_bits).count('1'))
    print(ans)



if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
n = int(input())
num_of_sug = []
sug = []
for i in range(n):
    m = int(input())
    num_of_sug += [m]
    sug += [[tuple(map(int, input().split())) for _ in range(m)]]

ans = 0

for i in range(2 ** n):
    liar = []
    honest = []
    for j in range(n):
        if ((i >> j) & 1):
            if j + 1 in liar:
                break
            elif j + 1 not in honest:
                honest += [j + 1]
            sug_tmp = sug[j]

            for sug_ in sug_tmp:
                if sug_[1] == 1:
                    if sug_[0] in liar:
                        break
                    elif sug_[0] not in honest:
                        honest += [sug_[0]]
                else:
                    if sug_[0] in honest:
                        break
                    elif sug_[0] not in liar:
                        liar += [sug_[0]]
            else:
                continue
            break
        else:
            if j + 1 in honest:
                break
            elif j + 1 not in liar:
                liar += [j + 1]
    else:
        if ans < len(honest):
            ans = len(honest)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product


N = int(input())
all_testimonies = []
for i in range(N):
    A = int(input())
    testimony = [list(map(int, input().split())) for _ in range(A)]
    all_testimonies.append({'A': A, 'test': testimony})
    
    
# bit全探索
for bits in sorted(product(*[range(2) for _ in range(N)]), key=lambda x: sum(x), reverse=True):
    valid = True
    for i,testimony in enumerate(all_testimonies):
        person_is_honest = bool(bits[i])
        if person_is_honest:
            for j,y in testimony['test']:
                if bits[j-1] == y:
                    continue
                valid = False
    if valid:
        print(sum(bits))
        break

Submission status: Accepted

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

for i in range(n):
    temp_a = int(input())
    s = [list(map(int, input().split())) for _ in range(temp_a)]
    a.append(temp_a)
    xy.append(s)

ans = 0
for bit in range(1<<n):
    h = [0]*n
    flag = True
    sum = 0

    for i in range(n):
        if (bit>>i) & 1:
            h[i] = 1
            sum += 1
                   
    for i in range(n):
        if (bit>>i) & 1:
            for j in range(a[i]):
                if xy[i][j][1] != h[xy[i][j][0]-1]:
                    flag =False

    if flag:
        ans = max((ans, sum))
    
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
syo=[]
mx=0
for i in range(n):
  a=int(input())
  gen=[]
  for j in range(a):
    x,y=map(int,input().split())
    gen.append([x-1,bool(y)])
  syo.append(gen)
for i in range(2**n):
  brk=False
  table=[False]*n
  for j in range(n):
    if((i>>j)&1):
      table[j]=True
  for j in range(n):
    if table[j]==False:
      continue
    for syogen in syo[j]:
      if table[syogen[0]]!=syogen[1]:
        brk=True
        break
    if brk:
      break
  if brk:
    continue
  cnt=table.count(True)
  if cnt>mx:
    mx=cnt
print(mx)

Submission status: Accepted

Solution code:
N = int(input())

memberlist = []
testinomylist = []


for _ in range(N):

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

    memberlist.append(tmpmemberlist)      # [[2,3],[1,3],[1]] こんな感じで人が収容
    testinomylist.append(tmptestinomylist) # [[0,1],[1],[0]]
        
ans = 0

for i in range(2 ** N):
    honestlist = []
    liarlist = []

    for j in range(N):  
        if ((i >> j) & 1):
            #if true 条件を満たした人を正直物として考える.
            honestlist.append(j+1)
        else:
            # if false の人は嘘つきものだと考える。
            liarlist.append(j+1)

    #正直な人だけを見ればいい。
    Flag = 0

    for honestnumber in honestlist: #bit全探索で得た正直な人の番号

        for X,Y in zip(memberlist[honestnumber-1] , testinomylist[honestnumber-1]): # 正直な人だけの証言
            if (Y == 0):
                if X in liarlist: #正直者の証言が食い違ってないか
                    pass
                else:
                    Flag = 1 
            elif (Y == 1):
                if X in honestlist:
                    pass
                else:
                    Flag = 1


    if Flag == 1:
        pass
    else:
        ans = max(ans,len(honestlist))

print(ans)

Submission status: Accepted

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 i in range(1,2**N):
  consistent = True
  for j in range(N):
    if (i>>j)&1 == 1:
      for x,y in evidence[j]:
        if (i>>x)&1 != y:
          consistent = False
          break
      if not consistent:
        break
  if consistent:
    result = max(result,bin(i)[2:].count("1"))
    
print(result)

Submission status: Accepted

Solution code:
def resolve():
    import itertools
    N = int(input())
    A = []
    X = []
    ans = [0]
    for _ in range(N):
        a = int(input())
        xx = []
        for __ in range(a):
            x = list(map(int, input().split()))
            xx.append(x)
        X.append(xx)
        A.append(a)
    for i in itertools.product([0, 1], repeat=N):
        flag = 0
        for p in range(N):
            for q in range(A[p]):
                if i[p] == 1 and X[p][q][1] != i[X[p][q][0]-1]:
                    flag = 1
        if flag == 0:
            ans.append(i.count(1))
    print(max(ans))
resolve()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XY = []
for _ in range(N):
    A = int(input())
    xy = [list(mapint()) for _ in range(A)]
    XY.append(xy)

ans = 0
for i in range(1<<N):
    honest = [-1]*N
    cnt = 0
    ok = True
    for j in range(N):
        if (i>>j)&1:
            honest[j]=1
        else:
            honest[j]=0
    for j in range(N):
        if (i>>j)&1:
            cnt += 1
            for x, y in XY[j]:
                if honest[x-1]!=y:
                    ok = False
                    break
    if ok:
        ans = max(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l0=[[] for _ in range(n)]
l1=[[] for _ in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        if y==0:
            l0[i].append(x)
        else:
            l1[i].append(x)
ans=0
for i in range(2**n):
    s0=set()
    s1=set()
    num=0
    num1=[]
    num0=[]
    for j in range(n):
        if (i>>j) & 1:
            num1.append(j+1)
            for k in range(len(l0[j])):
                s0.add(l0[j][k])
            for k in range(len(l1[j])):
                s1.add(l1[j][k])
        else:
            num0.append(j+1)
    for j in range(len(s1)):
        if s1.pop() in num0:
            num=1
            break
    if num==0:
        for j in range(len(s0)):
            if s0.pop() in num1:
                num=1
                break
    if num==0:
        ans=max(ans,len(num1))
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations_with_replacement,product
def input(): return sys.stdin.readline().rstrip()
 
def main():
    n=int(input())
    li=[]
    for i in range(n):
        lia=[]
        A=int(input())
        for j in range(A):

            x,y=map(int, input().split())
            x-=1
            lia.append([x,y])
        li.append(lia)
    ans = 0
    for k in list(product([0,1],repeat=n)):
        if ans >= sum(k):
            continue
        kt = list(k)
        for y in range(n):
            if kt[y]==1:
                for g in li[y]:
                    if g[1] != kt[g[0]]:
                        break
                else:
                    continue
                break
        else:
            ans = sum(k)
            
    print(ans)



if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    A = []
    xy = []
    for _ in range(N):
        A.append(I())
        xy.append([LI() for _ in range(A[-1])])

    ans = 0
    for i in range(2 ** N):
        # まず正直者を仮定し、正直者の証言に矛盾がないか判定
        is_ok = True
        num = 0
        for j in range(N):
            if i >> j & 1:
                num += 1
                for k in xy[j]:
                    x, y = k
                    x -= 1
                    if i >> x & 1 != y:
                        is_ok = False
        if is_ok:
            ans = max(num, ans)

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N=int(input())
X=[0]*N
for i in range(N):
 X[i]=[list(map(int,input().split())) for _ in [0]*int(input())]
print(max(['{:b}'.format(i).count('1')for i in range(2**N) if all([all([y[1]==i>>(y[0]-1)&1 for y in X[j]]) for j in range(N) if (i>>j&1)])]))

Submission status: Accepted

Solution code:
N=int(input())
X=[0]*N
for i in range(N):
    X[i]=[list(map(int,input().split())) for _ in range(int(input()))]
print(max(['{:03b}'.format(i).count('1')for i in range(2**N) if all([i>>j&1 and all([y[1]==i>>(y[0]-1)&1 for y in X[j]]) for j in range(N) if (i>>j&1)])]))