Problem:


Score : 300 points

Problem Statement

There are N people numbered 1 to N. Each of them is either an honest person whose testimonies are always correct or an unkind person whose testimonies may be correct or not.

Person i gives A_i testimonies. The j-th testimony by Person i is represented by two integers x_{ij} and y_{ij}. If y_{ij} = 1, the testimony says Person x_{ij} is honest; if y_{ij} = 0, it says Person x_{ij} is unkind.

How many honest persons can be among those N people at most?

Constraints

All values in input are integers.

1 \leq N \leq 15

0 \leq A_i \leq N - 1

1 \leq x_{ij} \leq N

x_{ij} \neq i

x_{ij_1} \neq x_{ij_2} (j_1 \neq j_2)

y_{ij} = 0, 1

Input

Input is given from Standard Input in the following format:

N
A_1
x_{11} y_{11}
x_{12} y_{12}
:
x_{1A_1} y_{1A_1}
A_2
x_{21} y_{21}
x_{22} y_{22}
:
x_{2A_2} y_{2A_2}
:
A_N
x_{N1} y_{N1}
x_{N2} y_{N2}
:
x_{NA_N} y_{NA_N}

Output

Print the maximum possible number of honest persons among the N people.

Sample Input 1

3
1
2 1
1
1 1
1
2 0

Sample Output 1

2

If Person 1 and Person 2 are honest and Person 3 is unkind, we have two honest persons without inconsistencies, which is the maximum possible number of honest persons.

Sample Input 2

3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0

Sample Output 2

0

Assuming that one or more of them are honest immediately leads to a contradiction.

Sample Input 3

2
1
2 0
1
1 0

Sample Output 3

1



Sample input:
3
1
2 1
1
1 1
1
2 0


Sample output:
2

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for i in range(n):
    x=int(input())
    aa=[[int(i) for i in input().split()] for i in range(x)]
    a.append(aa)
#print(a)

ans=0
for i in range(2**n):
    status=[True]*n
    for j in range(n):
        if ((i>>j)&1):
            status[j]=False
    check=[None]*n
    flag=True
    for i in range(n):
        if status[i]==True:
            for x,y in a[i]:
                if y==1 and status[x-1]==True and (check[x-1]==None or check[x-1]==True):
                    check[x-1]=True
                elif y==1 and (check[x-1]==False or status[x-1]==False):
                    flag=False
                elif y==0 and status[x-1]==False and (check[x-1]==None or check[x-1]==False):
                    check[x-1]=False
                elif y==0 and (check[x-1]==True or status[x-1]==True):
                    flag=False
    if flag:
        #print(status,check)
        cnt=status.count(True)
        ans=max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

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


for i in range(0, n+1):
    for liers in combinations(list(range(0,n)), i):
        who_ishonest = [1] * n
        for lier in liers:
            who_ishonest[lier] = 0

        for j in range(n):
            if j in liers:
                continue
            
            for testimony in testimonies[j]:
                if who_ishonest[testimony[0]-1] != testimony[1]:
                    break
            else:
                continue
            break
        else:
            print(n-i)
            break
    else:
        continue
    break

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    N = int(stdin.readline().rstrip())
    xys = []
    for _ in range(N):
        A = int(stdin.readline().rstrip())
        xys.append([tuple(int(x) for x in stdin.readline().rstrip().split()) for _ in range(A)])
    max_ = int('1' * N, 2)
    result = 0
    for i in range(max_ + 1):
        sb = bin(i)[2:]
        sb = '0' * (N - len(sb)) + sb
        for idx, c in enumerate(sb):
            if c == '0':
                continue
            is_break = False
            tmp = [None] * N
            for x, y in xys[idx]:
                if (y == 0 and sb[x - 1] == '1') or (y == 1 and sb[x - 1] == '0'):
                    is_break = True
                    break
                if tmp[x - 1] == None:
                    tmp[x - 1] = y
                elif tmp[x - 1] != y:
                    is_break = True
                    break
            if is_break:
                break
        else:
            result = max(result, sb.count('1'))
    print(result)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=[]
h=[]
for _ in range(n):
    x=int(input())
    h.append([tuple(map(int,input().split())) for _ in range(x)])
    a.append(x)
ans=0
for i in range(2**n):
    f=1
    for j in range(n):
        if (i>>j)&1:
            for k in range(a[j]):
                x,y=h[j][k]
                if (i>>(x-1))&1!=y:
                    f=0

    if f:
        c=0
        for j in range(n):
            c+=(i>>j)&1

        ans=max(ans,c)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = ["0","1"]
ab = [0] * n
x = [[0] * n for i in range(n)]
y = [[0] * n for i in range(n)]
for i in range(n):
	ab[i] = int(input())
	for j in range(ab[i]):
		x[i][j], y[i][j] = map(int, input().split())
		x[i][j] -= 1

def check(hit):
	for i in range(n):
		if hit[i] == "0":
			continue
		for j in range(ab[i]):
			if y[i][j] == 1 and hit[x[i][j]] == "0":
				return False
			if y[i][j] == 0 and hit[x[i][j]] == "1":
				return False
	return True

ans = []
def dfs(i, s):
	for j in a:
		if len(s) == n:
			#ary.append(s)
			if check(s):
				ans.append(s.count("1"))
			return
		else:
			dfs(i+1,s+j)
dfs(0,"")

print (max(ans))

Submission status: Accepted

Solution code:
N=int(input())

Axy={}

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

ans=0
for i in range(2**N):
    bi=list(format(i,'b').zfill(N))
    flag=True
    for j in range(N):
        if bi[j]=='0': continue
        if bi[j]=='1':
            for v in Axy[j]:
                if int(bi[v[0]-1])!=v[1]:
                    flag=False
    if flag: ans=max(ans,bi.count('1'))
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
from sys import stdin


def main():
    N = int(stdin.readline().rstrip())
    person = list(range(1, N + 1))
    xy = []
    for i in range(N):
        A = int(stdin.readline().rstrip())
        xy.append([tuple(int(x) for x in stdin.readline().rstrip().split()) for _ in range(A)])
    for i in range(N, 0, -1):
        for comb in combinations(person, i):
            result = [None] * N
            is_fail = False
            for num in comb:
                for x, y in xy[num - 1]:
                    if y == 0:
                        if x in comb:
                            is_fail = True
                            break
                    else:
                        if x not in comb:
                            is_fail = True
                            break

                    if result[x - 1] is None:
                        result[x - 1] = y
                    elif result[x - 1] == y:
                        pass
                    else:
                        is_fail = True
                        break
                if is_fail:
                    break
            else:
                print(i)
                return
    print(0)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read#全部読み込むやつ
readline = sys.stdin.buffer.readline#1行読み込むやつ
readlines = sys.stdin.buffer.readlines#リストで読み込むらしい


import itertools

N = int(readline())

syougen = []
for i in range(N):
    A = int(readline())
    hoge = []
    for i in range(A):
        s = tuple(map(int,readline().split()))
        hoge.append(s)
    syougen.append(hoge)
    
ans = 0
for i in list(itertools.product([0,1],repeat = N)):
    test = True
    for j in range(N):
        if i[j] == 0:
            pass
        else:
            for k,m in syougen[j]:
                if i[k-1] == int(m):
                    continue
                else:
                    test = False
    if test:ans = sum(i)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
table = []#リストをappendして長さの違う2重配列にする
for _ in range(n):
    a = int(input())
    tmp = []
    for _ in range(a):
        person,assessment = map(int,input().split())
        person -=  1
        tmp.append([person,assessment])
    table.append(tmp)

def check(i,n):
    
    for j in range(n):
        if i >> j & 1:
            for person,assessment in table[j]:
                if (i >> person)&1 !=  assessment:
                    return False
    
    return True

ans = 0
for i in range(2**n-1,-1,-1):
    if check(i,n):
        ans = max(ans,bin(i).count("1"))
        

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
table = []
for _ in range(n):
    a = int(input())
    tmp = []
    for _ in range(a):
        person,assessment = map(int,input().split())
        person -=  1
        tmp.append([person,assessment])
    table.append(tmp)

def check(i,n):
    
    for j in range(n):
        if i >> j & 1:
            for person,assessment in table[j]:
                if (i >> person)&1 !=  assessment:
                    return False
    
    return True

ans = 0
for i in range(2**n):
    if check(i,n):
        ans = max(ans,bin(i).count("1"))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

    
def check(i,n):#iはbitでn人それぞれが正直者か嘘つきかのどちらかを表している。
    flg = True
    for j in range(n):
        if i>>j & 1:#右にシフト演算したものの一桁目が1であるとき。iのうち１である桁j=正直者jの意見に関しては吟味する。
            for x,y in table[j]:#ある正直者jの、xに対する評価y
                if (i>>x)&1 != y:#iにおけるxの評価(実際のxの評価)　！＝　jのxに対する評価y
                    flg = False
                    # print(flg)
                    return flg
    # print(flg)
    return flg

# print(table)
ans = 0
for i in range(2**n):   #bit全探索
    if check(i,n):
        ans = max(bin(i).count("1"),ans)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

times = n
table = []
for _ in range(times):
    a = int(input())
    temp = []
    for _ in range(a):
        x , y = map(int,input().split())
        temp.append([x-1,y])
    table.append(temp)  # S += [input()] とも書ける
    
def check(i,n):
    flg = True
    for j in range(n):
        if i>>j & 1:
            for x,y in table[j]:
                if (i>>x)%2 != y:
                    flg = False
                    # print(flg)
                    return flg
    # print(flg)
    return flg

# print(table)
ans = 0
for i in range(2**n):   #bit全探索
    if check(i,n):
        ans = max(bin(i).count("1"),ans)

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=[[[],[]] for _ in range(N)]
for i in range(N):
  a=int(input())
  for j in range(a):
    n,p = map(int, input().split())
    A[i][p].append(n)
def test(i):
  T=[]
  F=[]
  TT=set()
  TF=set()
  for n in range(N):
    if 1 & i>>n:
      T+=A[n][1]
      F+=A[n][0]
      TT.add(n+1)
    else: TF.add(n+1)
  if set(T)<=TT and set(F)<=TF: return len(TT)
  else: return -1
        
s=0
for i in range(2**N):
  s=max(s,test(i))
print(s)

Submission status: Accepted

Solution code:
n = int(input())

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

ans = 0
for i in range(1, 2**n):
   consistent = True
   for j in range(n):
      if (i >> j) & 1 == 0:
         continue

      for x, y in evidences[j]:
         if (i >> x)  & 1 != y:
            consistent = False
            break

      if not consistent:
         break

   if consistent:
      ans = max(ans, bin(i)[2:].count('1'))

print(ans)

Submission status: Accepted

Solution code:
def f(i):
    global m
    if i == n:
        for j in range(n):
            for k in range(n):
                if G[j][k] == 1:
                    if s[j] == 1 and s[k] == 0:
                        return
                elif G[j][k] == 0:
                    if s[j] == 1 and s[k] == 1:
                        return
        if m < sum(s):
            m = sum(s)
        return
    f(i + 1)
    s[i] = 1
    f(i + 1)
    s[i] = 0

n = int(input())
G = [[-1 for _ in range(n)] for _ in range(n)]
for i in range(n):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        G[i][x - 1] = y
s = [0] * n
m = 0
f(0)
print(m)

Submission status: Accepted

Solution code:
n = int(input())

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

def count(x,check):
    l = []
    for j in range(n):
        if ((x >> j) & 1):
            l.append(1)
        else:
            l.append(0)
    chec = True
    for i in range(n):
        if l[i] == 1:
            for k in check[i]:
                if k[1] == 1 and l[k[0]-1] == 0:
                    chec = False
                elif k[1] == 0 and l[k[0]-1] == 1:
                    chec = False
    if chec:
        return l.count(1)
    else:
        return 0

ans = 0
for i in range(2**n):
    ans = max(ans,count(i,check))
print(ans)

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]):
    u,v=map(int,input().split())
    x[i][j]=u-1
    y[i][j]=v
ans=0
for k in range(2**n):
  arr=[0]*n
  cnt=0
  flag=True
  for i in range(n):
    if k>>i&1:
      arr[i]=1
      cnt+=1
  for i in range(n):
    for j in range(a[i]):
      if arr[i]==1:
        if (y[i][j]==1 and arr[x[i][j]]==0) or (y[i][j]==0 and arr[x[i][j]]==1):
          flag=False
  if flag:
    ans=max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
testimony=[[-1]*N for i in range(N)]
count=0
for i in range(N):
    A=int(input())
    for j in range(A):
        x,y=map(int,input().split())
        testimony[i][x-1]=y
for i in range(1<<N):
    honest=[0]*N
    for j in range(N):
        if (i>>j)&1:
            honest[j]=1
    flag=True
    for j in range(N):
        if honest[j]:
            for k in range(N):
                if testimony[j][k]==-1:
                    continue
                if testimony[j][k]!=honest[k]:
                    flag=False
    if flag:
        count=max(count,honest.count(1))
print(count)

Submission status: Accepted

Solution code:
n=int(input())
L=[['nd']*n 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][x-1]=y
r=0
for bit in range(1<<n):
    flag=0
    for k in range(n):
        if bit&(1<<k):
            for l in range(n):
                if l!=k:
                    if L[k][l]==1:
                        if bit&(1<<l):
                            pass
                        else:
                            flag=1
                            break
                    elif L[k][l]==0:
                        if bit&(1<<l):
                            flag=1
                            break
                        else:
                            pass
            
        if flag==1:
            break
        if k==n-1:
            r=max(r,str(bin(bit)).count('1'))
print(r)

Submission status: Accepted

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

def judge(bit):
    for i in range(N):
        if bit&(1<<i)==False: #決め打ち時に不親切の場合
            continue
        for j in range(A[i]): #親切な人の発言検証
            tmpx=pairs[i][j][0]
            tmpy=pairs[i][j][1]
            if tmpy==1  and (bit&(1<<tmpx)==False):
                return False
            if tmpy==0 and (bit&(1<<tmpx)):
                return False
    return True

ans=0
for bit in range((1<<N)):
    if judge(bit):
        count=0
        for i in range(N):
            if (bit&(1<<i)):
               count+=1
        ans=max(ans,count)

print(ans)

Submission status: Accepted

Solution code:
# C
N=int(input())
ans=0
A=[[] for _ in range(N)]
for i in range(N):
    a=int(input())
    for j in range(a):
        A[i].append(tuple(int(i) for i in input().split()))
for i in range(2**N):
    flag=True
    tmp=0
    S=bin(i)[2:][::-1]
    TF=list(S)+['0' for _ in range(N-len(S))]
    # print(TF)
    for j,s in enumerate(list(S)):
        if s=='1':
            tmp+=1
            for x,y in A[j]:
                if TF[x-1]!=str(y):
                    # print(x,y)
                    flag=False
    if flag:
        ans=max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
import sys

import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
"""dd = [(-1, 0), (0, 1), (1, 0), (0, -1)];
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)];
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  # NumberGrid
def grid(n): return [s_list() for _ in range(n)]


def main():
    n = int(input())
    xy = []
    for i in range(n):
        a = int(input())
        y = []
        for j in range(a):
            y.append(list(map(int,input().split())))
        xy.append(y)

    #print(xy)
    #print(xy[0])
    #print(len(xy[0]))

    ans = 0
    for i in range(2**n):   # パターンが2のn乗
        flag = False
        count = 0
        for j in range(n):                # n人

            if i >> j & 1 == 1:                         #はなす人が正直者
                for k in range(len(xy[j])):
                    if (i >> xy[j][k][0]-1 & 1) != xy[j][k][1]:        # 違っていたら
                        flag = True
                        break

                if flag == True:
                    break

                else:
                    count += 1


        if flag == False:
            ans = max(ans, count)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
testimony = [[0] * N for i in range(N)]
A = []

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

testimony = np.array(testimony)

A = np.array(A)
ans = 0

for i in range(2 ** N):
    honesty = [-1] * N
    h = 0
    for j in range(N):
        if (i >> j) & 1:
            honesty[j] = 1
            h += 1
    honesty = np.array(honesty)
    B = np.dot(testimony,honesty) - A
    if any(honesty[j] == 1 and B[j] != 0 for j in range(N)):
        continue

    ans = max(ans, h)

print(ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = []
L = []

for i in range(N):
    a = INT()
    A.append(a)
    l = []
    for j in range(a):
        l.append(LIST())
    L.append(l)

from itertools import product
num = N
bits = product([0, 1], repeat=N)

ans = 0

for x in bits:
    flag = 0# honest
    for j in range(N):
        if x[j] == 1:# honest
            for a, b in L[j]:
                if b != x[a-1]:# lie
                    flag = 1
                    break
        if flag == 1:
            break
    else:
        tmp = sum(x)
        if ans <= tmp:
            ans = tmp
print(ans)



exit()

for l in L:
    info = [False] * 2 ** num
    print(info)
    for y in l:
        a, b = y
        print(a, b)
        for x in bits:
            #print(x)
            if x[a-1] == b:
                info[a-1] = True
                print(info)
        
    print(info)
            
            










#for l in L:
#    x_t = [True] * len(list(bits))
#    for info in l:
#        print(info)
#        print(x_t)
#        i = 0
#        for x in bits:
#            print(x)
#            if x[info[0]-1] != info[1]:
#                x_t[i] = False
#            i += 1
#    print(x_t)
#                
#for x in bits:
#     for l in L:
#         for y in l:
#             print(x)

Submission status: Accepted

Solution code:
n = int(input())
shogen = []
for i in range(n):
    shogen.append({})
for i in range(n):
    for k in range(int(input())):
      x,y = map(int,input().split())
      shogen[i][x] = y 
MaxHonest = 0
for i in range(2**n):
    num = format(i,'b').zfill(n)
    lst = list(map(int,list(num)))
    flag = True
    for k in range(n):
        if lst[k] == 1:
            for l in shogen[k]:
                if shogen[k][l] != lst[l-1]:
                    flag = False
    if flag:
        MaxHonest = max(MaxHonest,sum(lst))
print(MaxHonest)

Submission status: Accepted

Solution code:
n=int(input())
a=[[] for i in range(n)]
for i in range(n):
    b=int(input())
    for j in range(b):
        c,d= map(int, input().split())
        a[i].append((c-1,d))

ans=0
for i in range(2**n):
    flag=True
    count=0
    for j in range(n):
        if (i>>j)&1:
            # １がたったら正直者
            count+=1
            for k in range(len(a[j])):
                if a[j][k][1]==1:
                    if (i>>(a[j][k][0]))&1==1:
                        continue
                    else:
                        flag=False
                        break

                if a[j][k][1]==0:
                    if (i>>(a[j][k][0]))&1!=1:
                        continue
                    else:
                        flag=False
                        break
    if flag:
        ans=max(ans,count)
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    edge = [[-1]*N for i in range(N)]
    for i in range(N):
        A = int(input())
        for a in range(A):
            x, y = (int(i) for i in input().split())
            edge[i][x-1] = y
    # print(*edge, sep="\n")
    ans = 0
    for bit in range(1 << N):
        cur = [0] * N
        flag = True  # 正直者が嘘をついたときだけFalse
        for i in range(N):
            if bit & (1 << i):
                cur[i] = 1
        for i in range(N):
            for j in range(N):
                if edge[i][j] == -1:
                    continue
                elif edge[i][j] == 1 and cur[i] and not(cur[j]):
                    flag = False
                elif edge[i][j] == 0 and cur[i] and cur[j]:
                    flag = False
        if flag:
            ans = max(ans, sum(cur))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def int_to_list(bit, n):
    l = []
    for i in range(n):
     if bit & (1 << i):
         l.append(i)
    return l

def solve():
    N = int(input())
    
    l = [[] for _ in range(N)]
    for i in range(N):
        for _ in range(int(input())):
            p, q = map(int, input().split())
            l[i].append((p-1, q))

    ans = 0
    for i in range(1 << N):
        partial = int_to_list(i, N)

        f = True
        for j in range(N):
            if j not in partial: continue
            for p, q in l[j]:
                if q == 0 and p in partial:
                    f = False
                if q == 1 and not p in partial:
                    f = False
        if f:
            ans = max(ans, len(partial))
            
    return ans

print(solve())

Submission status: Accepted

Solution code:
n = int(input())
witness = [[] for _ in range(n)]
for i in range(n):
    ai = int(input())
    for _ in range(ai):
        x, y = map(int, input().split())
        witness[i].append((x - 1, y))
ans = 0
for i in range(2 ** n):
    f = [False] * n
    flag = False
    for j in range(n):
        if i >> j & 1:
            f[j] = True
    for j in range(n):
        if f[j]:
            for x, y in witness[j]:
                if f[x] and y == 0 or not f[x] and y == 1:
                    flag = True
                    break

        if flag:
            break
        if j == n - 1:
            ans = max(ans, f.count(True))
print(ans)

Submission status: Accepted

Solution code:
import re
n=int(input())
A=[]
for i in range(n):
    B=["."]*n
    for j in range(int(input())):
        x,y=map(int,input().split())
        B[x-1]=str(y)
    A.append("".join(B))

ans=0
for i in range(2**n):
    num=format(i, "b").zfill(n)
    flag,cnt=1,0
    for j,k in enumerate(num):
        result=re.fullmatch(r"".join(A[j]),num)
        if result is not None and k=="1":
            cnt +=1
        elif (result is not None and k=="0") or (result is None and k=="1"):
            flag=0
            break
    if flag:ans=max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
mark=dict()
for i in range(n):
    A=int(input())
    temp_list=[tuple(map(int,input().split())) for i in range(A)]
    mark[i+1]=temp_list
#正直者を仮定する
#正直者の証言を集める（L）
#Lに矛盾がないか調べる
#print(mark)
ans=0
for i in range(2**n):
    honest_remark=[]
    mujun=[]
    cnt=0
    for j in range(n):
        #j桁目が1の時
        if (i>>j)&1:
            cnt+=1
            for k in mark[j+1]:
                honest_remark.append(k)
            mujun.append((j+1,0))
        else:
            mujun.append((j+1,1))

    #if not honest_remark:continue
    #print(honest_remark,mujun)
    honest_remark=set(honest_remark)
    mujun=set(mujun)
    temp=honest_remark&mujun
    if len(temp)==0:
        ans=max(ans,cnt)

print(ans)

Submission status: Accepted

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

ans = 0
for p in range(1<<N):
    h = []
    judge = True
    for i in range(N):
        h.append(p&1)
        p>>=1
    for i in range(N):
        for x, y in xy[i]:
            if h[i] and y != h[x]:
                judge = False
                break
        if not judge: break
    if not judge: continue
    ans = max(ans,sum(h))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
L = [[-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())
        x -= 1
        L[i][x] = y
#print(L)

ans = 0
for i in range(2**n):
    temp = 0
    for j in range(n):
        if (i >> j) & 1:
            temp += 1
    flag = True
    for j in range(n):
        if (i >> j) & 1:
            for k in range(n):
                #print((i >> k) & 0)
                if  L[j][k] == 1 and ((i >> k) & 1) == 0:
                    flag =  False
                elif L[j][k] == 0 and ((i >> k) & 1) != 0:
                    flag = False
                else:
                    pass
    if flag:
        ans = max(ans, temp)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
n = int(input())
a = []
xy = [] #xy[i人目][j個目][0: x, 1: y]
for i in range(n):
    a.append(int(input()))
    xy.append([])
    for _ in range(a[i]):
        xy[i].append([int(i) for i in input().split()])
ans = 0
for i in range(n + 1): #i人の正直者
    b = list(combinations(list(range(n)), i))
    for j in range(len(b)): #組み合わせj
        flag = False
        #print(b[j])
        for k in b[j]: #人k
            for l in range(a[k]): #証言l
                if (xy[k][l][0] - 1 in b[j] and xy[k][l][1] != 1) or ((not xy[k][l][0] - 1 in b[j]) and xy[k][l][1] == 1):
                    flag = True
                    break
                #print(xy[k][l][0], xy[k][l][1])
            if flag:
                break
        if not flag:
            #print('YES', j)
            ans = i
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**N):
    # 1: 正直者
    state = [0] * N
    for j in range(N):
        state[j] = (i >> j) & 1
    
    # 真偽を確かめる
    flag = True
    for j in range(N):
        if state[j] == 0:
            continue
        for x,y in edge[j]:
            if state[x] == y:
                continue
            flag = False
            break
        if not flag:
            break
    if not flag:
        continue

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

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N = int(input())
said = [[-1] * (N+1) for _ in range(N+1)]

for a in range(N):
    K = int(input())
    for _ in range(K):
        x, y = map(int, input().split())
        said[a][x - 1] = y

ans = 0
for cand in product(range(2), repeat=N):
    isOK = True

    for i, c in enumerate(cand):
        if not c:
            continue
        A = said[i]
        for j in range(N):
            if i == j or A[j] == -1:
                continue
            if cand[j] != A[j]:
                isOK = False
                break

    if isOK:
        ans = max(ans, sum(cand))

print(ans)

Submission status: Accepted

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

ans=0
for c in range(2**n):
    b=bin(c)[2:]
    B=[0]*n
    for i in range(len(b)):
        B[-i-1]=int(b[-i-1])
    a=0
    for i in range(n):
        if B[i]==1:
            for j in range(n):
                if B[j]+Y[i][j]==1:
                    a=1
                    break
        if a>0:
            break
    if a==0:
        ans=max(ans,sum(B))
print(ans)