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())
testimony = [[None for _ in range(N)] for _ in range(N)]
person = [None] * N

for i in range(N):
    person[i] = int(input()) #i番目のpersonの証言の数
    for _ in range(person[i]):
        j, good_or_bad = map(int, input().split())
        j -= 1
        testimony[i][j] = good_or_bad
        #i番目の人がj番目の人のことをgood_or_badって思ってるよーってこと。

ans = 0
for i in range(1, 1<<N):
    which_person = [None] * N
    for j in range(N): #j番目の人を見てる。
        which_person[j] = i>>j & 1
    ok = True
    for j in range(N):
        if(which_person[j]): #j番目の人が正直者である時のみ、可否を見れば良い。
            for k in range(N):
                #これ以降でj番目の人が正しいこと言ってるのか否かを調べてる。
                if testimony[j][k] == None: 
                    continue
                if testimony[j][k] != which_person[k]: #which_personってのは、全探索で仮定しているパターンに過ぎない
                    ok = False
    if ok:
        ans = max(ans, which_person.count(1))
print(ans)

Submission status: Accepted

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

ans = 0
for bit in range(1 << N):
    flag = True
    for i in range(N):
        if bit & (1 << i):
            for x, y in es[i]:
                if y == 1 and not bit & (1 << x) or y == 0 and bit & (1 << x):
                    flag = False
    
    if flag:

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = [[]for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        s[i].append(list(map(int, input().split())))
ans = 0
def bfs(honest):
    if len(honest) == n:
        global ans
        for i in range(n):
            if honest[i]==1:  
                for j in s[i]:
                    target, istrue = j
                    if (honest[target-1] != istrue):
                        return
        ans = max(ans, honest.count(1))
    else:
        bfs(honest + [0])
        bfs(honest + [1])
bfs([])
print(ans)

Submission status: Accepted

Solution code:
#python3

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


    ans = -1
    for i in range(1<<n):
        h = [0 for _ in range(n)]
        for k in range(n):
            if (i>>k) & 1: 
                h[k] = 1

        flag = True
        for j in range(n):
            if h[j] == 1:
                for k in range(n):
                    if g[j][k] == -1:
                        continue
                    if g[j][k] != h[k]:
                        flag = False
        if flag:
            ans = max(sum(h), ans)
    print(ans)
main()

Submission status: Accepted

Solution code:
N = int(input())
statement = {}
ans = 0
for i in range(N):
  l = []
  n = int(input())
  for j in range(n):
    l.append(list(map(int, input().split())))
  statement[i+1] = l
#print(statement)
def det(stat, hypo):
  D = True
  for i in range(1, N+1):
    if hypo[i] == "1":
#      print("{} is Honest".format(i))
      for j in range(len(stat[i])):
        if int(hypo[stat[i][j][0]]) != stat[i][j][1]:
#          print("{} says {} is not {}".format(i, stat[i][j][0], hypo[stat[i][j][0]]))
          D = False
#          print("The hypothesis {} is False".format(hypo))
          break
    if D == False:
      break
  return D
for i in range(2**N):
  Hypo = format(2**N - i - 1, "017b")[-(N+1):]
#  print(Hypo)
  if Hypo.count("1") > ans:
    if det(statement, Hypo):
      ans = Hypo.count("1")
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
al=[]
l=[]
for i in range(n):
  a=int(input())
  al.append(a)
  templ=[list(map(int,input().split())) for i in range(a)]
  l.append(templ)
ans=0
for i in range(2**n):
  b=bin(i)
  chkdic={}
  n_honest=0#正直者の人数をカウント
  flag=False#矛盾が生じるかどうか
  for j in range(n):
    if ((i >> j) & 1):#もし正直者なら
      n_honest+=1
      #saying_l=l[j]
      #a=al[j]
      chkdic[j+1]=1
    else:
      chkdic[j+1]=0
  #chkdicをもとに判定
  for j in range(n):
    if ((i >> j) & 1):
      saying_l=l[j]
      a=al[j]
      for k in range(a):
        saying=saying_l[k]
        if chkdic[saying[0]]!=saying[1]:
          flag=True
          break
    if flag:
      break  
  if not flag:
    ans=max(ans,n_honest)
print(ans)

Submission status: Accepted

Solution code:
def solve(inp):
    N = int(inp.readline().strip())
    XY = [[] for i in range(N)]
    for i in range(N):
        a = int(inp.readline().strip())
        XY[i] = [list(map(int, inp.readline().strip().split(' '))) for j in range(a)]

    r = 0
    for b in range(1, pow(2, N)):
        f = True
        for i in range(N):
            if b & (1 << i) != 0:
                for (x, y) in XY[i]:
                    if y == 1 and b & (1 << (x - 1)) == 0:
                        f = False
                        break
                    if y == 0 and b & (1 << (x - 1)) != 0:
                        f = False
                        break
                if not f:
                    break
        if f:
            rr = 0
            for i in range(N):
                if b & (1 << i) != 0:
                    rr += 1
            r = max([r, rr])

    return str(r)


def main():
    import sys
    result = solve(sys.stdin)
    if result:
        print(result)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = []
x = []
ans = 0
for i in range(n):
    a.append(int(input()))
    x.append([[0, 0] for _ in range(a[i])])
    for j in range(a[i]):
        e1, e2 = map(int,input().split())
        x[i][j][0] = e1
        x[i][j][1] = e2
for i in range(2**n):
    h = [0]*n
    for j in range(n):
        if (i >> j) & 1:
            h[j] = 1
    if ans >= sum(h): 
        continue
    flag = 1
    for j in range(n):
        if h[j] == 1:
            for k in x[j]:
                if h[k[0]-1] != k[1]:
                    flag = 0
                    break
    if flag == 1:
        ans = max(ans, sum(h))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = []
x = []
ans = 0
for i in range(n):
    a.append(int(input()))
    x.append([[0, 0] for _ in range(a[i])])
    for j in range(a[i]):
        e1, e2 = map(int,input().split())
        x[i][j][0] = e1
        x[i][j][1] = e2
for i in range(2**n):
    h = [0]*n
    for j in range(n):
        if (i >> j) & 1:
            h[j] = 1
    flag = 1
    for j in range(n):
        if h[j] == 1:
            for k in x[j]:
                if h[k[0]-1] != k[1]:
                    flag = 0
                    break
    if flag == 1:
        ans = max(ans, sum(h))
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations as comb
import sys
n = int(input())
li = [[] for i in range(n)]
for i in range(n):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        li[i].append((x-1, y))

for i in range(n, 0, -1):
    honests_list = comb(range(n), i)
    for honests in honests_list:
        for j in honests:
            for k, l in li[j]:
                if ((k in honests) and l==0) or ((k not in honests) and l==1):
                    break
            else:
                continue
            break
        else:
            print(i)
            sys.exit()
print(0)

Submission status: Accepted

Solution code:
import collections as c
ip = lambda : map(int, input().split())
mod = 10**9+7
# ##############
N = int(input())
l = []
for i in range(N):
    a = int(input())
    l1 = []
    for j in range(a):
        l1.append(list(ip()))
    l.append(l1)
ans=0
for i in range(2**N):
    tmp = [0]*N
    t = 0
    for j in range(N):
        if i>>j & 1:
            tmp[j]=1
            t+=1
    # print(tmp)
    for j in range(N):
        if tmp[j] ==0:
            continue
        for k in l[j]:
            x,y = k
            if tmp[x-1]!=y:
                break
        else:
            continue
        break
    else:
        if t > ans:
            ans = t
    continue
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
evi_list = [[] for _ in range(N)]
for n in range(N):
    A = int(input())
    for _ in range(A):
        evi_list[n].append([int(xy) for xy in input().split()])

max_honest = 0
for c in range(1, 2**N):
    index = 0
    honest_count = 0
    for bit in reversed(list(bin(c))[2:]):
        if bit == "1":
            is_honest = True
            for evi in evi_list[index]:
                judge = c & (1 << (evi[0]-1))
                if (judge == 0 and evi[1] == 1) or (judge >= 1 and evi[1] == 0):
                    is_honest = False
                    break
            if is_honest:
                honest_count += 1
            else:
                honest_count = 0
                break
        index += 1
    max_honest = max(max_honest, honest_count)

print(max_honest)

Submission status: Accepted

Solution code:
N = int(input())

p = []
t = []

for n in range(N):
  a = int(input())
  p.append(a)

  t.append([list(map(int, input().split())) for k in range(a)])

ans = 0

for bit in range(1 << N):
  flag = True

  for i in range(N):
    if not (bit & (1 << i)):
      continue
    
    for x in t[i]:
      if x[1] == 1 and not (bit & (1 << (x[0] - 1))):
        flag = False
      if x[1] == 0 and (bit & (1 << (x[0] - 1))):
        flag = False

  if flag:
    count = 0
    for s in range(N):
      if bit & (1 << s):
        count += 1

    if count > ans:
      ans = count

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a =[]
#標準入力
for _ in range(n):
    m = int(input())
    a.append([list(map(int, input().split())) for _ in range(m)])

    
c = 0#答え
for i in range(1 << n):#bit全探索
    Flag = True
    for j in range(n):
      if ((i>>j) & 1) == 1:
        for k in a[j]:
          if i >> (k[0]-1) & 1 != k[1]:#証言が正しくないときFalseを付け、breakする。
            Flag = False
      
      if Flag == False:
        break
      if (j == n - 1) & (Flag == True):
        honest = sum([i>>j & 1 for j in range(n)])
        #print(honest)
        c = max(c,honest)
print(c)

Submission status: Accepted

Solution code:
from itertools import product 
N = int(input())
A = [[[int(x) for x in input().split()] for _ in range(int(input()))] for i in range(N)]

def judge1(joukens, case):
    i = 1
    for jouken in joukens:
        if case[jouken[0]-1] != jouken[1]:
            i = 0
    return bool(i)

def judge(case):
    for i in range(N):
        if case[i] == 0:
            continue
        else:
            joukens = A[i]
            if judge1(joukens,case):
                continue
            else:
                return False
    return True

for case in list(product([1,0],repeat=N)):
    if judge(case):
        print(sum(case))
        break

Submission status: Accepted

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

def main():
    N = int(input())
    test = [[] for _ in range(N)]
    for i in range(N):
        num = int(input())
        for j in range(num):
            p,h = map(int,input().split())
            test[i].append((p-1,h))
    hon = 0
    for i in range(2**N):
        tf = [None for _ in range(N)]
        count = 0
        ans = True
        for j in range(N):
            if (i>>j)&1:
                tf[j] = True
                count += 1
            else:
                tf[j] = False
        for k in range(N):
            if tf[k]:
                for p,h in test[k]:
                    if (tf[p] == True and h == 1) or (tf[p] == False and h == 0):
                        continue
                    else:
                        ans = False
                        break
            else:
                continue
        if ans:
            hon = max(hon,count)
            
    print(hon)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())

p = []

for i in range(n):
    a = int(input())
    b = [input().split() for j in range(a)]
    p.append(b)

ans = 0
bit = 2**n

for i in range(bit):
    # 正直状態
    a = format(i,'0{}b'.format(n))

    flag = 1
    for j in range(len(p)):
        if a[j]=='1':
            for k in range(len(p[j])):
                if a[int(p[j][k][0])-1]!=p[j][k][1]:
                    flag = 0
                    break

    if flag:
        ans = max(ans,a.count('1'))
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l=[]
  for i in range(1<<n):
    _l=[]
    for j in range(n):
      _l.append(1 if i&(1<<j) else 0)
    l.append(_l)

  l2=[]
  for _ in range(n):
    a=I()
    _l2=[]
    for __ in range(a):
      _l2.append(LI())
    l2.append(_l2)

  ans=0
  for x in l:
    f=True
    for i,y in enumerate(x):
      if y==1:
        for z1,z2 in l2[i]:
          if x[z1-1]!=z2:
            f=False
            break
        if not f:
          break
    if f:
      ans=max(ans,x.count(1))

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
n = int(input())

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

count = 0
for bit in range(2 ** n):
	honest_table = [(bit >> i) & 1 for i in range(n)]

	flag = True
	for person in range(n):
		if honest_table[person] == 1:
			for x, y in testimonies[person]:
				if honest_table[x] != y:
					flag = False

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

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n = int(input())

    testimony = {}
    for i in range(n):
        a = int(input()) # 証言数
        for j in range(a):
            who, ans = list(map(int, input().split(' ')))
            if j == 0:
                testimony[i + 1] = [{
                    'who': who,
                    'ans': ans
                }]
            else:
                testimony[i + 1].append({
                    'who': who,
                    'ans': ans
                })

    # print(testimony)
    # testimony = {1: [{'who': 2, 'ans': 1}], 2: [{'who': 1, 'ans': 1}], 3: [{'who': 2, 'ans': 0}]}

    max_honest = 0
    for i in reversed(range(2 ** n)):
        check_list = bin(i)[2:].zfill(n)
        # print(check_list) # 000 - 111
        ng_flag = 0
        for j in range(n):
            if check_list[j] == '1' and (j + 1) in testimony:
                for k in testimony[j + 1]: #正直者j +1さんの意見を順にチェック
                    if check_list[k['who'] - 1] != str(k['ans']):
                        ng_flag = 1
                        break
        if ng_flag == 0:
            if check_list.count('1') > max_honest:
                max_honest = check_list.count('1')

    print(max_honest)

Submission status: Accepted

Solution code:
import itertools
#人数
n = int(input())

#証言リスト
syougen = []
for i in range(n):
  #証言数[a番目の証言]
  a = int(input())
  detail =[]
  for s in range(a):
    t,h = map(int,input().split())
    detail.append([t,h])
  syougen.append(detail)

maxHonor = 0
#全探索
for i in itertools.product([0,1],repeat=n):
  honor = 0
  dare = 0
  for s in i:    
    isCorrect=True
    #正直物の場合
    if s == 1:
      honor+=1
      for d in syougen[dare]:
        # 証言と対象の属性があっているかチェック
        if d[1] == i[d[0]-1]:
          continue
        else:
          isCorrect=False
          break
      if isCorrect==False:
        break
      
    dare+=1
  #全員チェックOKの場合、最大値を保持      
  if isCorrect == True and honor > maxHonor:
    maxHonor = honor

print(maxHonor)

Submission status: Accepted

Solution code:
n = int(input())
List = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
  num_evidence = int(input())
  for j in range(num_evidence):
    darega, doushita = map(int,input().split())
    List[i][darega - 1] = doushita * 2 - 1

def is_inconsistent(all_evidence, honest_or_unkind):
  for i in range(n):
    if honest_or_unkind[i] == 1:
      for j in range(n):
        if honest_or_unkind[j] * all_evidence[i][j] == -1:
          return True
  return False

max_honest = 0
for i in range(2**n):
  temp = format(i, '0'+str(n)+'b')
  honest_or_unkind = [int(temp[i]) * 2 - 1 for i in range(n)]
  if not is_inconsistent(List, honest_or_unkind):
    max_honest = max(max_honest, honest_or_unkind.count(1))

print(max_honest)

Submission status: Accepted

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

def main():
    # Failed to predict input format
    N = int(input())
    x = [ [] for i in range(N+1)]
    for i in range(N):
        a = int(input())
        for j in range(a):
            x[i].append(list(map(int, input().split())))

    ans = 0
    for i in range(1<<N):
        y = [[] for k in range(N+1)]
        for j in range(N):
            if (i>>j) &1:
                for k in range(len(x[j])):
                    a, b = x[j][k]
                    # print(a-1, b)
                    y[a].append(b)

        if all([j == [] or j.count(1) == len(j) or j.count(0) == len(j) for j in y[1:]]):
            f = True
            for idx, k in enumerate(y[1:], 1):
                if k == []:
                    continue

                elif k[0] == 0 and not i>>(idx-1)&1:
                    continue

                elif k[0] == 1 and i>>(idx-1)&1:
                    continue

                else:
                    f = False
            if f:
                ans = max(ans, '{:05b}'.format(i).count('1'))
                
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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




def main():
    # Failed to predict input format
    N = int(input())
    x = [ [] for i in range(N+1)]
    for i in range(N):
        a = int(input())
        for j in range(a):
            x[i].append(list(map(int, input().split())))

    # print(x)
    ans = 0
    for i in range(1<<N):
        y = [[] for k in range(N+1)]
        for j in range(N):
            if (i>>j) &1:
                for k in range(len(x[j])):
                    a, b = x[j][k]
                    # print(a-1, b)
                    y[a].append(b)

        if all([j == [] or j.count(1) == len(j) or j.count(0) == len(j) for j in y[1:]]):
            # print('{:05b}'.format(i), y)
            # if all([(i>>idx)&1 for idx, k in enumerate(y[1:], 1) if k.count(1) == len(k)]):
            #     ans = max(ans, bin(i).count('1'))
            #     print(bin(i), y, 'ok')
            # f = True
            # for idx, k in enumerate(y[1:], 1):
            #     if k.count(0) == len(k):
            #         if not (i>>(idx-1))&0:
            #             f = False
                        

            #     elif k.count(1) == len(k):
            #         if not (i>>(idx-1))&1:
            #             f = False
            #         else:
            #             print('t')
            # if f:
            #     ans = max(ans, '{:05b}'.format(i).count('1'))
            f = True
            for idx, k in enumerate(y[1:], 1):
                if k == []:
                    continue

                elif k != [] and k[0] == 0 and not i>>(idx-1)&1:
                    continue

                elif k != [] and k[0] == 1 and i>>(idx-1)&1:
                    continue

                else:
                    f = False
            if f:
                # print('{:05b}'.format(i), y, 'ok')
                ans = max(ans, '{:05b}'.format(i).count('1'))
                





    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class Solve:
    def __init__(self, n, data):
        # write variables you use here
        self.n = n
        self.data = data
        self.honest = 0
        self.flag = 0

    
    def main(self):
        for i in range(2 ** n):
            for j in range(n):
                if i & (1 << j):
                    for k in self.data[j]:
                        if (i & (1 << (k[0] - 1))) != 0 and k[1] == 0:
                            break
                        if (i & (1 << (k[0] - 1))) == 0 and k[1] != 0:
                            break

                    else:
                        continue  # 矛盾なく回ったとき
                    break
                else:
                    continue
            else:
                self.honest = max(self.honest, bin(i).count('1'))
        
        print(self.honest)
                     

if __name__ == "__main__":
    # write standard input here
    n = int(input())
    data = []
    for i in range(n):
        tmp = int(input())
        data.append([list(map(int, input().split())) for j in range(tmp)])
    s = Solve(n, data)
    s.main()

Submission status: Accepted

Solution code:
n = int(input())
from itertools import product as pd
from collections import defaultdict as dd
dic = dd(lambda: [])
for i in range(n):
  a = int(input())
  for j in range(a):
    x, y = map(int, input().split())
    dic[i] += [[x-1, y]]

def not_contradict(cand, lis, dic):
  for pair in lis:
    id, tf_c = pair
    if cand[id] != tf_c:
      return False
  else:
    return True

max_num = 0
for cand in pd([0, 1], repeat=n):
#  print(list(cand))
  for i, tf in enumerate(cand):
    if tf == 1:
      lis = dic[i]
      if not_contradict(cand, lis, dic) == False:
        break
  else:
    max_num = max(sum(cand), max_num)
print(max_num)

Submission status: Accepted

Solution code:
N = int(input())
prefix = '0{}b'.format(N)
li = [[-1]*N for _ in range(N)]

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

ans = 0
for i in range(2**N):
    bin = format(i,prefix)
    flag = 1
    for j in range(N):
        if (i>>j)&1:
            for k in range(N):
                if li[j][k] == 1:
                    if bin[-k-1] != '1':
                        flag = 0
                elif li[j][k] == 0:
                    if bin[-k-1] != '0':
                        flag = 0
    if flag:
        ans = max(ans,list(bin).count('1'))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
B = [[-1]*N for i in range(N)]

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

ans = 0

for i in range(1<<N):
    tmp = i
    tmpans = 0
    while tmp!=0:
        tmpans += tmp%2
        tmp //= 2
    tmpshi = [-1]*N
    flag = 0
    for j in range(N):
        if flag == 1:
            break
        if ((i>>j)&1)==1:
            for k in range(N):
                if B[j][k] != -1:
                    if B[j][k] == tmpshi[k] or tmpshi[k]==-1:
                        tmpshi[k]=B[j][k]
                    else:
                        flag = 1
                        break
    flag1 = 0
    if flag == 0:
        for j in range(N):
            if ((i>>j)&1)!=tmpshi[j] and tmpshi[j]!=-1:
                flag1 = 1
                break
        if flag1 == 0:
            ans = max(ans,tmpans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
B = [[-1]*N for i in range(N)]

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

zero1 = [0,1]
import itertools

ans = 0
for i in itertools.product(zero1,repeat=N):
    tmpans = sum(i)
    tmpshi = [-1]*N
    flag = 0
    for j in range(len(i)):
        if flag == 1:
            break
        if i[j]==1:
            for k in range(len(B[j])):
                if B[j][k] in [0,1]:
                    if B[j][k] == tmpshi[k] or tmpshi[k]==-1:
                        tmpshi[k]=B[j][k]
                    else:
                        flag = 1
                        break
    flag1 = 0
    if flag == 0:
        for j in range(N):
            if i[j]!=tmpshi[j] and tmpshi[j]!=-1:
                flag1 = 1
                break
        if flag1 == 0:
            ans = max(ans,tmpans)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N = int(input())

A = {
  i+1 : [
    tuple(map(int, input().split())) for _  in range(int(input()))
  ] for i in range(N)
}


def judge_(joukens, case):
  ans = 1
  for jouken in joukens:
    if case[jouken[0]-1] != jouken[1]:
      ans = 0
    
  return bool(ans)

def judge(case):
  for i in range(N):
    if case[i] == 0:
      continue
    else:
      joukens = A[i+1]
      if judge_(joukens, case):
        continue
      else:
        return False
  
  return True

ans = 0
# 正直者を1、嘘つきを０とする
for case in list(product([1, 0], repeat = N)):
  if judge(case):
    ans = sum(case)
    break
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import itertools


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

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

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

seq = (0, 1)

# print(A)

ans = 0
for pos in itertools.product(seq, repeat=N):
    # print(pos)
    isValid = True
    for i in range(N):
        if pos[i] == 0:
            continue

        for prop in A[i]:
            #print("i", i, prop)
            x, y = prop
            if pos[x] == y:
                continue
            else:
                isValid = False
                break

        if not isValid:
            break

    if isValid:
        a = sum(pos)
        if a > ans:
            ans = a


print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())

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

def is_ok(state):
    true_numbers = [i for i in range(n) if state & (1 << i)]

    visited = [False] * n
    que = deque(true_numbers)
    while que:
        target = que.popleft()
        if not visited[target]:
            visited[target] = True

            for av in al[target]:
                tf = bool(state & (1 << (av[0] - 1)))
                if tf != av[1]:
                    return False
                if tf:
                    que.append(av[0] - 1)

    # for number in true_numbers:
    #     for av in al[number]:
    #         if state & (1 << (av[0] - 1)) != av[1]:
    #             return 0
    return len(true_numbers)

print(max(is_ok(state) for state in range(2**n)))

# for state in range(2**n):
#     # print(f"%0{n}d" % int(bin(state)[2:]))
#     print(is_ok(state))
#
# # pass
# # state = int('010', 2)
# # print(is_ok(state))

Submission status: Accepted

Solution code:
N = int(input())

L = [0] * N

for i in range(N):
  A = int(input())
  if A == 0:
    L[i] = []
  else:
    L[i] = [list(map(int, input().split()))]
  for j in range(1,A):
    L[i].append(list(map(int, input().split())))
    
#print(L)

ans = 0
for i in range(2**N):
  pat = str(format(i, '0' + str(N) + 'b'))
  flg = True
  #S = [-1] * (N)
  for j in range(N):
    if pat[j] == "1": # trueman
      for rule in L[j]:
        if pat[rule[0]-1] == "0" and rule[1] == 1:
          flg = False
          break
        if pat[rule[0]-1] == "1" and rule[1] == 0:
          flg = False
          break
  #print("XXX", flg, pat, j)
  if flg:
    work = 0
    for ch in pat:
      if ch == "1":
        work += 1
    #print("XXX", flg, pat, j, work)
    ans = max(ans, work)
    
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a =[]
for _ in range(n):
    m = int(input())
    a.append([list(map(int, input().split())) for _ in range(m)])
c = 0
for i in range(1 << n):
    Flag = True
    for j in range(n):
        if ((i>>j)&1) == 1:
            for k in a[j]:
                if i>>(k[0]-1)&1 != k[1]:
                    Flag = False
        if Flag == False:break
    else:
        honest = sum([i>>j&1 for j in range(n)])
        c = max(c,honest)
print(c)

Submission status: Accepted

Solution code:
#python3

graph = [[-1 for _ in range(15)] for _ in range(15)]

def main():
    n = int(input())
    for i in range(n):
        a = int(input())
        for j in range(a):
            x, y = map(int, input().split())
            graph[i][x-1] = y
            
    ans = 0
    for i in range(1<<15):
        h = [0]*15
        for k in range(n):
            if (i >> k) & 1:
                h[k] = 1

        f = True
        for i in range(15):
            if h[i] == 1:
                for j in range(n):
                    if graph[i][j] == -1:
                        continue
                    if graph[i][j] != h[j]:
                        f = False

        if f:
            ans = max(ans, sum(h))

    print(ans)
main()

Submission status: Accepted

Solution code:
from collections import*
n=int(input())

d=defaultdict(list)
for i in range(n):
    a=int(input())
    for j in range(a):
        d[i+1].append(list(map(int,input().split())))
        
#print(d)

ans=[]
for i in range(2**n):
    bol=[i>>j&1for j in range(n)]
#    print(bol)
    f=0
    for p,b in enumerate([i>>j&1for j in range(n)]):
        if b:
            for s,t in d[p+1]:
                if bol[s-1]!=t:
                    f=1
    if f==0:
#        print(bol)
        ans.append(sum(bol))
print(max(ans))