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())

says = []

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


# print(says)
max_upright_count = 0
for i in range(1 << N):
    integrate = True
    upright_count = 0
    declares = [-1 for _ in range(N)]
    for j in range(N):
        if not integrate:
            continue
        # もし真偽不明の場合は正しいことを言う場合もあるから無視する
        if (i >> j & 1) == 1:
            upright_count += 1
            for x, y in says[j]:
                # print(i, j, x, y, declares)
                if declares[x - 1] == -1:
                    declares[x - 1] = y
                else:
                    if declares[x - 1] == y:
                        continue
                    else:
                        integrate = False
                        break
    # print(bin(i), integrate, declares, upright_count)
    for j in range(N):
        # print((i >> j) & 1, declares[j])
        if ((i >> j) & 1) != declares[j] and declares[j] != -1:
            # print(False)
            integrate = False
    # print(integrate)
    if integrate:
        max_upright_count = max(max_upright_count, upright_count)
print(max_upright_count)

Submission status: Accepted

Solution code:
n = int(input())
m = []
a = [[] for i in range(n)]
for i in range(n):
    tmp = int(input())
    m.append(tmp)
    for j in range(tmp):
        a[i].append(list(map(int,input().split())))
ans = 0
for i in range(2**n):
    cnt = 0
    for j in range(n):
        flg = True
        if i >> j & 1:
            cnt += 1
            for k in range(m[j]):
                kj = (i >> (a[j][k][0]-1)) & 1
                if a[j][k][1] != kj:
                    flg = False
                    break
            if not flg:
                break
    if flg:
        ans = max(ans, cnt)
            
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import itertools

n = int(input())

l = [[] for i in range(n)]
p = [i for i 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,y))

for i in range(n,-1,-1):
    for comb in itertools.combinations(p,i):
        tmp = [1 if j in comb else 0 for j in range(n)]
        F = True
        for c in comb:
            for k in l[c]:
                if tmp[k[0]-1] != k[1]:
                    F = False
        if F:
            print(i)
            exit()

print(0)

Submission status: Accepted

Solution code:
from typing import List

# 人iの証言を人jに対する証言をリストで格納。1:正直者, 0:不親切, -1:言及なし
def io_info() -> List[List[int]]:
    N = int(input())
    res = [[-1] * N for _ in range(N)]
    for n in range(N):
        a = int(input())
        for _ in range(a):
            x, y = map(int, input().split())
            res[n][x-1] = y
    return res


def main():
    infos = io_info()
    n = len(infos)
    ans = 0
    for i in range(1 << n):
        d = [0] * n
        for j in range(n):
            # iのj+1ビット目が1かどうか,d[j]が正直なら1を割り当てる
            if (i >> j) & 1:
                d[j] = 1
        ok = True
        for j in range(n):
            if d[j]:
                for k in range(n):
                    if infos[j][k] == -1: continue
                    if infos[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:
def check(i,N,Ls):
    count=0
    for j in range(N):
        if (i>>j)%2==1:
            for k in Ls[j]:
                if ((i>>(k[0]-1))%2)!=k[1]:
                    return 0
            count+=1
    return count
                
N=int(input())
A_ls=[]
Ls=[]
for i in range(N):
    A=int(input())
    A_ls.append(A)
    ls=[]
    for j in range(A):
        x,y=map(int,input().split())
        ls.append((x,y))
    Ls.append(ls)

ans=0
for i in range(2**N):
    num=check(i,N,Ls)
    if num>ans:
        ans=num
print(ans)

Submission status: Accepted

Solution code:
# bit全探索 典型といえば典型（問題文の意味がよくわからんので読解力コンテスト）

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

ans = 0
for bit in range(1 << n):
    p = ["不親切"] * n
    ng = False
    # bitの立っているのを正直者と仮定
    for i in range(n):
        if bit >> i & 1 == 1:
            # 上位bit = 小さいインデックス、になる（ように実装してしまった わかりづらい
            p[n - i - 1] = "正直者"
    for i in range(n):
        if p[i] == "不親切":
            # まあ不親切な人間のことなんて聞かなくていい
            continue
        for s in syogen[i]:
            if p[s[0] - 1] == "正直者" and s[1] == 1:
                # 証言と一致する
                continue
            elif p[s[0] - 1] == "不親切" and s[1] == 0:
                # 証言と一致する
                continue
            else:
                # 証言と一致しない
                ng = True
                break

    if not ng:
        ans = max(ans, p.count("正直者"))
print(ans)

Submission status: Accepted

Solution code:
#C
import itertools
#入力
n = int(input())
xy = []
a=[]
for i in range(n):
    a += [int(input())]
    xy += [[list(map(int, input().split())) for _ in range(a[i])]]
    
#演算
#bit全捜索
ans = 0
for i in range(2 ** n):
    flag = 0
    for j in range(n):
        #iをjだけシフトした一の位が１である(iのｊ番目が1であるとき)
        if (i >> j) & 1 == 1:
            #xy[j][0]番目がxy[j][1]である供述Statementが現実と矛盾していないか確かめる
            for ParsonStatement in xy[j]:
                if (i >> (ParsonStatement[0] - 1) & 1 )!= ParsonStatement[1]:
                    #矛盾していたらFlagを立ててbreak
                    flag = 1
                    break
    #Flagが立っていない＞＞矛盾点が発見されていない＞＞大丈夫
    if flag == 0:
        ans=max(ans,bin(i)[2:].count("1"))     
print(ans)

Submission status: Accepted

Solution code:
def main():
    import itertools
    n = int(input())
    test = []
    for i in range(n):
        a = int(input())
        t = []
        for j in range(a):
            x,y = map(int,input().split())
            t.append([x,y])
        test.append(t)
    stats = ((0,1) for i in range(n))
    ans = 0
    for k in itertools.product(*stats):
        tf = [-1 for i in range(n)]
        flg = 0
        for i in range(len(k)):
            if k[i]==1:
                for t in test[i]:
                    if tf[t[0]-1]==-1:
                        tf[t[0]-1] = t[1]
                    else:
                        if tf[t[0]-1] != t[1]:
                            flg = 1
                            break
        for i in range(len(k)):
            if tf[i] != -1:
                if tf[i] != k[i]:
                    flg = 1
                    break
        if flg == 0:
            if ans < sum(k):
                ans = sum(k)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
 
testimony = [[] for _ in range(N)]
 
for i in range(N):
    num = int(input())
    for j in range(num):
        person, state = map(int, input().split())
        testimony[i].append([person-1, state])

honest = 0
for i in range(1, 2**N):
    flag = 0
    for j in range(N):
        if (i>>j)&1 == 1: # j番目は正直と仮定
            for x,y in testimony[j]:
                if (i>>x)&1 != y: # j番目は正直だが矛盾を発見
                    flag = 1
                    break
    if flag == 0:  # 矛盾がある場合はflag == 1になる
        honest = max(honest, bin(i)[2:].count('1'))  # 1の数をカウントし最大となるものを選択
print(honest)

Submission status: Accepted

Solution code:
N = int(input())
 
testimony = [[] for _ in range(N)]
 
for i in range(N):
    num = int(input())
    for j in range(num):
        person, state = map(int, input().split())
        testimony[i].append([person-1, state])
        
honest = 0
for i in range(1, 2**N):
    flag = 0
    for j in range(N):
        if (i>>j)&1 == 1: # j番目は正直と仮定
            for x,y in testimony[j]:
                if (i>>x)&1 != y: # j番目は正直だが矛盾を発見
                    flag = 1
                    break
    if flag == 0:  # 矛盾がある場合はflag == 1になる
        honest = max(honest, bin(i)[2:].count('1'))  # 1の数をカウントし最大となるものを選択
print(honest)

Submission status: Accepted

Solution code:
from itertools import product

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

MAX=0
for p in product(range(2),repeat=N):
  flag=0
  for i in range(N):
    if p[i] == 1:
      for j in range(len(statement[i])):
        if statement[i][j][1]==1:
          x = statement[i][j][0]
          if p[x] != 1:
            flag=1
            break
        if statement[i][j][1]==0:
          x = statement[i][j][0]
          if p[x] == 1:
            flag=1
            break
    if flag==1:break
  if flag==1:continue
  if sum(p) > MAX:
    MAX=sum(p)

print(MAX)

Submission status: Accepted

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


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

  max_ = 0
  for bit in range(1 << N):
    for i in range(N):
      mask = (1 << i)
      # i番目の仮定についてN人の証言について検証
      for j in range(N):
        if A[j][i] == -1:
          continue
        # j番目の人が正直者と仮定してiについての証言が仮定と一致しない
        if (bit & (1 << j)) and A[j][i] != bool(bit & mask):
          # print(f'bit:{bin(bit)}, i:{i}, j:{j}, A[j][i]:{A[j][i]} != {bit & mask}')
          break
      else:
        # cnt += 1
        continue
      break
    else:
      # print(bin(bit))
      max_ = max(max_, bin(bit).count('1'))

  print(max_)


if(__name__ == '__main__'):
  main()

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
proof_list=np.array([[None]*N for i in range(N)])
check_list=[True]*N
for i in range(N):
    A = int(input())
    for j in range(A):
        x,y = map(int,input().split())
        proof_list[i][x-1] = y
ans = 0
for i in range(2**N):
    honests = []
    for j in range(N):
        if((i>>j)&1):
            honests.append(j)
    flag = True
    for l in honests:
        for k in range(N):
            if (k in honests) and proof_list[l][k] == 0:
                flag = False
            elif(k not in honests) and proof_list[l][k] ==1:
                flag = False
    if flag:
        ans = max(ans,len(honests))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
G = [[-1] * N for i in range(N)]
ans = 0
for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split())
        G[i][x-1] = y
for bit in range(2**N):
    honests = []
    for i in range(N):
        if bit & (1<<i):
            honests.append(i)
    flag = True
    for j in honests:
        for k in range(N):
            if (k in honests) and G[j][k] == 0:
                flag = False
            elif(k not in honests) and G[j][k] == 1:
                flag = False
    if flag:
        ans = max(ans, len(honests))
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())

    user_remarks = {}

    for i in range(1, N+1):
        A = int(input())
        user_remarks[i] = []

        for _ in range(A):
            user_id, is_honest = [int(x) for x in input().split()]
            user_remarks[i].append((user_id, is_honest == 1))

    max_count = 0

    for i in range(2**N):
        honest = {}
        is_ok = True
        for x in range(N):
            # フラグが経っている時 = 正直もの
            if ((i >> x) & 1):
                honest[x+1] = True

                if is_ok:
                    # 正直者の証言チェック
                    for user_remark in user_remarks[x+1]:
                        target_user = user_remark[0]
                        target_is_honest = user_remark[1]

                        # ターゲットは正直者である場合
                        if target_is_honest:
                            # 正直者ではなかったら矛盾している
                            if not ((i >> (target_user-1)) & 1):
                                is_ok = False

                        # ターゲットが不親切な人である場合
                        if not target_is_honest:
                            # 正直者だったら矛盾している
                            if ((i >> (target_user-1)) & 1):
                                is_ok = False

        if is_ok:
            max_count = max(max_count, len(honest))

    print(max_count)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
say = {}
for i in range(N):
    say[i] = []
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split())
        x -= 1
        say[i].append((x, y))
ans = 0
for i in range(1 << N):
    ok = True
    Honecount = 0
    for j in range(N):
        if((i >> j) & 1 == 0):
            continue
        Honecount += 1
        for k in say[j]:
            if ((i >> k[0]) & 1) != k[1]:
                ok = False
                break
        if ok == False:
            break
    if ok == True:
        ans = max(ans, Honecount)

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

def solve():
    N = int(input())
    graph = {i: [] for i in range(1, N+1)}
    for i in range(N): 
        A = int(input())
        for _ in range(A):
            x,y = map(int, input().split())
            graph[i+1].append((x,y))
            
    def dfs(nodes):
        searched = [-1] * N
        stack = [i+1 for i,node in enumerate(nodes) if node == 1]
        ret_len = len(stack)
        
        while stack:
            node = stack.pop(0)
            for x,y in graph[node]:
                if nodes[x-1] != y: return -1
                if searched[x-1] == -1:
                    searched[x-1] = y
                    if y == 1: stack.append(x)
                        
        # print(nodes, searched)
        return ret_len
                    
        
    ret = 0
    for nodes in product([0,1], repeat=N):
        ret = max(ret, dfs(nodes))
        
    print(ret)
    
solve()

Submission status: Accepted

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

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

ans=[0]
for i in range(2**n):
    ch=1
    for k in range(0,n):
        if ((i>>k)&1):
            for q in a[k]:
                if ((i>>q[0])&1)==(q[1]^1):
                    ch=0

    if ch==1:
        ans.append(bin(i).count("1"))
print(max(ans))

Submission status: Accepted

Solution code:
n = int(input())
v = [[tuple(map(int, input().split()))for i in range(int(input()))]
     for i in range(n)]

ans = 0
for i in range(2**n):
    f = True
    a = 0
    for j in range(n):
        if (i >> j) & 1:
            if all(i >> (x - 1) & 1 == y for x, y in v[j]):
                a += 1
            else:
                f = False
                break
    if f:
        ans = max(ans, a)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
v = [[tuple(map(int, input().split()))for i in range(int(input()))]
     for i in range(n)]

ans = 0
for i in range(2**n):
    f = [0] * n
    xy = []
    for j in range(n):
        if (i >> j) & 1:
            f[j] = 1
            xy.append(v[j])
    flag = True
    for xyi in xy:
        for x, y in xyi:
            #print(f,x,y,bin(i))
            if (i>>(x-1))&1 != y:
                flag = False
                break
    if flag:
        ans = max(ans, len(xy))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
v = [[tuple(map(int, input().split()))for i in range(int(input()))]
     for i in range(n)]

ans = 0
for i in range(2**n):
    f = [False] * n
    xy = []
    for j in range(n):
        if (i >> j) & 1:
            f[j] = True
            xy.append(v[j])
    flag = True
    for xyi in xy:
        for x, y in xyi:
            if f[x - 1] is not bool(y):
                flag = False
                break
    if flag:
        ans = max(ans, len(xy))
print(ans)

Submission status: Accepted

Solution code:
import itertools
n = int(input())
l = []
for i in range(n):
    d = int(input())
    for dd in range(d):
        x, y = map(int, input().split())
        l.append([i, x-1, y])
 
ans = 0
for p in itertools.product([0, 1], repeat=n):
    for ll in l:
        if p[ll[0]] == 1 and p[ll[1]] != ll[2]:
            break
    else:
        ans = max(ans, sum(p))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = [set() for _ in range(n)]
b = [set() for _ in range(n)]
for i in range(n):
    nn = int(input())
    for j in range(nn):
        x,y = list(map(int, input().split()))
        x -= 1
        if y==1:
            a[i].add(x)
        else:
            b[i].add(x)
ans = -1
for bit in range(1<<n):
    tmpa = set()
    tmpb = set()
    tmp2a = set()
    tmp2b = set()
    for j in range(n):
        if bit>>j&1:
            tmpa |= a[j]
            tmpb |= b[j]
            tmp2a.add(j)
        else:
            tmp2b.add(j)
    if len(tmpa&tmpb)==0 and len(tmp2a&tmpb)==0 and len(tmpa&tmp2b)==0: #and tmpa==tmp2:
        ans = max(ans, len(tmp2a))
print(ans)

Submission status: Accepted

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

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

ans = 0
for bit in range(2**n):
    flag = True
    for i in range(n):
        if bit & (1 << i):
            for j in xy[i]:
                x = j[0]
                y = j[1]
                b = bit & (1 << x)
                if (b and y) or (b == 0 and y == 0):
                    continue
                else:
                    flag = False
                    break
        if not flag:
            break
    if flag:
        ans = max(ans, bin(bit).count('1'))
print(ans)

Submission status: Accepted

Solution code:
g = [[-1 for i in range(15)] for j in range(15)]
# 15×15の行列gを-1で埋めておく

n=int(input()) #参加人数
for i in range(n):
  m = int(input())
  for j in range(m):
    x, y= map(int, input().split())
    g[i][x-1] = y
#人の番号Aは1から始まるのでxの番号も1つ前倒し
# y==1なら正直, Y==0なら不親切
ans=0

for i in range (1<<n): #range(2**n)でも同じはず
  honests = [0 for _ in range(n)] #正直者の番号格納用、0の列
  for j in range(n):
    if (i >> j) & 1:
      honests[j] = 1 
#正直ものが1,3,5,6ならhonests = [1,0,1,0,1,1,・・・]となる
#これを全bitで作成したものがhonests[施行番号][スイッチ行列]
  hantei = True
  for j in range(n):
    if honests[j]==1: 
      #j番目の人の証言が正しいとしたときの分岐
      for k in range(n):
        if g[j][k] == -1: 
          continue #証言なし
        if g[j][k] != honests[k]:
          #g[j][k]はj番目の人が話したk番目の人に対する証言
          #これが異なっていると矛盾が生じている
          hantei = False
  if hantei == True:
    ans = max(ans, honests.count(1))
                     
print(ans)

Submission status: Accepted

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

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

res = 0
for i in range(2**N):
    bi = [j for j in range(N) if (i >> j &1)]
    dic = {}
    for b in bi:
        dic[b] = 1
    
    endfor = False
    for b1 in bi:
        if endfor:
            break
        said = table[b1]
        for k in said.keys():
            if k not in dic.keys():
                if said[k]:
                    endfor = True
                    break
                dic[k] = said[k]
            elif dic[k] == said[k]:
                continue
            else:
                endfor = True
                break
    if not endfor:
        res = max(res, len(bi))

print(res)

Submission status: Accepted

Solution code:
import itertools

def main():
    N = int(input())
    xy = [0] * N
    for i in range(N):
        A = int(input())
        xy_list = []
        for _ in range(A):
            x, y = map(int, input().split())
            xy_list.append((x, y))
        xy[i] = xy_list

    res = 0
    tf_gen = itertools.product([0, 1], repeat=N)
    for tf in tf_gen:
        honest = sum(tf)
        able = True
        for i, xy_l in enumerate(xy):
            for (x, y) in xy_l:
                if tf[x-1] != y and tf[i] == 1:
                    able = False
        if res < honest and able:
            res = honest
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
fo_x = '0' + str(n) + 'b'
a = [None] * n
x = [None] * n
y = [None] * n
ans = 0
flag = 0
for i in range(n):
    a[i] = int(input())
    ax = [None] * a[i]
    ay = [None] * a[i]
    for j in range(a[i]):
        ax[j],ay[j] = map(int,input().split())
    x[i] = ax
    y[i] = ay

for i in range(2 ** n):
    b = format(i,fo_x)
    for j in range(len(b)):
        if b[j] == '0':
            continue
        for z in range(a[j]):
            if str(y[j][z]) != b[x[j][z]-1]:
                flag = 1
                break
        if flag == 1:
            break
    if flag == 0:
        ans = max(ans,b.count('1'))
    flag = 0
print(ans)

Submission status: Accepted

Solution code:
def II(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

N=II()
ans=0
List=[[-1 for _ in range(N)] for _ in range(N)]
for j in range(N):
  A=II()
  for i in range(A):
    x,y=MI()
    x-=1
    List[j][x]=y
for i in range(1<<N):
  honests=[0]*N
  for j in range(N):
    if 1&(i>>j):
      honests[j]=1
  ok=True
  for j in range(N):
    if honests[j]:
      for k in range(N):
        if List[j][k]==-1:
          continue
        if List[j][k]!=honests[k]:
          ok=False
  if ok:
    ans=max(ans,honests.count(1))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ans = [1]*n
T = [[-1]*n for _ in range(n)]
for ni in range(n):
    a = int(input())
    for ai in range(a):
        x, y = map(int,input().split())
        T[ni][x-1] = y

mx = 0
for i in range(pow(2,n)):
    tmx = -1
    B = bin(i)[2:].zfill(n)
    S = [i for i,b in enumerate(B) if b=='1']
    for s in S:
        _Ts = [i for i,t in enumerate(T[s]) if t==1]
        _Tf = [i for i,t in enumerate(T[s]) if t==0]
        if not (set(_Ts)<=set(S) and set(_Tf)&set(S)==set()):
            tmx = 0
            break
    if tmx==-1: tmx=len(S)
    mx = max(mx, tmx)
print(mx)

Submission status: Accepted

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

Submission status: Accepted

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