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())
link=[[] for _ in range(n)]
for i in range(n):
    for j in range(int(input())):
        a,b=map(int,input().split())
        link[i].append([a-1,b])
def bitj(bit):
    for i in range(n):
        if not (bit>>i)&1:
            continue
        for x,y in link[i]:
          if y==1 and not (bit>>x)&1:
            return False
          elif y==0 and (bit>>x)&1:
            return False
    return True
ans=0
for i in range(1<<n):
    if not bitj(i):
        continue
    res=0
    for j in range(n):
        if (i>>j)&1:
            res+=1
    ans=max(ans,res)
print(ans)

Submission status: Accepted

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

    ans = 0
    for i in range(1, 2**N):
        flag = True
        cnt = 0
        for j in range(N):
            if i>>j & 1: #iのj bit shift
                cnt += 1 #iの二進表示の１の個数
                for x, y in XY[j]:
                    if i>>x & 1 != y:
                        flag = False
                        break
        if flag:
            ans = max(ans, cnt)

    print(ans)
main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    N = int(input())
    g = [[-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())
            g[i][x-1] = y
    
    ans = 0
    for i in range(2**N):
        d = [0]*N
        for j in range(N):
            if i>>j & 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:
                       continue 
                    if g[j][k] != d[k]:
                        ok = False
        if ok:
            ans = max(ans, bin(i).count('1'))
    
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
#pypyではscipy, numpyは使えない
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
from datetime import datetime as dt

def main():
  n = int(readline())
  info = []
  for i in range(n):
    a = int(readline())
    for _ in range(a):
      x, y = map(int, readline().split())
      info.append((i, x-1, y))
  A = np.array(list(product([0,1], repeat=n)),np.bool)
  for i, x, y in info:
    bl = (~A[:,i]) | (A[:,x]==bool(y))
    A = A[bl]
  print(A.sum(axis=1).max())
  
  
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def judge(bit, n, v):
    # i 人目の証言を検証する
    for i in range(n):
        # 1人目が「不親切」だったら証言はすべて無視
        if not (bit & (1 << i)):
            continue

        for x, y in v[i]:
            # y == 1 なのに「不親切」だったらダメ
            if y == 1 and not (bit & (1 << x)):
                return False

            # y == 0 なのに「正直者」だったらダメ
            if y == 0 and (bit & (1 << x)):
                return False
    return True


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

ans = 0
for bit in range(1 << n):
    if not judge(bit, n, v):
        continue

    # bit に含まれる人数を数える
    cnt = 0
    for i in range(n):
        if bit & (1 << i):
            cnt += 1
    ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
def main():
    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
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    l = [[-1]*n for _ in range(n)]
    for i in range(n):
        a = int(input())
        for _ in range(a):
            x,y = map(int, input().split())
            l[i][x-1] = y
    
    res = 0
    for s in range(1<<n):
        flag = 1
        check = [-1]*n
        #i人目
        for i in range(n):
            #i人目が正直者
            if (s>>i) & 1:
                #j人目についての証言
                for j in range(n):
                    if i==j:
                        continue
                    if l[i][j] == -1:
                        continue
                    if check[j] == -1:
                        check[j] = l[i][j]
                    else:
                        if check[j] != l[i][j]:
                            flag = 0
            # #i人目が真偽不明
            # else:
            #     #j番目の証言
            #     for j in range(n):
            #         if i==j:
            #             continue
            #         if l[i][j] == -1:
            #             continue
            #         if check[j] == -1:
            #             check[j] = l[i][j]^1
            #         else:
            #             if check[j] == l[i][j]:
            #                 flag = 0
            if flag==0:
                break
        else:
            for i in range(n):
                if check[i] == -1:
                    continue
                if ((s>>i)&1) != check[i]:
                    break
            else:
                res = max(res, bin(s).count('1'))
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

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

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

maxT = 0

for i in range(2**N ):
    ju = [0] * N
    ind = 0

    trust = 0
    for b in reversed(str(bin(i))[2::]):
        if b == "1":
            ju[ind] = 1
            trust += 1
        ind += 1
    
    flag = 0
    for n in range(N):

        if ju[n] == 0:
            continue

        for  y in A[n]:
            if ju[y[0]-1] != y[1]:
                flag = 1
                break
        
        if flag == 1:
            break
        
    if flag == 0:
        maxT = max(maxT , trust )

print(maxT)

Submission status: Accepted

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

ret = 0
for i in range( 2 ** n - 1, 0, -1 ):
  o = [int(i) for i in str( "{:b}".format(i).zfill(n) )]
  is_right = True
  for j in range( n ):
    for m in range( n ):
      if o[j] == 1:
        is_right &= ( l[j][m] in [-1, o[m]] )
    if not is_right:
      break
        
  if is_right:
    ret = sum(o)
    break
          
print( ret )

Submission status: Accepted

Solution code:
from itertools import product

N = int(input())
input_table = list([-1] * N for _ in range(N))
ans = 0

for i in range(N):
    A_i = int(input())
    for j in range(A_i):
        x_i_j, y_i_j = map(int, input().split())
        x_i_j -= 1
        input_table[i][x_i_j] = y_i_j

for pat in product((0, 1), repeat = N):
    for i in range(N):
        if pat[i] == 1:
            for j in range(N):
                i_says_j_is_kind = input_table[i][j]
                if i_says_j_is_kind == -1:
                    continue
                else:
                    if i_says_j_is_kind != pat[j]:
                        break
            else:
                continue
            break
    else:
        honest_persons = sum(pat)
        ans = max(ans, honest_persons)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
evidencies = {}
for i in range(N):
    A = int(input())
    evidence = []
    for j in range(A):
        x, y = map(int, input().split(" "))
        evidence.append((x - 1, y))
    evidencies[i] = evidence

#  B r u t e   F o r c e   S e a r c h
ans = 0
for S in range((1 << N)):
    is_conflict = False
    bitcount = 0
    for i in range(N):
        if ((S >> i) & 1) == 1:
            # i is honest
            bitcount += 1
            for ev in evidencies[i]:
                # ev[0] is ev[1]?
                is_conflict |= ((S >> ev[0]) & 1) ^ ev[1]
    if not is_conflict:
        ans = max(bitcount, ans)

print(ans)

Submission status: Accepted

Solution code:
# N = int(input())
#
# ans = []
# for i in range(N):
#     A = int(input())
#     for j in range(A):
#         ans.append(list(map(int, input().split())))
#
# print(ans)

# print(bin(1 << 15))
# print(1 << 15)
# print(2**15)
n= int(input())
shogens = []
for i in range(n):
    a = int(input())
    shogens.append([])
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        shogens[i].append((x, y))
# print(shogens)

# def is_honest(i, j):
#     return (i >> j) % 2 == 1
#
# def honest_cnt(i):
#     ans = 0
#     for j in range(n):
#         ans += is_honest(i, j)
#     return ans
# ans = 0
#
# for i in range(1 << n):
#     ok = True
#     print(bin(i))
#     for j in range(n):
#         if not is_honest(i, j):continue
#         for (x, y) in shogens[j]:
#             if y == 0 and is_honest(i, x):ok = False
#             if y == 1 and not is_honest(i, x):ok = False
#
#     if ok:
#         ans = max(ans, honest_cnt(i))
#
# print("ans", ans)

lists = {i : 0 for i in range(1 << 15)}
for i in range(1 << 15):
    count = 0
    for j in range(n):
        if (i >> j) & 1:
            for x, y in shogens[j]:
                if y == 0 and (i >> x) & 1: count -= 1
                if y == 1 and not (i >> x) & 1: count -= 1
    if count == 0:
        ans = 0
        for k in range(n):
            ans += (i >> k) % 2
        lists[i] = ans

print(max(lists.values()))
# print(0 >> 0)

Submission status: Accepted

Solution code:
n=int(input())
a=[0]*n
x=[[0]*n for i in range(n)]
y=[[0]*n for i in range(n)]
for i in range(n):
  a[i]=int(input())
  for j in range(a[i]):
    x[i][j],y[i][j]=map(int,input().split())
ans=0
for bit in range(1<<n):
  res=True
  for i in range(n):
    if bit & (1<<i):
      for j in range(a[i]):
        if ((bit>>(x[i][j]-1))&1)^y[i][j]:
          res=False
  if res:
    wklen=len(str(format(bit,"b")).replace("0",""))
    ans = ans if ans>=wklen else wklen
print(ans)

Submission status: Accepted

Solution code:
import itertools as it

n = int(input())
lis = [[] for _ in range(n)]
val = list(it.product([0, 1], repeat=n))

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


def honesty(k, lis, n):
    for i in range(n):
        if k[i] == 1:
            for l, m in lis[i]:
                if k[l] != m:
                    return False
    return True


res = 0
for k in val:
    if honesty(k, lis, n):
        res = max(res, sum(k))
print(res)

Submission status: Accepted

Solution code:
n = int(input())
t = [[] for _ in range(n)]
s = [[] for _ in range(n)]

for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        if y == 1:
            t[i].append(x - 1)
        else:
            s[i].append(x - 1)
res = 0
for k in range(pow(2, n)):
    judge = True
    cnt = 0
    for i in range(n):
        if (k >> i) & 1 == 1:
            for e in t[i]:
                if (k >> e) & 1 == 0:
                    judge = False
            for e in s[i]:
                if (k >> e) & 1 == 1:
                    judge = False
            cnt += 1
    if judge:
        res = max(res, cnt)

print(res)

Submission status: Accepted

Solution code:
N=int(input())
A=[0]*N
rel=[]
for i in range(N):
    tmp = []
    A[i] = int(input())
    for j in range(A[i]):
        tmp.append(list(map(int,input().split())))
    rel.append(tmp)


ans = 0
for i in range(1<<N):
    cond = [0] * N
    for j in range(N):
        if 1&(i>>j):
            cond[j] = 1
    
    mujun = False
    for j in range(N):
        if cond[j] == 1:
            for k in range(A[j]):
                if cond[rel[j][k][0]-1] != rel[j][k][1]:
                    mujun = True
    
    if not mujun:
        if ans < sum(cond):
            ans = sum(cond)

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
XY = [[] for _ in range(N)]
for i in range(N):
    a = ir()
    for j in range(a):
        x, y = lr()
        XY[i].append((x-1, y)) # 0-indexedとして

A = np.array(list(itertools.product([0, 1], repeat=N)), np.bool)
for i in range(N):
    for x, y in XY[i]:
        bl = (~A[:, i]) | (A[:, x] == bool(y)) # その人が不親切の場合、または、正直者の場合
        A = A[bl]

answer = np.sum(A, axis=1).max()
print(answer)
# 24 repeat

Submission status: Accepted

Solution code:
import itertools

N=int(input())
testimony=[]
for i in range(N):
    a=int(input())
    l=[]
    for j in range(a):
        l2=[int(k) for k in input().split()]
        l.append(l2)
    testimony.append(l)

nums=[0,1]
kind=itertools.product(nums,repeat=N)

def is_corect_kind(k,testimony,N):
    for i in range(N):
        if k[i]==1:
            for t in testimony[i]:
                if k[t[0]-1]!=t[1]:
                    return False
    return True

answer=0
for k in kind:
    if is_corect_kind(k,testimony,N):
        answer=max(answer,sum(k))
print(answer)

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

answer = 0
N = ir()
honest = [[] for _ in range(N+1)]
liar = [[] for _ in range(N+1)]
# bit全探索
for i in range(N):
    a = ir()
    for _ in range(a):
        x, y = lr()
        if y == 1:
            honest[i].append(x-1)
        else:
            liar[i].append(x-1)

for bit in range(1<<N):
    bl = True
    h = []
    for i in range(N):
        if (bit >> i) & 1:
            h.append(i)
    s = set(h)
    for person in h:
        for x in honest[person]:
            if x not in s:
                bl = False
                break
        for y in liar[person]:
            if y in s:
                bl = False
                break
        if not bl:
            break
    if bl:
        answer = max(answer, len(s))

print(answer)

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 i in range(1,2**n):
    ls = [0] * n
    
    for j in range(n):
        if (i >> j) & 1:
            ls[j] = 1
            
    fl = 1
    for j in range(n):
        for k,l in s[j]:
            if ls[j] == 1:
                if ls[k] != l:
                    fl = 0
    if fl == 1:
        ans = max(ans , sum(ls))
    
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[[] for _ in range(n)]
for i in range(n):
    cnt=int(input())
    while cnt>0:
        x,y=map(int,input().split())
        x-=1
        a[i].append([x,y])
        cnt-=1
ans=0
for mask in range(1<<n):
    #0 means bad 1 means good
    #check if this choice leads to a valid solution
    honest=[]
    for j in range(n):
        if (mask>>j)&1:
            honest.append(j)
    choice=True
    for i in honest:
        for j in a[i]:
            if (j[0] in honest and j[1]==0) or (j[0] not in honest and j[1]==1):
                choice=False
                break
        if choice==False:
            break
    if choice:
        ans=max(ans,len(honest))
print(ans)

Submission status: Accepted

Solution code:
# 入力の受取
n = int(input())
a = [0] * (n+1)
x = [[0] * (n+1) for _ in range(n+1)]
y = [[0] * (n+1) for _ in range(n+1)]

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

# ビット全探索用のシーケンスを生成
import itertools
seq = [0, 1]
arr = itertools.product(seq, repeat=(n))

# ビット全探索
# 証言と整合する場合は，その際の人数をリストに格納
ans = [0]
for v in arr:
    v = [0] + list(v)
    
    flag = True
    # 証言と整合しない場合，フラグをfalseにする
    for i in range(1, n+1):
        if v[i] == 1:
            for k in range(1,a[i]+1):
                if y[i][k] == 1 and v[x[i][k]] == 0:
                    flag = False
                if y[i][k] == 0 and v[x[i][k]] == 1:
                    flag = False
                          
    # 証言と整合した場合
    if flag:
        ans.append(sum(v))


# 証言と整合したケースの人数の最大値を出力
print(max(ans))

Submission status: Accepted

Solution code:
n = int(input())

talk = []
for i in range(n):
    a = int(input())
    talk += [[list(map(int,input().split())) for _ in range(a)]]
    
ans = 0
    
for i in range(2 ** n):
    result = [True] * n
    
    for j in range(n):
        if ((i >> j) & 1):
            result[n - 1 -j] = False
    check = 1       
    for k in range(n):
        for x, y in talk[k]:
            if result[k] == True:
                if result[x-1] == y:
                    continue
                else:
                    check = 0
                    break
        else:
            continue
        break
    
    if check == 1:
        ans = max(ans, sum(result))
            
print(ans)

Submission status: Accepted

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

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

ls = [-1]*n
ans = 0

for i in range(2**n):
    b = str(bin(i))[2:]
    c = b.zfill(n)
    # print(c)
    numbers = sum(list(map(int,list(str(c)))))
    for j in range(n):
        if c[j]=="0":
            pass
        else:
            for k in range(a[j]):
                x = xy[j][k][0]
                y = xy[j][k][1]
                # print(x,y)
                if c[x-1]==str(y):
                    pass
                else:
                    numbers = 0
        # print("--")
    ans = max(ans,numbers)
    # print("------")

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
men=[0]*(n+1)
sta=[[[0]]]
for i in range(1,n+1):
  men[i]=int(input())
  xy=[list(map(int,input().split())) for j in range(men[i])]
  sta.append(xy)
ho=0
for bi in range(2**n):
  honest=[-1]*(n+1)
  honest[0]=0
  x=format(bi,'b')
  x='0'*(n-len(x)+1)+x
  ok='Yes'
  for i in range(1,n+1):
    if x[i]=='1':
      for j in range(men[i]):
        if sta[i][j][1]!=int(x[sta[i][j][0]]):
          ok='No'
  if ok=='Yes':
    ho=max(ho,x.count('1'))

print(ho)

Submission status: Accepted

Solution code:
N=int(input())

A=[[-1]*N 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][x-1]=y
#正直者が正直者に不親切と言われていない
#→正直ものが不親切を正直者と言っていないか
ans=0
for i in range(2**N):
  ok=True
  for j in range(N):
    if (i>>j&1)==1:
      for k in range(N):
        if A[j][k]!=-1 and (i>>k&1)!=A[j][k]:
          ok=False
  if ok:
    ans=max(ans, bin(i).count("1"))
  
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
shougen=[(0,0) for i in range(0,N)]
for i in range(0,N):
    A=int(input())
    honest=0
    unkind=0
    for j in range(0,A):
        x,y=map(int,input().split())
        if y==0:
            unkind+=2**(x-1)
        else:
            honest+=2**(x-1)
    shougen[i]=(honest,unkind)

ans=0
for i in range(0,2**N):
    honest=i
    unkind=2**N-1-i
    check=True
    test=0
    for j in range(0,N):
        if (i>>j)&1 ==1:
            test+=1
            x,y=shougen[j]
            if (honest-x)^x!=honest or (unkind-y)^y!=unkind:
                check=False
    if check:
        if test>ans:
            ans=test

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N=int(input())
data=[]
for i in range(N):
    for j in range(int(input())):
        x,y=map(int,input().split())
        data.append((i,x-1,y))
ans=0
for i in product([1,0],repeat=N):
    s=True
    for k in data:
        if i[k[0]]==1 and i[k[1]]!=k[2]:
            s=False
            break
    if s:
        ans=max(ans,sum(i))
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
g=[[-1]*N for _ in range(N)]
ans=0
for i in range(N):
    A=int(input())
    for _ in range(A):
        x,y=map(int,input().split())
        g[i][x-1]=y
for s in range(2**N):
    flag=1
    for i in range(N):
        if (s>>i&1):
            for j in range(N):
                if g[i][j]!=-1 and (s>>j&1)!=g[i][j]:
                    flag=0
                    break
        if flag==0:break
    if flag==1:
        t=0
        x=s
        while x>0:
            t+=x%2
            x//=2
        ans=max(ans,t)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
g=[[-1]*N for _ in range(N)]
ans=0
for i in range(N):
    A=int(input())
    for _ in range(A):
        x,y=map(int,input().split())
        g[i][x-1]=y
for s in range(2**N):
    flag=1
    for i in range(N):
        if (s>>i&1):
            for j in range(N):
                if g[i][j]!=-1 and (s>>j&1)!=g[i][j]:
                    flag=0
    if flag==1:
        t=0
        x=s
        while x>0:
            t+=x%2
            x//=2
        ans=max(ans,t)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
lst=[[] for _ in range(N)]
for i in range(N):
  for j in range(int(input())):
    x,y=map(int,input().split())
    x-=1
    lst[i].append([x,y])
ans=0
for i in range(2**N):
  honest=[]
  unkind=[]
  flag=0
  for j in range(N):
    if (i>>j)&1:        # jは正直者
      honest.append(j)
    else:
      unkind.append(j)
  for p in honest:
    for l in lst[p]:
      x,y=l[0],l[1]
      if y:
        if x in unkind:
          flag=1
          break
      else:
        if x in honest:
          flag=1
          break
  if flag!=1:
    ans=max(ans,len(honest))
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

N = i_i()

arr = [[] for _ in range(N)]
for i in range(N):
    A = i_i()
    for _ in range(A):
        x, y = i_l()
        arr[i].append((x-1, y))

ans = 0
for i in range(1, 1<<N):
    ok = True
    for j in range(N):
        if not i>>j&1:
            continue
        for x, y in arr[j]:
            if (i >> x) & 1 != y:
                ok = False
                break
        if not ok:
            break
    if ok:
        ans = max(ans, bin(i)[2:].count('1'))

print(ans)

Submission status: Accepted

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
# import numpy as np
from functools import reduce
# import statistics
import decimal
import heapq
import collections
import itertools
from operator import mul

sys.setrecursionlimit(100001)


# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

n = int(input())

d = []
for _ in range(n):
    tmp = int(input())
    tmpa = getSomeInputListInt(tmp)
    d.append(tmpa)



ans = 0
for i in range(int(pow(2, n))):
    flg = True
    cnt = 0
    for j in range(len(d)):
        tmp = (i >> j) & 1
        if tmp == 0:
            continue

        cnt += 1

        for k in range(len(d[j])):
            tmp = (i >> (d[j][k][0]-1)) & 1
            if tmp != d[j][k][1]:
               flg = False
               break
        if not flg:
            break

    if flg:
        ans = max(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

X = [[-1]*N for i in range(N)]
for i in range(N):
    a = int(input())
    for j in range(a):
        b, c = map(int, input().split())
        X[i][b-1] = c
ans = 0
for i in range(2**N):
    Y = [0]*(N)
    for j in range(N):
        if ((i >> j) & 1):
            Y[j] = 1
    flag = True
    for j in range(N):
        if Y[j] == 1:
            for k in range(N):
                if X[j][k] == -1:
                    continue
                if X[j][k] != Y[k]:
                    flag = False
    if flag:
        ans = max(ans, sum(Y))

print(ans)

Submission status: Accepted

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

import numpy as np
import itertools
def tfcheck(say,tf):
    if len(say)==0:
        return 0
    for i in range(len(say)):
        for j in range(len(say[i])):
            [x,y] = say[i][j]
            if tf[x-1] == -1:
                tf[x-1] = y
                continue
            if tf[x-1] != y:
                return 0
    return 1
status = [[0,1] for i in range(n)]
m = 0
for tf in itertools.product(*status):
    s = []
    for i in range(n):
        if tf[i] == 1:
            s.append(say[i])
    if tfcheck(s,tf)==1:
        if sum(tf)>m:
            m = sum(tf)
print(m)

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)
 
# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]
 
# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]
 
# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())
 
def log(*args):
    print("DEBUG:", *args, file=sys.stderr)
 
def count_bit_one(bits, n):
    ret = 0
    for keta in range(n):
        if bits & 2**keta:
            ret += 1
    return ret
 
n = int(input())
aaa = [None] * n
for i in range(n):
    a = int(input())
    aaa[i] = [ get_nums_l() for _ in range(a)]
 
ans = -1
for bits in range(2**n):
    ng = False
    for keta in range(n):
        if bits & 2**keta != 0:
            for a in aaa[keta]:
                if (bits & 2**(a[0]-1) != 0) != (a[1]==1):
                    ng = True
                    break
        if ng:
            break
    if not ng:
        ans = max(ans, count_bit_one(bits, n))
 
print(ans)

Submission status: Accepted

Solution code:
def is_consistent(bit, testimony):
    all_consistence = True
    for shift in range(n):
        if (bit >> shift) & 1:
            mask, tf = testimony[shift]
            if (bit & mask) != (tf & mask):
                all_consistence = False
    return all_consistence

n = int(input())
testimony = [0] * n
for i in range(n):
    mask, tf = 0, 0
    for j in range(int(input())):
        x, y = map(int, input().split())
        mask += 1 << (x - 1)
        tf += y << (x - 1)
    testimony[i] = (mask, tf)

max_honest = 0
for bit in range(1 << n):
    if is_consistent(bit, testimony) and (max_honest < bin(bit).count('1')):
        max_honest = bin(bit).count('1')
print(max_honest)

Submission status: Accepted

Solution code:
def is_consistent(bit, t_tuple):
    mask, tf = t_tuple
    if (bit & mask) == (tf & mask):
        return True
    else:
        return False

n = int(input())
testimony = [0] * n
for i in range(n):
    mask, tf = 0, 0
    for j in range(int(input())):
        x, y = map(int, input().split())
        mask += 1 << (x - 1)
        tf += y << (x - 1)
    testimony[i] = (mask, tf)

max_honest = 0
for bit in range(1 << n):
    honest = 0
    all_consistence = True
    for shift in range(n):
        if ((bit >> shift) & 1):
            if is_consistent(bit, testimony[shift]):
                honest += 1
            else:
                all_consistence = False    
    if all_consistence and (max_honest < honest):
        max_honest = honest
print(max_honest)