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 collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

n = int(input())
ls_a = []
ls_xy = []
for i in range(n):
    a = int(input())
    ls_a.append(a)
    xy = mylistinput(a)
    ls_xy.append(xy)
# print(a)
# print(ls_xy)

ans = 0
for i in range(2**n):
    flag = True
    for j in range(n):
        if i & (2**j):
            for k in range(len(ls_xy[j])):
                x = ls_xy[j][k][0] - 1
                y = ls_xy[j][k][1]
                if y==1:
                    if i & (2**x) > 0:
                        pass
                    else:
                        flag = False
                elif y==0:
                    if i & (2**x) == 0:
                        pass
                    else:
                        flag = False
    if flag:
        tmp = sum( list(map(int,list(bin(i)[2:]))) )
        ans = max( ans, tmp )

print(ans)

Submission status: Accepted

Solution code:
import itertools

N = int(input())
L = []
for i in range(N):
    A = int(input())
    x = [tuple(map(int,input().split())) for i in range(A)]
    L.append(x)
    
X = list(itertools.product([0,1],repeat=N))
ans = 0

for i in X:
    cnt = True
    for j,value in enumerate(i):
        if value  == 1:
            for k,m in L[j]:
                if i[k-1] != m:
                    cnt = False
    if cnt:
        ans = max(ans,sum(i))
           
print(ans)

Submission status: Accepted

Solution code:
import sys, heapq, bisect, math, fractions
from collections import deque

N = int(input())
xy = [[] for _ in range(N)]
for i in range(N):
    a = int(input())
    for _ in range(a):
        xy[i].append(tuple(map(int, input().split())))
        
def ok(i: int, j: int):
    for x, y in xy[j]:
        if y == 0 and (i >> (x - 1) & 1 == 1):
            return False
        if y == 1 and (i >> (x - 1) & 1 == 0):
            return False
    return True

res = 0
for i in range(2 ** N):
    cnt = 0
    for j in range(N):
        if i >> j & 1 == 1:
            cnt += 1
            if not ok(i, j):
                break
    else:
        res = max(res, cnt)

print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()
n=I()
lis=[[]for i in range(n)]
for i in range(n):
    u=I()
    for j in range(u):
        a,b=MI()
        lis[i].append([a,b])
#print(lis)
z=[]
for x in range(2**n):
    u=[]
    for j in range(n):
        u.append(x%2)
        x=x>>1
    #print(u)
    count2=0
    for i in range(n):
        if u[i]==1:
            count=0
            for k in range(len(lis[i])):
                if lis[i][k][1]==u[lis[i][k][0]-1]:
                    count+=1
            if count==len(lis[i]):
                count2+=1
    if count2==sum(u):
        z.append(sum(u))
print(max(z))

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    shogen=[]
    nums=[]
    for i in range(n):
        a=int(readline())
        nums.append(a)
        xy=[0]*a
        for j in range(a):
            xy[j]=list(map(int,readline().split()))
        shogen.append(xy)
    
    res=0
    for i in range(1<<n):
        output=[]
        for j in range(n):
            if(i>>j)&1:
                output.append(j)
        
        flag=True
        for p in output:
            num_p=nums[p]
            shogen_p=shogen[p]
            for j in range(num_p):
                if shogen_p[j][1]==1:
                    if shogen_p[j][0]-1 in output:
                        pass
                    else:
                        flag=False
                        break
                else:
                    if shogen_p[j][0]-1 in output:
                        flag=False
                        break
                    else:
                        pass
            if flag==False:
                break
        else:
            res=max(res,len(output))

    print(res)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N=int(input())
    G=[None]
    for i in range(N):
        A=int(input())
        G.append([tuple(map(int, input().split())) for _ in range(A)])
    ans=0
    for p in range(1<<N):
        pp=[0] + [1 if p&(1<<i) else 0 for i in range(N)]
        judge=True
        for v in range(1,N+1):
            if pp[v]:
                for to,h in G[v]:
                    if pp[to]!=h: judge=False
        if judge:
            ans = max(ans, popcount(p))
    print(ans)

def popcount(x):
    x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555)
    x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333)
    x = x + (x >> 4) & 0x0f0f0f0f0f0f0f0f
    x += x >> 8
    x += x >> 16
    x += x >> 32
    return x & 0x7f

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))

def main():
    n = int(input())
    Present = [[] for _ in range(n)] # 人による
    for i in range(n):
        a = int(input())
        for j in range(a):
            x,y = readInts()
            Present[i].append([x-1,y]) # 0-indexed
    #print(Present)
    ans = 0
    # こっから、誰が正直者で、正直者ではないかをbit全探索
    for bit in range(1 << n):
        cnt = 0
        for i in range(n):
            if bit & (1 << i): # フラグが立っていたらそいつは正直者
                cnt += 1
                for x,y in Present[i]:
                    if y != (bit >> x & 1):
                        break
                else:
                    continue
                break
        else:
            ans = max(ans,cnt)
    print(ans)
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
n = int(input())
evi = []
for _ in range(n):
    m = int(input())
    evi.append([list(map(int, input().split())) for _ in range(m)])
ans = 0
for i in range(1 << n):
    for j in range(n):
        if ((i >> j) & 1) == 1:
            for x,y in evi[j]:
                if ((i >> (x-1))&1) != y:
                    break
            else:
                continue
            break
    else:
        ans = max(ans,bin(i).count('1'))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

N = int(input())
lst = [[] for _ in range(N)]

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


ans = 0
for i in range(2 ** N):
    count = 0
    flag = True
    for j in range(N):
        if (i >> j) & 1: #正直者の時、証言を確認する
            for x, y in lst[j]:
                if y == 1:
                    if (i >> (x - 1)) & 1:
                        continue
                    else:
                        pass
                if y == 0:
                    if (i >> (x - 1)) & 1:
                        pass
                    else:
                        continue
                flag = False
                break
            count += 1
        if not flag:
            break
    if flag:
        ans = max(ans, count)

print (ans)

Submission status: Accepted

Solution code:
import itertools

n = int(input())
lst = []
for i in range(n):
    ai = int(input())
    lsti = []
    for j in range(ai):
        xj, yj = map(int, input().split())
        xj -= 1
        lsti.append([xj, yj])
    lst.append(lsti)

ans = 0
for v in itertools.product([0, 1], repeat=n):
    ok = 1
    for i in range(n):
        if v[i] == 0: continue
        if ok == 0: break
        lsti = lst[i]
        for xj, yj in lsti:
            if v[xj] != yj:
                ok = 0
                break
    if ok == 1:
        ans = max(ans, sum(v))

print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = [0 for _ in range(n)]
    xy = [None for _ in range(n)]
    for i in range(n):
        a[i] = int(input())
        xy[i] = [None for _ in range(a[i])]
        for j in range(a[i]):
            xy[i][j] = tuple(map(int, input().split()))

    ans = 0
    for i in range(1 << n):
        m = [0 for _ in range(n)]
        p = 0
        for j in range(n):
            m[j] = (1 if i & (1 << j) else 0)
            p += (1 if i & (1 << j) else 0)
        if p < ans:
            continue
        good = True
        for j in range(n):
            if m[j]:
                for k in range(a[j]):
                    if m[xy[j][k][0]-1] != xy[j][k][1]:
                        good = False
                        break
            if not good:
                break
        if good:
            ans = p

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())

#正直者も発言に矛盾が生じない
L=[[-1]*N for _ in range(N)]
for i in range(N):
    A=int(input())
    for a in range(A):
        x,y=map(int, input().split())
        L[i][x-1]=y
ans=0
for b in range(2**N):
    ok=True
    for i in range(N):
        if b>>i&1==1:
            l=L[i]
            for j,x in enumerate(l):
                if x!=-1 and b>>j&1!=x:
                    ok=False
    if ok:
        ans=max(ans, bin(b).count("1"))

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    cnt = 0
    temp = [-1]*n
    for j in range(n):
        if (i >> j) & 1:
            cnt += 1
            temp[j] = 1
        else:
            temp[j] = 0
    flag = True
    for j in range(n):
        if (i >> j) & 1:
            for x, y in X[j]:
                if temp[x] != y:
                    flag = False
    if flag:
        ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N = int(input())
state = []

for _ in range(N):
    A = int(input())
    l = []
    
    for _ in range(A):
        x, y = map(int, input().split())
        l.append((x-1, y))
    
    state.append(l)
    
ans = 0

for S in range(2**N):
    flag = True
    cnt = 0
    
    for i in range(N):
        if (S>>i)&1:
            for x, y in state[i]:
                if y==0 and (S>>x)&1:
                    flag = False
                elif y==1 and not (S>>x)&1:
                    flag = False
            
            cnt += 1
    
    if flag:
        ans = max(ans, cnt)

print(ans)

Submission status: Accepted

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

for _ in range(N):
    A.append([tuple(map(int, input().split())) for _ in range(int(input()))])

def exists(state):
    ret = 0
    for i in range(N):
        if ((1 << i) & state) == 0:
            continue
        ret += 1
        for x, y in A[i]:
            if ((state & (1 << (x - 1))) > 0) != (y > 0):
                return 0
    return ret

ans = 0
for state in range(1 << N):
    ans = max(ans, exists(state))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
xy=[[]for _ 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 i in range(1,1<<n):
  syojiki=[(i&(1<<j)!=0)+0 for j in range(n)]
  flag=True
  for j in range(n):
    for x,y in xy[j]:
      if syojiki[x-1]!=y and syojiki[j]==1:flag=False
  if flag:
    ans=max(ans,syojiki.count(1))
print(ans)

Submission status: Accepted

Solution code:
#標準入力受け取り
N = int(input())
shougen = []
A_lis = []
for _ in range(N):
    A = int(input())
    A_lis.append(A)
    minishougen = []
    for j in range(A):
        xy = list(map(int, input().split()))
        minishougen.append(xy)
    shougen.append(minishougen)

#ビットの配列作る
bit_lis = []
for i in range(2 ** N):
    mini_bit_lis = []
    for j in range(N):
        mini_bit_lis.append(i % 2)
        i = i // 2
    bit_lis.append(mini_bit_lis)
    
#ビットの配列について全探索を行う
ans = 0
for i in range(2 ** N):
    flag = 0
    for l in range(N):
        if bit_lis[i][l] == 1:
            for k in range(A_lis[l]): 
                if shougen[l][k][1] != bit_lis[i][shougen[l][k][0] - 1]:
                    flag = 1
                    break
        if flag == 1:
            break
    if flag == 0:
        tmp = sum(bit_lis[i])
        if tmp > ans :
            ans = tmp
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
X=[]
Y=[]
for n in range(N):
    A=int(input())
    lx=[]
    ly=[]
    for m in range(A):
        x,y=map(int,input().strip().split())
        lx.append(x)
        ly.append(y)
    X.append(lx)
    Y.append(ly)    

def judge(l,X,Y):
    honest=True
    for n in range(N):
        if l[n]==1:
            for i in range(len(X[n])):
                if l[X[n][i]-1]!=Y[n][i]:
                    honest=False
    return honest

ans=0
def dfs(l,N): #honest=1,unkind=0
    if len(l)==N:
        global ans
        if judge(l,X,Y):
            ans=max(ans,sum(l))
            return
    else:
        for n in range(2):
            l.append(n)
            dfs(l,N)
            l.pop()

dfs([],N)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())

talk=[]

for _ in range(n):
    a=int(input())
    sei=set([])
    uso=set([])
    for __ in range(a):
        x,y=map(int,input().split())
        if y==1:
            sei.add(x-1)
        else:
            uso.add(x-1)
    
    talk.append((sei,uso))
#print(talk)
result=0
for i in range(2**n):
    flag=0
    s=str(bin(i))[2:].zfill(n)
    #print("#####",s)
    kari_sei=set([])
    kari_uso=set([])

    for j in range(n):
        if i>>j &1:
            kari_sei.add(j)
        else:
            kari_uso.add(j)

    flag=0
    for item in kari_sei:
        for item2 in talk[item][0]:
            if item2 not in kari_sei:
                flag=1
                break
        if flag==1:
            break
        else:
            for item2 in talk[item][1]:
                if item2 not in kari_uso:
                    flag=1
                    break
            
    
    if flag==0:
        result=max(result,s.count("1"))

print(result)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
lists = deque()
A = deque() 
ans = 0
for _ in range(n):
    a = int(input())
    A.append(a)
    tmp = [list(map(int, input().split())) for _ in range(a)]
    lists.append(tmp)

for bit in range(1<<n):
    flag = True
    is_honest = [(bit>>i)&1 for i in range(n)]
    for i in range(n):#i人目の証言を検証する
        if is_honest[i] == 0:#i人目が「不親切」ならその人の証言は無視
            continue
        for k in range(A[i]):#i人目のk個目の証言を検証する
            x,y = lists[i][k]
            x -= 1
            #番号xとyが一致しているかどうか
            if is_honest[x] != y:
                flag = False
    if flag:
        ans = max(ans, sum(is_honest))
print(ans)

Submission status: Accepted

Solution code:
import itertools

N = int(input())

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

ans = 0
for hu in list(itertools.product([0,1], repeat=N)):
    xy_idx = 0
    ok_flg = 1
    for i in range(N):
        if hu[i]:
            for _ in range(A[i]):
                x, y = xy[xy_idx]
                x -= 1
                if hu[x] != y:
                    ok_flg = 0
                    break
                xy_idx += 1
        else:
            xy_idx += A[i]
    if ok_flg:
        ans = max(ans, sum(hu))

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from itertools import permutations, accumulate
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
# from fractions import gcd
# from math import gcd
import sys


def I(): return int(input())  # '123' -> 123


def Is(): return map(int, input().split())  # '123 456' -> 123, 456


def LI(): return list(map(int, input().split()))  # '123 456' -> [123, 456]


def TI(): return tuple(map(int, input().split()))  # '123 456' -> (123, 456)


def IR(n): return [I() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def TIR(n): return [TI() for _ in range(n)]


def S(): return input()


def Ss(): return input().split()  # 'aa bb' -> 'aa','bb' or ['aa','bb']


def LS(): return list(input())  # 'abc123' -> ['a','b','c','1','2','3']


def SR(n): return [S() for _ in range(n)]


def SsR(n): return [Ss() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


sys.setrecursionlimit(1000000)
MOD = 1000000007
INF = float('inf')

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

ans = 0

for bit in range(1, 1 << N):
    contradiction = False
    for i in range(N):
        if bit & (1 << i):
            for x, y in XY[i]:
                if ((bit >> x) & 1) ^ y:
                    contradiction = True
    if not contradiction:
        ans = max(ans, bin(bit).count("1"))

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input()) 
insist_num = []
insists = []

for i in range(N):
    insist_num.append(int(input()))
    insists.append([list(map(int,input().split())) for _ in range(insist_num[-1])])

all_patterns = ["0","1"] # 1が正直者とする
for _ in range(N-1):
    all_patterns = [j+i for i in ["0","1"] for j in all_patterns]

ok = [True for _ in range(len(all_patterns))]

for h, pattern in enumerate(all_patterns):
    for i, honest in enumerate(list(pattern)):
        if honest == "1":
            for j in range(insist_num[i]):
                if str(insists[i][j][1]) != str(list(pattern)[insists[i][j][0]-1]):
                    ok[h] = False
                    break
            else:
                continue
            break

max_val = 0
for i, pp in enumerate(ok):
    if pp==True and all_patterns[i].count("1") > max_val:
        max_val = all_patterns[i].count("1")
print(max_val)

Submission status: Accepted

Solution code:

N = int(input()) 
insist_num = []
insists = []

for i in range(N):
    insist_num.append(int(input()))
    insists.append([list(map(int,input().split())) for _ in range(insist_num[-1])])

all_patterns = ["0","1"] # 1が正直者とする
for _ in range(N-1):
    all_patterns = [j+i for i in ["0","1"] for j in all_patterns]

ok = [True for _ in range(len(all_patterns))]

for h, pattern in enumerate(all_patterns):
    for i, honest in enumerate(list(pattern)):
        if honest == "1":
            for j in range(insist_num[i]):
                if str(insists[i][j][1]) != str(list(pattern)[insists[i][j][0]-1]):
                    ok[h] = False
                    break
            else:
                continue
            break

max_val = 0
for i, pp in enumerate(ok):
    if pp==True and all_patterns[i].count("1") > max_val:
        max_val = all_patterns[i].count("1")
print(max_val)

Submission status: Accepted

Solution code:
N = int(input())
L = []
l = []
A = []
ans = 0
for i in range(N):
    a = int(input())
    A.append(a)
    for j in range(a):
        l.append(list(map(int,input().split())))
    L.append(l)
    l = []
for bit in range(1<<N):
    flag = True
    listH = [(bit>>i)&1 for i in range(N)]
    for j in range(N):
        if not listH[j]:
            continue
        for k in range(A[j]):
            x = L[j][k][0]-1
            y = L[j][k][1]
            if listH[x] != y:
                flag = False
    if flag:
        ans = max(ans,sum(listH))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
g = [[-1]*N for i in range(N)]
ans=0
for i in range(N):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        g[i][x-1] = y
for i in range(1 << N):
    d=[0]*N
    for j in range(N):
        if (i >> j & 1) == 1:
            d[j] = 1
    ok = True
    for j in range(N):
        if d[j] == 1:
            for k in range(N):
                if g[j][k] == -1:
                    pass
                elif g[j][k] != d[k]:
                    ok = False
    if ok:
        ans = max(ans,d.count(1)) 
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

ans = 0
for i in range(1<<N):
    honest = []
    unkind = []
    for j in range(N):
        if i & (1<<j):
            honest.append(j)
        else:
            unkind.append(j)
    
    flag = True
    for h in honest:
        for x, y in xy[h]:
            if y == 0 and (x-1) in unkind:
                continue
            if y == 1 and (x-1) in honest:
                continue

            flag = False
    
    if flag:
        ans = max(ans, len(honest))

print(ans)

Submission status: Accepted

Solution code:
N=int(input())

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

        testimony_i.append([x,y])
    
    test.append(testimony_i)

total=0
for i in range(2**N):

    member = format(i,'0{}b'.format(N))

    flg = 0

    for j in range(N):
        if member[j]== '1':

            syogen = test[j]

            for s in syogen:
                if member[s[0]-1]==str(s[1]):
                    continue
                else:
                    flg+=1

    if flg ==0:
        total = max(total , member.count('1')) 

print(total)

Submission status: Accepted

Solution code:
N=int(input())

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

        testimony_i.append([x,y])
    
    test.append(testimony_i)
    
total=0
for i in range(2**N):

    member = format(i,'0{}b'.format(N))

    flg = 0

    for j in range(N):
        if member[j]== '1':

            syogen = test[j]

            for s in syogen:
                if member[s[0]-1]==str(s[1]):
                    continue
                else:
                    flg+=1

    if flg ==0:
        total = max(total , member.count('1')) 

print(total)

Submission status: Accepted

Solution code:
N = int(input())
tes = [[] for _ in range(N+1)]
ans = 0

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

for x in range(1, 2**N):
    HorU = [0] + [(x >> n) & 1 for n in range(N)]
    cand = True
    for i in range(1, N+1):
        for j, y in tes[i]:
            if HorU[j] == 1 and y != HorU[i]:
                cand = False
    if cand:
        temp = (N+1) - sorted(HorU).index(1)
        if ans < temp:
            ans = temp
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2 ** n):
    H_lis = [0 for i in range(n)]
    for j in range(n):
        if ((i >> j) & 1):
            H_lis[j] = 1
    flag = True
    j = 0
    while j < n and flag:
        if H_lis[j] == 1:
            for k in range(A[j]):
                if X[j][k][1] != H_lis[X[j][k][0] - 1]:
                    flag = False
                    break
        j += 1
    if flag:
        ans = max(ans, H_lis.count(1))
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from itertools import product

N = int(input())
info = []

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

whole = np.array(list(product([0,1],repeat=N)), np.bool)

for i, x, y in info:
    b = (whole[:, i] & whole[:, x]==y) | (~whole[:, i])
    whole = whole[b]

print(whole.sum(axis=1).max())

Submission status: Accepted

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

for i in range(2 ** n):
    t = (n - len(bin(i)[2:])) * '0' + bin(i)[2:]
    point = 1
    for index, value in enumerate(t):
        if value == '1':
            for com in comment[index]:
                if t[com[0] - 1] == str(com[1]):
                    continue
                else:
                    point = 0
                    break
    if point == 1:
        ans = max(ans, t.count('1'))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
n = int(input())
testimony = []
ans = 0

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

for bits in product(range(2), repeat=n):
    for num, bit in enumerate(bits):
        if bit:
            for x, y in testimony[num]:
                if bits[x-1] != y:
                    break
            else:
                continue
            break
    else:
        ans = max(ans, sum(bits))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [[] for i in range(N)]
for i in range(N):
    a = int(input())
    for j in range(a):
        x, y = [int(_) for _ in input().split()]
        A[i].append([x-1, y])

ans = 0
for i in range(2**N):
    ss = str(format(i, 'b')).zfill(N)
    h = [int(s) for s in ss]
    t = True
    for j, a in enumerate(A):
        for x in a:
            if h[j] and h[x[0]] != x[1]:
                t = False
    if t:
        ans = max(ans, h.count(1))
print(ans)

Submission status: Accepted

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

    
kouho=[]
for i in range(0,2**n):
  liis=[]
  for j in range(0,n):
    j=n-j-1
    onezero=i//(2**j)
    liis.append(onezero)
    i-=onezero*(2**j)
  kouho.append(liis)

maxx=0
for i in range(0,2**n):
  keep=0
  for j in range(0,n):
    usohonto=kouho[i][j]
    for k in range(0,len(lis[j])):
      shoge_hito=lis[j][k][0]
      shoge_data=lis[j][k][1]
      if usohonto==1:
        if not kouho[i][shoge_hito-1]==shoge_data:
          keep=1
          break
    if keep==1:
      break
  if keep==0:
    temp=kouho[i].count(1)
    if temp>maxx:
      maxx=temp
print(maxx)