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:
g = [[-1 for _ in range(15)] for _ in range(15)]
n = int(input())
ans=0
for i in range(n):
  m = int(input())
  for j in range(m):
    x,y = map(int, input().split())
    g[i][x-1] = y
for i in range(1<<n):
  honests = [0 for _ in range(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)
'''
・正直者の人の組を全ての組合せで仮定する。
・正直者と仮定した人の証言が仮定に矛盾するとき、
その正直者の選び方の組はあり得ない。
・正直者と仮定した人の証言同士の矛盾は調べる必要はない。
ある人に対して矛盾する二つの証言があるとき、
どちらか一方の証言は必ず仮定に矛盾する。したがって、
この仮定があり得ないことを調べるには仮定と証言の矛盾を調べるだけでよい。
・全ての証言が矛盾しない正直者の選び方の組のうち、
正直者が最も多い組の正直者の人数を求めれば良い。
人xの人yに対する証言のデータを二次元配列gへ次のような対応関係で
格納しておく。なお、ここでは人の番号は配列のオフセットに合わせるため
0から始めるものとする。
・人xが人yに対して正直者であると証言するとき、
二次元配列g[x][y]を1にする。
・人xが人yに対して不親切な人であると証言するとき
二次元配列g[x][y]を0とする。
・人xが人yに対して言及していないとき、
二次元配列g[x][y]を-1にする。
・入力よりNの最大が15なので、
15行15列の二次元配列gをデフォルト値-1用意しておく
・全員の人数を表す値を受け取る。
・用意した配列に人iが人jに対して述べる証言のデータを格納していく。
・人iの証言の数mを受け取る。
・人iの証言を受け取るためm回次のループを回す。
・証言を表す二つの値を受け取り二次元配列gに格納する。
人iが「人xはyである」と証言しているときg[i][x]=yである。
（入力で受け取る「人の番号」は1から始まるため、
コードでは受け取った値から1引いている。）
g = [[-1 for _ in range(15)] for _ in range(15)]
n = int(input())
for i in range(n):
 m = int(input())
 for j in range(m):
   x,y = map(int, input().split())
   g[i][x-1] = y
二次元配列gの作成と入力の受け取りは以上である。
次に問題を解く中心となるコードを実装していく。
まず、全ての正直者の組を表現するために二進数表記を用いることを考える。
二進数の右端の桁を0桁目とする。またkを0から14までの整数とする。
・「k桁目が1である」を「人kは正直者である」
・「k桁目が0である」を「人kは不親切な人である」
作り出した正直者の組それぞれに対して何らかの処理を行うため、
これは全bit探索である。
「正直者の組を作りだす」部分のコード。
・カウンタ変数iを1から2^15まで変化させ、次の処理を繰り返す。
・正直者の番号を格納する要素数nの配列honestsをデフォルト値0で作る。
・iを二進数で表現したときj桁目が1であればhonests[j]に1を追加する。
for i in range(1<<n):
 honests = [0 for _ in range(n)]
 for j in range(n):
   if (i>>j) &1:
     honests[j] = 1 
honests[j]が1であることは,人jは正直者であると仮定することに対応する。
次はhonestsの仮定と証言gに矛盾がないか調べ、求める値「N人のうち
正直者であり得る最大人数」を出力するまでの実装をおこなう。
仮定と証言に矛盾があればそのhonestsで表現された組はあり得ない。
・求める値「N人のうち正直者であり得る最大人数」を格納するための
変数ansをデフォルト値0で用意しておく。
求める値は0以上の値であり以下のループ処理によって、
より大きな値で更新され得る。最終的に最大値が格納される。
・ある正直者の組に矛盾がなかったことを表す変数okをデフォルト値
Trueで用意しておく
・外側のループで配列honestsを作る。作ったhonestsの要素を順に調べる。
honests[j]が1ならば証言g[j]は正しいのでg [j]を以下のように調べる。
・g[j][k]が-1ならば何もしなくてよいので次の証言を調べるループへ移る。
・g[i][k]がhonests[k]の値と異なるならばこの正直者の組はあり得ないので
変数okをFalseにする。
・okがTureのときhonestsの要素の値が1であるものの数（つまり正直者の数）を
数えてansより大きいならばその値をansに代入する。
・最終的なansの値を出力する。
'''

Submission status: Accepted

Solution code:
g = [[-1 for _ in range(15)] for _ in range(15)]
n = int(input())
ans=0
for i in range(n):
  m = int(input())
  for j in range(m):
    x,y = map(int, input().split())
    g[i][x-1] = y
for i in range(1<<n):
  honests = [0 for _ in range(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())
evidences = [[] for _ in range(n)]
for i in range(n):
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        evidences[i].append((x-1, y))
result = 0
for i in range(1, 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:
        result = max(result, bin(i)[2:].count('1'))
print(result)

Submission status: Accepted

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

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

honest = []
for i in range(2 ** n):
    flag = 0
    for j in range(n):
        if (i >> j)&1 == 1: #j番目は正直であるとき
            for person_state in xy[j]:
                if (i >> (person_state[0]-1) & 1) != person_state[1]:
                    flag = 1 #矛盾が生じるとflagを立てる
                    break
    if flag == 0:
        honest += [bin(i)[2:].count("1")]

print(max(honest))

Submission status: Accepted

Solution code:
N = int(input())
Z = []
max = 0
for i in range(N):
    A = int(input())
    Z.append([list(map(int, input().split())) for i in range(A)])
for a in range(2 ** N):
    flag = 1
    for i in range(N):
        if (((a >> i) + 1) & 1):
            continue
        z = Z[i]
        for x in z:
            if not (((a >> (x[0] - 1)) + 1 - x[1]) & 1):
                flag = 0
                break
        if flag == 0:
            break
    if flag == 1:
        x = bin(a).count('1')
        if x > max:
            max = x
print(max)

Submission status: Accepted

Solution code:
N = int(input())
Z, W = [], []
for i in range(N):
    A = int(input())
    Z.append([list(map(int, input().split())) for i in range(A)])
for a in range(2 ** N):
    flag = 1
    for i in range(N):
        if (((a >> i) + 1) & 1):
            continue
        z = Z[i]
        for x in z:
            if not (((a >> (x[0] - 1)) + 1 - x[1]) & 1):
                flag = 0
                break
        if flag == 0:
            break
    if flag == 1:
        W.append(a)
W = [bin(x).count("1") for x in W]
print(max(W))

Submission status: Accepted

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

Submission status: Accepted

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

opinions = []
for i in range(N):
    opinion = [-1]*N
    for j in range(A[i]):
        if Y[i][j] == 0:
            opinion[X[i][j]-1] = 0
        elif Y[i][j] == 1:
            opinion[X[i][j]-1] = 1
    opinions.append(opinion)
answer = 0


for i in range(2**N):
    check = 0
    count = 0
    
    for j in range(N):
        if ((i >> (N-j-1)) & 1) == 1:
            count += 1
            for k in range(A[j]):
                num = X[j][k]
                if ((i >> (N-num)) & 1) == Y[j][k]:
                    
                    continue
                else:
                    check = -1
                    break
            
    
    if check == 0:
        answer = max(answer,count)
    
    
print(answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N  = int(input())
    R = [[] for i in range(N)]
    for i in range(N):
        A = int(input())
        R[i] = [list(map(int, input().split())) for i in range(A)]
    ans = 0
    for i in range(1<<N):
        CNT = 0
        for j in range(N):
            if not (i>>j & 1):
                continue
            CNT += 1
            for x, y in R[j]:
                if y == 1 and (i>>(x-1) & 1):
                    continue
                elif y == 0 and (not (i>>(x-1) & 1)):
                    continue
                else:
                    CNT = 0
                    break
            else:
                continue
            break

        ans = max(ans, CNT)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict, deque

n, a, s, h = int(input()), [], [], []
for i in range(n): a.append(int(input())); s.append(list(list(map(int, input().split())) for _ in range(a[i])))
for i in range(2 ** n):
    flag = False
    for j in range(n):
        if (i >> j) & 1:
            for ps in s[j]:
                if (i >> (ps[0]-1) & 1) != ps[1]: flag = True; break
    if not flag: h.append(bin(i)[2:].count('1'))
print(max(h))

Submission status: Accepted

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


mx=0
for mask in range(1<<n):
    honest=[0]*n
    clear=True
    for i in range(n):
        if ((mask>>i)&1)==0:
            honest[i]+=1
    for i in range(n):
        if honest[i]==1:
            for k in range(a[i]):
                if honest[l[i][k][0]-1]!=l[i][k][1]:
                    clear=False
    if clear:
        ans=sum(honest)
        mx=max(ans,mx)

print(mx)

Submission status: Accepted

Solution code:
n= int(input())
test = [[]for _ in range(n)]
for i in range(n):
    num = int(input())
    for j in range(num):
     a, b= map(int,input().split())
     test[i].append([a-1,b])
ans = 0
for i in range(1,2**n):
    flag = 0
    for j in range(n):
        if(i>>j)&1 == 1:
            for x,y in test[j]:
                if(i>>x)&1 !=y:
                    flag = 1
                    break
    if flag == 0:
        ans = max(ans,bin(i)[2:].count('1'))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = []
xy = []
for i in range(n):
    a += [int(input())]
    xy += [[list(map(int,input().split())) for i in range(a[i])]]
honest = []
for i in range(2 ** n):
    flag = 0
    for j in range(n):
        if (i >> j)&1 == 1: #j番目は正直であるとき
            for person_state in xy[j]:
              if (i >> (person_state[0]-1) & 1) != person_state[1]:
                  flag = 1 #矛盾が生じるとflagを立てる
                  break
    if flag == 0:
        honest += [bin(i)[2:].count("1")]
print(max(honest))

Submission status: Accepted

Solution code:
n = int(input())
xy_ls = [0]*n

for i in range(n):
    a = int(input())
    ls = [list(map(int, input().split())) for _ in range(a)]
    xy_ls[i] = ls 

ok_ls = []
for i in range(2**n):
    ok = 1
    people = [0]*n
    for j in range(n):
        if i >> j & 1:
            people[j] = 1
    for j in range(n):
        if people[j] == 1:
            for xy in xy_ls[j]:
                if xy[1] != people[xy[0]-1]:
                    ok = 0
    if ok:
        ok_ls.append(len([i for i in people if i == 1]))

print(max(ok_ls))

Submission status: Accepted

Solution code:
import sys

N = int(input())
List = [[-1] * 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())
        List[i][x - 1] = y

Max = 0

for i in range(2 ** N):

    flag = True
    Sum = 0
    for j in range(N):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            for k in range(N):
                if (List[j][k] != int((i >> k) & 1)) and List[j][k] != -1:
                    flag = False
            Sum += 1

    if flag:
        #print(i,Sum)
        Max = max(Max, Sum)

print(Max)

Submission status: Accepted

Solution code:
from itertools import product 
n=int(input())
x=[]
ans=0
for _ in range(n):
    temp=[]
    A=int(input())
    for _ in range(A):
        temp.append(list(map(int,input().split())))
    x.append(temp)
for i in product([0,1],repeat=n):
    for j in range(n):
            for k in x[j]:
                if i[k[0]-1]!=k[1] and i[j]==1:
                    break
            else:
                continue
            break
    else:
      ans=(max(ans,list(i).count(1))) 
print(ans)

Submission status: Accepted

Solution code:
import os, sys, re, math

N = int(input())
honest = []
liar = []

for i in range(N):
    a = int(input())
    h = []
    l = []
    for j in range(a):
        (x, y) = [int(n) for n in input().split()]
        if y == 1:
            h.append(x)
        else:
            l.append(x)
    honest.append(h)
    liar.append(l)

answer = 0
for i in range(2 ** N - 1, -1, -1):
    b = ('{:0%db}' % N).format(i)
    truth = True
    for j in range(N):
        if b[j] == '1':
            for h in honest[j]:
                if b[h - 1] != '1':
                    truth = False
                    break
            if not truth:
                break
            for l in liar[j]:
                if b[l - 1] != '0':
                    truth = False
                    break
        if not truth:
            break
    if truth:
        answer = max(answer, len(b.replace('0', '')))

print(answer)

Submission status: Accepted

Solution code:
N = int(input())
A = {}

for i in range(N):
    num = int(input())
    tmp = [list(map(int, input().split())) for _ in range(num)]
    A[i] = tmp

ans = 0
# bit: pattern of hornest 1 and unkind 0
for bit in range(2**N):
    tmp = bit
    flag = True
    # check
    for i in range(N):
        if not (bit >> i & 1):  # case of unkind => continue
            continue
        # case of honest
        for x, y in A[i]:
            if (bit >> (x - 1) & 1) != y:   # check if really honest
                flag = False
                break
    if flag:
        ans = max(ans, bin(bit).count("1"))
print(ans)

Submission status: Accepted

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

for i in range(2**n):
    honest = []
    contradiction_f = False

    for j in range(n):
        if i>>j & 1:
            honest.append(j)

    for j in honest:
        judge = lst[j]
        for k in judge:
            if k[1] == 1:
                if not k[0] in honest:
                    contradiction_f = True
                    break
            else:
                if k[0] in honest:
                    contradiction_f = True
                    break

    if not contradiction_f:
        ans = max(ans, len(honest))

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
n=int(input())
A=[]
xy=[[]]*n
for i in range(n):
    a=int(input())
    A.append(a)
    xy[i]=[list(map(int,input().split())) for _ in range(a)]

ans=0

for bit in range(1<<n):
    tmp=0
    for i in range(n):
        if bit>>i & 1:
            cnt=0
            for elem in xy[i]:
                if elem[1]==1:
                    if bit>>(elem[0]-1) & 1:
                        cnt+=1
                else:
                    if not (bit>>(elem[0]-1) & 1):
                        cnt+=1
            if cnt==A[i]:
                tmp+=1
            else:
                continue
    
    if tmp==bin(bit).count("1"):
        ans=max(bin(bit).count("1"),ans)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n = int(input())

answers = []
for i in range(n):
	a = int(input())
	answers.append((i, []))
	for j in range(a):
		(x, y) = [int(k) for k in input().split()]
		answers[i][1].append((x, y))

lst = []
combi_lst = [i for i in range(n)]
for i in range(n, -1, -1):
	for balls in itertools.combinations(combi_lst, i):
		lst = [True if j in balls else False for j in range(n)]
		success = True
		for i, ans in enumerate(answers):
			if lst[i] == False:
				continue
			for x, y in ans[1]:
				if y == 1 and lst[x - 1] == False:
					success = False
				if y == 0 and lst[x - 1] == True:
					success = False
		if success:
			print(sum(lst))
			exit()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3]
import sys
sys.setrecursionlimit(2000)

N = int(input())
syogen = []
for i in range(N):
    N_a = int(input())
    syogen_a = []
    for _ in range(N_a):
        x, y = input().split()
        syogen_a.append([int(x) - 1, int(y)])
    syogen.append(syogen_a)


def syojiki(i):
    for x, y in syogen[i]:
        if y == 1:
            syojiki_list.append(x)
            if len(syojiki_list) >= N:
                return
            syojiki(x)


def check_syojiki(syojikitati):
    d = {}
    for s in range(N):
        if s in syojikitati:
            d[s] = 1
        else:
            d[s] = 0

    for s in syojikitati:
        d[s] = 1
        for x, y in syogen[s]:
            if d[x] != y:
                return False
    return True


max_syojiki = 0

for i in range(2 ** N):
    d = {}
    syojiki_list = []
    for j in range(N):
        if (i >> j) & 1:
            syojiki_list.append(j)
            syojiki(j)
    syojiki_list = list(set(syojiki_list))
    if check_syojiki(syojiki_list):
        max_syojiki = max(max_syojiki, len(syojiki_list))

print(max_syojiki)

Submission status: Accepted

Solution code:
import os, sys, re, math

N = int(input())
honest = []
liar = []

for i in range(N):
    a = int(input())
    h = []
    l = []
    for j in range(a):
        (x, y) = [int(n) for n in input().split()]
        if y == 1:
            h.append(x)
        else:
            l.append(x)
    honest.append(h)
    liar.append(l)

for i in range(2 ** N - 1, -1, -1):
    b = ('{:0%db}' % N).format(i)
    truth = True
    for j in range(N):
        if b[j] == '1':
            for h in honest[j]:
                if b[h - 1] != '1':
                    truth = False
                    break
            if not truth:
                break
            for l in liar[j]:
                if b[l - 1] != '0':
                    truth = False
                    break
        if not truth:
            break
    if truth:
        break

if truth:
    print(len(b.replace('0', '')))

Submission status: Accepted

Solution code:
n = int(input())
d = dict()
for i in range(n):
    a = int(input())
    for j in range(a):
        l = d.get(i, [])
        p, t = list(map(int, input().split(' ')))
        l.append((p-1, t))
        d[i] = l
# d[i] に i番の人の証言のlistがあるので 全パターン(=2^15)で矛盾しないか試す？
def get_bit_array(num):
    res = []
    while num > 0:
        res.append(num%2)
        num //= 2
    while len(res) < n:
        res = res + [0]
    return res[::-1]

def valid(tfs):
    for i in range(len(tfs)):
        honest = tfs[i]
        if not honest:  # 嘘つきは無視する
            continue
        for (person, tf) in d.get(i, []):  # 合ってる？
            if tfs[person] != tf:
                return False
    return True

ans = 0
def f(num):
    global ans
    if num >= 2**n:
        return
    tfs = get_bit_array(num)  # tfs = [1,0,1,0,...0] true or flase 
    total = sum(tfs)
    if valid(tfs):
        ans = max(ans, total)

for i in range(int(2**n)):
    f(i)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
dic = {i+1: [] for i in range(n)}

for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        dic[i+1].append((x, y))
#print(dic)
ans = 0
for i in range(1 << n):
    flag = 0
    s = str(bin(i))
    cnt = s.count("1")
    #print(s,cnt)

    for j in range(n):
        if (i >> j) & 1:
            for x, y in dic[j + 1]:
                if str(bin((i>>(x-1))))[-1] == str(y):
                    continue
                else:
                    flag = 1
                    break
            
            
            
    if flag != 1:
        ans = max(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

n = I()
shogens = []

for i in range(n):
    a = I()
    shogens.append([])
    for j in range(a):
        x,y = LI()
        x -= 1
        shogens[-1].append((x,y))

def is_honest(i,j):
    return (i >> j) % 2 == 1

def honest_cnt(i):
    ans = 0
    for j in range(n):
        ans += is_honest(i,j)
    return ans 

ans = 0
for i in range(1 << n):
    ok = True
    for j in range(n):
        if not is_honest(i,j):continue
        for (x,y) in shogens[j]:
            if y == 0 and is_honest(i,x):ok = False
            if y == 1 and not is_honest(i,x):ok = False
    if ok:
        ans = max(ans, honest_cnt(i))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [[] for _ in range(n)]
for i in range(n):
  num = int(input())
  for j in range(num):
    person, state = map(int, input().split())
    a[i].append([person-1, state])
honest = 0
for i in range(1, 2**n):
  flag = True
  for j in range(n):
    if (i>>j)&1 == 1:
      for x, y in a[j]:
        if (i>>x)&1 != y:
          flag = False
          break
  if flag:
    honest = max(honest, bin(i)[2:].count('1'))
print(honest)

Submission status: Accepted

Solution code:
from itertools import product 

n = int(input())
XY = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())          
        XY[i].append((x-1,y))
ans = 0
bits = list(product([0,1],repeat=n))
for bit in bits:
    honest_tes = []
    honest_idx = []
    honest_list = [0 for _ in range(n)]
    flag = True
    for who, h in enumerate(bit):
        if h == 1:
            honest_tes.append(XY[who])
            honest_idx.append(who)
            honest_list[who] = 1
    for idx in honest_idx:
        for x, y in XY[idx]:
            if honest_list[x] != y:
                flag = False
                break
    if flag:
        ans = max(ans, len(honest_idx))
print(ans)

Submission status: Accepted

Solution code:
import itertools

def main():
    N = int(input())
    BIT = list(itertools.product([True,False], repeat=N))
    P = [[(0,0)]]
    for i in range(1,N+1):
        A =  int(input())
        L = []
        for _ in range(A):
            x,y = map(int,input().split())
            L.append((x,y))
        P.append(L)

    ans = 0

    for b in BIT:
        cnt = 0
        flag = True
        HU = [-1]*(N+1)
        for i in range(1,N+1):
            if b[i-1]:
                cnt += 1
                for hu in P[i]:
                    if b[hu[0]-1] != (hu[1]==1):
                        flag = False
                        break
        if flag:
            ans = max(ans,cnt) 


    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

A_list = []
for i in range(N):
    A = int(input())
    A_list.append([list(map(int, input().split())) for _ in range(A)])


def judge(mask):
    for i in range(N):
        if (mask>>i & 1)==0:
            continue
        for xy in A_list[i]:
            x = xy[0]-1
            y = xy[1]
            if y==0 and (mask>>x & 1):
                return False
            if y==1 and (mask>>x & 1)==0:
                return False
    return True


num_max = 0
for mask in range(1<<N):
    if judge(mask):
        num = 0
        for i in range(N):
            num += mask>>i & 1
        num_max = max(num, num_max)

print(num_max)

Submission status: Accepted

Solution code:
#donut29
n=int(input())
lst=[]
for i in range(n):
    a=int(input())
    b=[]
    for j in range(a):
        x,y=map(int,input().split())
        x-=1
        b.append([x,y])
    lst.append(b)
ans=0
for i in range(2**n):
    on=[]
    switch=0
    for j in range(n):
        if ((i>>j)&1):
            on.append(j)
    for j in on:
        judge=lst[j]
        for k in judge:
            if k[1]==1:
                if not k[0] in on:
                    switch=1
            else:
                if k[0] in on:
                    switch=1
    if switch==0:
        ans=max(ans,len(on))

print(ans)

Submission status: Accepted

Solution code:
# ビット全探索
from itertools import product

N = int(input())

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

result = 0
for i in product([0, 1], repeat=N):
    consistent = True
    for j in range(N):
        if i[j] == 0:
            continue
        for x, y in evidences[j]:
            if i[x] != y:
                consistent = False
                break
        if not consistent:
            break
    if consistent:
        result = max(result, i.count(True))
print(result)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
S = [[] for I in range(0,N)]
for T in range(0,N):
    A = int(input())
    S[T] = np.zeros((A,2),dtype=int)
    for TT in range(0,A):
        S[T][TT,:] = np.array([int(X) for X in input().split()])
    
MAX = 0
for P in range(pow(2,N)-1,-1,-1):
    Bin    = [int(X) for X in list(('{:0'+str(N)+'b}').format(P,'b'))]
    BIndex = [I for I,N in enumerate(Bin) if N==1]
    Flag   = True
    for PT in BIndex:
        for PTB in range(0,S[PT].shape[0]):
            if S[PT][PTB,1]==0 and (S[PT][PTB,0]-1) in BIndex:
                Flag = False
                break
            if S[PT][PTB,1]==1 and (S[PT][PTB,0]-1) not in BIndex:
                Flag = False
                break
        if not Flag:
            break
    if Flag:
        MAX = len(BIndex)
        break
print(MAX)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    A = [[] for i in range(n)]
    ans = 0
    for i in range(n):
        a = int(input())
        tmp = {}
        for j in range(a):
            x,y = map(int,input().split())
            tmp[x-1] = y
        A[i] = tmp
    #print(A)
    for i in range(2**n):
        kouho = []
        for j in range(n):
            if  (i>>j)&1:
                kouho.append(j)
        honest = {}
        for j in range(n):
            if j in kouho:
                honest[j] = 1
            else:
                honest[j] = 0
        flag = True
        #print(kouho)
        for j in kouho:
            hatugen = A[j]
            for k in hatugen.keys():
                if honest[k]!=hatugen[k]:
                    flag = False
        if flag:
            ans = max(ans,len(kouho))
    print(ans)

main()

Submission status: Accepted

Solution code:
from itertools import product

N = int(input())
xy = [[] for i in range(N)]

for i in range(N):
    for j in range(int(input())):
        xy[i].append(list(map(int, input().split())))
        
ans = 0
for bit in product([0,1], repeat=N):
    f = 0
    for i, j in enumerate(bit):
        if j == 1:
            for x, y in xy[i]:
                if bit[x-1] != y:
                    f = 1
                    break
    if f == 0:
        ans = max(ans, sum(bit))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
XY = []
for i in range(n):
    a = int(input())
    xy = []
    for j in range(a):
        x, y = map(int, input().split())
        xy.append([x, y])
    XY.append(xy)
ans = 0
for i in range(2 ** n):
    s = [0] * n
    cnt = 0
    case = True
    for j in range(n):
        if (i >> j) & 1:
            s[j] = 1
            cnt += 1
    for k in range(n):
        if s[k] == 1:
            for l in range(len(XY[k])):
                if s[XY[k][l][0] - 1] != XY[k][l][1]:
                    case = False
    if case is True:
        ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
XY = []
for i in range(n):
    a = int(input())
    xy = []
    for j in range(a):
        x, y = map(int, input().split())
        xy.append([x, y])
    XY.append(xy)
ans = 0
for i in range(2 ** n):
    s = [0] * n
    cnt = 0
    case = True
    for j in range(n):
        if (i >> j) & 1:
            s[n - 1 - j] = 1
            cnt += 1
    for k in range(n):
        if s[k] == 1:
            for l in range(len(XY[k])):
                if s[XY[k][l][0] - 1] != XY[k][l][1]:
                    case = False
    if case is True:
        ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
XY = []
for i in range(n):
    a = int(input())
    xy = []
    for j in range(a):
        x, y = map(int, input().split())
        xy.append([x, y])
    XY.append(xy)
ans = 0
for i in range(2 ** n):
    s = [0] * n
    cnt = 0
    case = 0
    for j in range(n):
        if (i >> j) & 1:
            s[n - 1 - j] = 1
            cnt += 1
    for k in range(n):
        if s[k] == 1:
            for l in range(len(XY[k])):
                if s[XY[k][l][0] - 1] != XY[k][l][1]:
                    case = 1
    if case == 0:
        ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
X = {}

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

ans = 0
for bit in range(2 ** N):
    tmp = bit
    flag = True
    for i in range(N):
        if not (bit >> i & 1):
            continue

        for x, y in X[i]:
            if (bit >> (x - 1) & 1) != y:
                flag = False
                break
                
    if flag:
        ans = max(ans, bin(bit).count("1"))

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

ans = 0
for i in range(2**n):
    hone = set()
    unki = set()
    for j in range(n):
        if i >> j & 1:
            hone |= {j + 1}
            for k in a[j]:
                if k[1] == 1:
                    hone |= {k[0]}
                else:
                    unki |= {k[0]}
        else:
            unki |= {j + 1}
    if hone & unki == set():
        ans = max(ans, len(hone))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N = int(input())
G = {i:[] for i in range(1,N+1)}
for i in range(1,N+1):
    a = int(input())
    G[i] = [list(map(int,input().split())) for _ in range(a)]
cmax = 0
for z in product((0,1),repeat=N+1):
    if z[0]==0:
        X = []
        for i in range(1,N+1):
            if z[i]==1:
                X.append(i)
        A = []
        B = []
        for i in X:
            for x,y in G[i]:
                if y==1:
                    A.append(x)
                else:
                    B.append(x)
        flag = 0
        for a in A:
            if a not in X:
                flag = 1
                break
        for b in B:
            if b in X:
                flag = 1
                break
        if flag==0:
            cmax = max(cmax,sum(z[1:]))
print(cmax)