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:
N = int(input())
A = [[-1 for _ in range(N)] for _ in range(N)]
for i in range(N):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        x -= 1
        A[i][x] = y 

ans = 0
for b in range(2**N):
    bit = bin(b)[2:].zfill(N)
    flg = True
    for i in range(N):
        if bit[i] == '0': continue
        for j in range(N):
            if A[i][j] == -1: continue
            if A[i][j] != int(bit[j]):
                flg = False
                break
        
        if not flg: break

    ans = max(bit.count('1'), ans) if flg else ans

print(ans)

Submission status: Accepted

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

ans = 0
for p in range(2**n):
    q = p
    c = 0
    t = []
    l = 0
    while q:
        if q&1:
            t.append(graph[c])
            l += 1
        q >>= 1
        c += 1
    flag = True
    for c in range(n):
        if p&1:
            for s in t:
                if s[c] == 0:
                    flag = False
        else:
            for s in t:
                if s[c] == 1:
                    flag = False
        p >>= 1
    if flag:
        ans = max(ans, l)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = []
x = []
y = []
for i in range(n):
    ai = int(input())
    a.append(ai)
    xi = []
    yi = []
    for j in range(ai):
        xij, yij = map(int, input().split(' '))
        xi.append(xij)
        yi.append(yij)
    x.append(xi)
    y.append(yi)
ans = 0
for case in range(2**n):
    truth_t = 0  #正直者の真の数
    truth = 0    #正直者の確認した数
    for i in range(n):  #人ごとに矛盾が生じないか確認
        if (case>>i)&1:  #正直者であれば証言に矛盾がないか確認
            truth_t+=1
            proof=0
            for j in range(a[i]):
                if ((case>>(x[i][j]-1))&1)==y[i][j]:
                    proof+=1
            if proof==a[i]:
                truth += 1
    if truth==truth_t:
        if ans<truth:
            ans = truth
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
ls1 = []
for i in range(N):
    A = int(input())
    ls2 = []
    for i in range(A):
        x, y = map(int,input().split())
        ls2.append([x,y])
    ls1.append(ls2)
ans = 0
f = True
for i in range(2**N):
    for j in range(N):
        if (i>>j&1):
            f = True
            for k in ls1[j]:
                if (i >>(k[0] - 1) &1) == (k[1]&1):
                    continue
                else:
                    f = False
                    break
            if f == False:
                break
    if f:
        ans = max(ans,bin(i).count('1'))    
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
ll = [] #リストのリスト
for i in range(N):
    l = [None]*N
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        l[x-1] = y
    ll.append(l)

ans = 0
for i in range(1, 2**N): #bit全探索
    b = 1
    hon = [0]*N #正直者なら1, 
    for j in range(N):
        if i>>j&1:
            hon[j] = 1
    
    for k in range(N): # llとhonの比較 # 全正直者について
        if hon[k]==1: #正直者のつじつまを合わせる
            for h in range(len(ll[k])): #正直者の全ての証言について	
                if ll[k][h]==None:
                    continue
                if hon[h]!=ll[k][h]:
                    b = 0
                
   
    if b:
        p = hon.count(1)
        ans = max(p, ans)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

ans = 0
for state in range(1<<n):
    tmp = 0
    hh = []
    for mask in range(n):
        if (1<<mask)&state:
            hh.append(mask)
    flag = True
    for h in hh:
        for x,y in s[h]:
            if y == 1:
                if x not in hh:
                    flag = False
                    break
            else:
                if x in hh:
                    flag = False
                    break
        tmp += 1
    if flag:        
        ans = max(tmp, ans)
    
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = []
XY = []
for i in range(N):
    a = int(input())
    A.append(a)
    xy = [list(map(int,input().split())) for j in range(a)]
    XY.append(xy)
ans = 0
for i in range(2**N):
    b = [i>>j&1 for j in range(N)]
    f = 0
    for j in range(N):
        if b[j] == 1:
            for k in range(A[j]):
                x = XY[j][k][0] -1
                y = XY[j][k][1]
                if b[x] != y:
                    f = 1
                    break
        if f:
            break
    else:
        ans = max(ans,b.count(1))
print(ans)

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    testimonies = []
    for _ in range(n):
        a = input_int()
        testimony = []
        for _ in range(a):
            x, y = input_int_list()
            testimony.append([x, y])
        testimonies.append(testimony)
    # すべてのパターンを試すO(2**n)
    ans = 0
    for i in range(2**n):
        sample = [None] * n
        for j in range(n):
            if i >> j & 1:
                sample[j] = 1
            else:
                sample[j] = 0
        sample = [None] + sample  # 1-indexed
        # sampleが成立するか確認する
        is_possible = True
        for idx, testimony in enumerate(testimonies):
            if sample[idx + 1] == 1:
                for x, y in testimony:
                    if sample[x] == y:
                        continue
                    else:
                        is_possible = False
        # すべての証言が正しければ、正直者の数を答えにする
        if is_possible:
            ans = max(ans, sum(sample[1:]))
    print(ans)

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())

statements = []

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

    statements.append(astates)

cnt = 0
for i in range(2**n):
    state = format(i, "0"+str(n)+"b")

    pos = True
    for j in range(n):
        if state[j] == "1":
            for x, y in statements[j]:
                if not (state[x-1] == str(y)):
                    pos = False
                    break

        if not pos:
            break

    if pos:
        cnt = max(cnt, state.count("1"))

print(cnt)

Submission status: Accepted

Solution code:
n=int(input())

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

ans = 0

for bit in range(2**n):
    
    for s in comment:
        if (bit>>s[0])&1 == 1:
            if (bit>>s[1])&1 != s[2]:
                break
    else:
        tmp = str(bin(bit)).count("1")
        ans=max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import chain
from itertools import product


def check(N, ptn, m_assert):
    for i in range(N):
        if ptn[i] == 1:
            for j in range(i + 1, N):
                if ptn[j] == 1:
                    if m_assert[i][j] == 0:
                        return False
                    if m_assert[j][i] == 0:
                        return False
                else:
                    if m_assert[i][j] == 1:
                        return False
        else:
            for j in range(i + 1, N):
                if ptn[j] == 1:
                    if m_assert[j][i] == 1:
                        return False
    return True


def solve(N, m_assert):
    ans = 0
    for ptn in product([1, 0], repeat=N):
        if check(N, ptn, m_assert):
            ans = max(sum(ptn), ans)
    return ans


def main():
    N = int(input())
    m_assert = [[-1] * N for _ in range(N)]
    for n in range(N):
        A = int(input())
        for a in range(A):
            x, y = map(int, input().split())
            m_assert[n][x - 1] = y
    answer = solve(N, m_assert)
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())

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

ans = 0

for bit in range(2**n):
    
    for s in syougen:
        if (bit>>s[0])&1 == 1:
            if (bit>>s[1])&1 != s[2]:
                break
    else:
        thisans = str(bin(bit)).count("1")
        ans=max(ans,thisans)
        # print(bin(bit))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
L = []
ans = 0

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

for i in range(1<<n):
    flg = True
    for j, x, y in L:
        if i>>j & 1 and i>>x & 1 != y:
            flg = False
            break
    if flg:
        ans = max(ans, sum(i>>j & 1 for j in range(n)))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
testimo_ls = [ [] for i in range(N) ]
rst = 0
for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split(' '))
        testimo_ls[i].append([x - 1, y])
for i in range(1 << N):
    honest_ls = []
    for j in range(N):
        if i >> j & 1:
            honest_ls.append(j)
    is_ok_cnt = 0
    is_ok = True
    for s in honest_ls:
        for t in testimo_ls[s]:
            if t[1] == 0 and t[0] in honest_ls:
                is_ok = False
                break
            if t[1] == 1 and t[0] not in honest_ls:
                is_ok = False
                break
    if is_ok:
        rst = max(rst, len(honest_ls))
print(rst)

Submission status: Accepted

Solution code:
N = int(input())

hatsugen = [[] for _ in range(N)]
#print(hatsugen)
A = -1
while True:
  try:
  	s = input()
  except EOFError:
    break  
  a = tuple(map(int,s.rstrip().split()))
  #print(a)
  if len(a) == 1:
    A += 1
  else:
    hatsugen[A].append(a)
#print(hatsugen)

ans = 0
for i in range(2**N):
  
  bit = i
  flag = [0]*N
  idx = 0
  while bit:
    if (bit&1):
      flag[idx] = 1
    bit >>= 1
    idx+=1
  
  flag2=0
  #print(flag)
  for i in range(N):
    if flag[i]:
      hatsu = hatsugen[i]
    else:
      continue
    for word in hatsu:
      #print(*word)
      if flag[word[0]-1] != word[1]:
        flag2 = 1
        #print("false")
        break
    if flag2:
      break
  if flag2==0:
    ans = max(ans, sum(flag))

print(ans)

Submission status: Accepted

Solution code:
import itertools

n=int(input())

lst=[[] for i in range(n)] 

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

ans=0


for xxx in itertools.product(range(2),repeat=n):
    table=[[] for i in range(n)]
    for j in range(n):
        if xxx[j]==1:
            for k in lst[j]:
                table[k[0]].append(k[1])
    
    flag=True

    for j in range(n):
        if xxx[j]==1:
            if table[j].count(0)!=0:
                flag=False
        
        else:
            if table[j].count(1)!=0:
                flag=False
    

    if not flag:
        continue
    

    ans=max(ans,xxx.count(1))



print(ans)

Submission status: Accepted

Solution code:
#
# abc147 c
#
import sys
from io import StringIO
import unittest
from collections import deque


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
1
2 1
1
1 1
1
2 0"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """2
1
2 0
1
1 0"""
        output = """1"""
        self.assertIO(input, output)


def resolve_bit():
    N = int(input())
    C = []
    for i in range(N):
        a = int(input())
        C.append([list(map(int, input().split())) for j in range(a)])

    ans = 0
    for bit in range(1 << N):
        f = True
        for i in range(N):
            if bit & (1 << i):
                for c in C[i]:
                    if bit & (1 << c[0]-1) != (1 << c[0]-1)*c[1]:
                        f = False
                        break
        if f == True:
            ans = max(ans, bin(bit).count("1"))
    print(ans)


def resolve():
    global N, C
    N = int(input())
    C = []
    for i in range(N):
        a = int(input())
        C.append([list(map(int, input().split())) for j in range(a)])

    V = deque()
    print(dfs(0, V))


def dfs(n, V):
    if n == N:
        count = 0
        for v in V:
            if count == -1:
                break
            for c in C[v-1]:
                if (c[0] in V and c[1] == 0) or (c[0] not in V and c[1] == 1):
                    count = -1
                    break
            else:
                count += 1
        if count == -1:
            return 0
        else:
            return count

    ans = 0
    V.append(n+1)
    ans = max(ans, dfs(n+1, V))
    V.pop()
    ans = max(ans, dfs(n+1, V))

    return ans


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
N=int(input())

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

ans=0

for h in range(2**N):
	flag=0
	cnt=0
	l=[0]*N
	for g in range(N):
		if h>>g &1:
			l[g]=1
	#print(l)
	for gg in range(N):
		if l[gg]==1:
			temp_=syogen[gg]
			#print(temp_)
			for n in range(temp_[0]):
				if l[temp_[1][n][0]-1]==temp_[1][n][1]:
					continue
				else:
					flag=1
					break
		if flag==1:
			break
		elif flag==0 and gg==N-1:
			#print(bin(h))
			ans=max(ans,sum(l))

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
l=[]
for i in range(n):     
      A=int(input())
      L=[list(map(int,input().split())) for _ in range(A)]
      a.append(A)
      l.append(L)
ans=0
for i in range(2**n):
      b=[0]*n
      for j in range(n):
            if (i>>j)&1:
                  b[j]=1
      for k in range(n):
            for h in range(a[k]):
                  hito=l[k][h][0]-1
                  singi=l[k][h][1]
                  if b[k]==1 and b[hito]!=singi:
                        break      
            else:
                  continue
            break
      else:
            ans=max(ans,sum(b))

print(ans)

Submission status: Accepted

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')

from collections import defaultdict
test = defaultdict(list)
test_per = defaultdict(dict)
n = int(input())
for i in xrange(n):
    nn = int(input())
    for j in xrange(nn):
        x,y = (int(x) for x in input().split())
        test[x-1].append(y)
        test_per[i][x-1] = y
ans = 0
for i in xrange(2**n):
    bini= bin(i)[2:]
    bini = '0'*(n-len(bini)) + bini
    valid = True
    for j,c in enumerate(bini):
        if c == '1':  # honnest
            for other_person in test_per[j]:
                if test_per[j][other_person] != int(bini[other_person]):
                    valid = False
                    break
        if not valid:
            break
    if valid:
        ans = max(ans, bini.count('1'))
print(ans)

Submission status: Accepted

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

for i in range(2**n):
    tmp=[0]*n
    for j in range(n):
        if (i>>j)&1:
            tmp[j]=1
    for k in range(n):
        for h in range(a[k]):
            hito=x[k][h][0]-1
            singi=x[k][h][1]
            if tmp[k]==1:
                if tmp[hito]!=singi:
                    break
        else:
            continue
        break # https://note.nkmk.me/python-break-nested-loops/
    else:
        ans=max(ans,sum(tmp))

print(ans)

Submission status: Accepted

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

for i in range(2**n):
    tmp=[0]*n
    for j in range(n):
        if (i>>j)&1:
            tmp[j]=1
    for k in range(n):
        # if a[k]==0:
        #     continue
        for h in range(a[k]):
            hito=x[k][h][0]-1
            singi=x[k][h][1]
            if tmp[k]==1:
                if tmp[hito]!=singi:
                    break
        else:
            continue
        break
    else:
        ans=max(ans,sum(tmp))

print(ans)

Submission status: Accepted

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

for i in range(2**n):
    tmp=[0]*n
    for j in range(n):
        if (i>>j)&1:
            tmp[j]=1
    for k in range(n):
        if a[k]==0:
            continue
        for h in range(a[k]):
            hito=x[k][h][0]-1
            singi=x[k][h][1]
            if tmp[k]==1:
                if tmp[hito]!=singi:
                    break
        else:
            continue
        break
    else:
        ans=max(ans,sum(tmp))

print(ans)

Submission status: Accepted

Solution code:
# ABC 147 C

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

res=0
for n in range(1<<(N)):
    check=[-1]+[(n>>j)&1 for j in range(N)]
    cnt=0
    j=0
    for j in range(N):
        if check[j+1]==1:
            cnt+=1
            #syouziki
            for x,y in A[j]:
                if check[x] == 1-y:
                    check[0]=1
                if check[0]>0:
                    break
        if check[0]>0:
            break
    if check[0]>0:
        continue
    res=max(res,cnt)
print(res)

Submission status: Accepted

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

#l = list(map(int, input().split()))
#import numpy as np
#arr = np.array([int(i) for i in input().split()])
'''
a,b=[],[]
for i in range(n):
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''


n=int(input())

a,x=[],[]
for i in range(n):
    A = int(input())
    a.append(A)
    B=[]
    for j in range(A):
        B.append(list(map(int, input().split())))
    x.append(B)

ma=0
for i in range(2**n):
    now=0
    flg=True
    e=[0]*n
    for j in range(n):
        if (i>>j)&1:
            now+=1
            e[j]=1

    for j in range(n):
        #print(e)
        if (i>>j)&1:
            
            if e[j]==0:
                flg=False
                break
            elif not flg:
                break

            for k in range(a[j]):
                """if e[x[j][k][0]-1]==-1: 
                    if x[j][k][1] and
                    e[x[j][k][0]-1]=x[j][k][1]"""
                
                if (e[x[j][k][0]-1]==0 and x[j][k][1]==1) or (e[x[j][k][0]-1]==1 and x[j][k][1]==0):
                    flg=False
                    break

    if flg and ma<now:
        ma=now
        #print(ma)

print(ma)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Sep 13 02:01:40 2020

@author: liang
"""

N = int(input())
A = list()
T = [list() for i in range(N)]

#データ挿入
for i in range(N):
    a = int(input())
    A.append(a)
    for a in range(a):
        x, y = map(int,input().split())
        x -= 1 #配列のインデックスに対応
        T[i].append((x,y))
ans = 0
#bit全探索
for i in range(2**N):
    #正直者のインデックスを格納
    persons = list()
    for j in range(N):
        if i>>j&1 == 1:
            persons.append(j)
    #正直者　= True
    d = [False]*N
    for p in persons:
        d[p] = True 

    judged = [False]*N
    #全ての人に対してループ
    for num in range(N):
        #正直者のみ採用
        f = False
        if d[num]:
            for t in T[num]:
                x, y = t[0], t[1]
                #dのテーブルを更新
                if y == 1 and d[x] != True:
                    f = True
                    break
                if y == 0 and d[x] != False:
                    f = True
                    break
        if f:
            break
    else:
        #print(d)
        ans = max(ans, len(persons))
print(ans)

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    return C

N=intput()
A=[list() for _ in range(N)]
for i in range(N):
    a=intput()
    for _ in range(a):
        A[i].append(lint())
ans=0
for c in product('01',repeat=N):
    tmp=True
    for i in range(N):
        if c[i]=='1':
            for x,y in A[i]:
                if c[x-1]!=str(y):
                    tmp=False
                    break
        if not tmp:
            break
    if tmp:
        ans=max(ans,c.count('1'))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
confesses = [[-1 for _ in range(N)] for __ in range(N)]
for i in range(N):
  A = int(input())
  for __ in range(A):
    x, y = map(int, input().split())
    confesses[i][x-1] = y
answer = 0
for num in range(2**N):
  users = [0 for _ in range(N)]
  cnt = 0
  for i in range(N):
    if num>>i&1:
      users[i] = 1
      cnt += 1
  right = True
  for j, user in enumerate(users):
    if user == 1:
      for i, confess in enumerate(confesses[j]):
        if confess != -1 and users[i] != confess:
          right = False
          break
    if not right:
      break
  if right:
    answer = max(answer, cnt)
print(answer)

Submission status: Accepted

Solution code:
def judge(bit):
    global l
    for i in range(n):
        if (bit>>i)&1 == 0:
            continue
        for x,y in l[i]:
            if y==1 and (bit>>x)&1==0:
                return False
            if y==0 and (bit>>x)&1==1:
                return False
    return True

n = int(input())
l = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        l[i].append((x-1,y))
maxi = 0
for bit in range(2**n):
    if judge(bit):
        maxi = max(maxi,str(bin(bit)).count('1'))
print(maxi)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
n = int(input())
d = defaultdict(list)
for i in range(n):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        d[i].append((x-1,bool(y)))
        
maxi = 0
for i in range(2 ** n):
    honest = [-1]*n
    que = deque([])
    for j in range(n):
        if ((i >> j) & 1):
            que.append(n-1-j)
            honest[n-1-j] = True
    flag = True
    while que and flag:
        v = que.popleft()
        for x,y in d[v]:
            if honest[x] == -1:
                honest[x] = y
                if y:
                    que.append(x)
            elif honest[x] != y:
                flag = False
                break
    if flag:
        maxi = max(maxi,str(bin(i)).count('1'))
print(maxi)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def ok(t, s):
    N = len(t)
    for i in range(N):
        if t[i]:
            for x, y in s[i]:
                if y == 1:
                    if not t[x]:
                        return False
                elif y == 0:
                    if t[x]:
                        return False

    return True


def solve():
    N = int(input())

    s = defaultdict(list)
    for i in range(N):
        A = int(input())
        for _ in range(A):
            X, Y = map(int, input().split())
            X -= 1
            s[i].append((X, Y))

    ans = 0
    for b in range(2 ** N):
        t = [0] * N
        num = 0
        for i in range(N):
            if (b >> i) & 1:
                t[i] = 1
                num += 1
        if ok(t, s):
            ans = max(ans, num)

    print(ans)


def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product

n = int(input())

d = {}
for i in range(n):
  a = int(input())
  for _ in range(a):
    x, y = map(int, input().split())
    if i + 1 not in d:
      d[i + 1] = []
    d[i + 1].append((x, y))

ret = 0
for x in product((0, 1), repeat=n):
  ok = True
  for i in range(n):
    if x[i] == 0 or i + 1 not in d:
      continue
    for p, tf in d[i + 1]:
      if x[p - 1] != tf:
        ok = False
        break
    if not ok:
      break
  if ok:
    ret = max(ret, sum(x))

print(ret)

Submission status: Accepted

Solution code:
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())
        x -= 1
        xy[i].append((x,y))
ans = 0
s = set()
t = set()
def true(s,t,j):
    if j not in t:
        s.add(j)
        return False
    return True
def false(s,t,j):
    if j not in s:
        t.add(j)
        return False
    return True
def chk(i):
    s = set()
    t = set()
    fl = False
    for j in range(N):
        if (i>>j)&1:
            fl |= true(s,t,j)
            for x,y in xy[j]:
                fl |= true(s,t,x) if y == 1 else false(s,t,x)
        else:
            fl |= false(s,t,j)
    return fl
ans = 0
for i in range(2**N):
    if chk(i):
        continue
    cnt = 0
    for j in range(N):
        if (i>>j)&1:
            cnt += 1
    ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

n = int(input())

d = {}
for i in range(n):
  a = int(input())
  for _ in range(a):
    x, y = map(int, input().split())
    if i + 1 not in d:
      d[i + 1] = []
    d[i + 1].append((x, y))

ret = 0
for x in product((0, 1), repeat=n):
  tmp = [-1] * n
  ok = True
  for i in range(n):
    if x[i] == 1 and i + 1 in d:
      for y in d[i + 1]:
        if tmp[y[0] - 1] == -1:
          tmp[y[0] - 1] = y[1]
        elif tmp[y[0] - 1] != y[1]:
          ok = False
          break
    if not ok:
      break
  if ok and all(a == b or b == -1 for a, b in zip(x, tmp)):
    ret = max(ret, sum(x))

print(ret)