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:
# 正直者；いっていることは正しい, 不親切：いっていることは正しいか正しくない（情報量０）
# A->B->C->Dみたいに正直者同士をつなげることができる．Aを正直者だと仮定するとB,C,Dのすべての人達の言うことが正しくなり，これらの間で矛盾があってはならない
# 正直者が最大となるのは，不親切者が最小となるとき，つまり１５こについてループを回すとまずそう
# 15*14*13 # 分割統治法f(不親切としておくヒトのリスト,正直者だと確定したヒトのリスト,A(新たに正直者だと仮定するひと))=f([],[])+f([],[+A])
N=int(input())
A=[] #(N+1,an,2)
for i in range(N):
    xij=[]
    an = int(input())
    for j in range(an):
        xij.append(list(map(int,input().split())))
    A.append(xij)

#def can_connect(tsuika,unkind,honest): # tsuikaを正直者とした時に既存のリストと矛盾しないか
#    i = tsuika
#    flag = True # なんにもなければTrueでいい
#    for a = A[i-1]:
#        if a[1] == 1: 
#            if a[0] in honest:  # もうすでに正直者で確定していれば探索する必要はない
#                pass
#            elif a[0] in unkind: # 不親切のリストに入っていなければまた調べる必要がある
#                flag = False
#            else:  
#                honest.append(a[0])
#                flag = can_connect(a[0],unkind,honest)
#        else:
#            if a[0] in unkind: # もうすでに不親切でかくていして
#                pass
#            elif a[0] in honest: # 正直者になっていれば
#                flag = False
#            else: 
#                unkind.append(a[0])
#        can_connect(a[0],unkind,honest)
#        if flag == False: # a[i]がおかしな値になっていたら
#            return False
#    if flag == True:
#        return 
#

# 総当りで解ける, bit全探索という N=15として,2^15*(N*N)10^8くらい？
max_num = 0
for i in range(2**N): #  前から順にi番目の要素ビットの値がヒトiが真か偽か
    res=True
    i = str(bin(i))[2:]
    i=i.zfill(N)
    for l,a in enumerate(A):
        flag=bool(int(i[l]))
        if flag: # 本当のことをいっている人なら判定をする
            for k,ai in enumerate(a):
                if not str(ai[1]) == i[ai[0]-1]:
                    res = False
                    break
        if not res: # もうだめなことがわかっていたら
            break
    if res:
        res_list = list(map(int,i))
        max_num = max(max_num, sum(res_list))

print(max_num)

Submission status: Accepted

Solution code:
def solve():
  n = int(input())
  query = [0]*n
  for i in range(n):
    a = int(input())
    tmp = []
    for j in range(a):
       x,y = (int(_) for _ in input().split())
       tmp.append((x-1,y))
    query[i] = tmp

  ans = 0
  for bit in range(1,2**n):
    bitsum = 0
    tmp = [0]*n
    for j in range(n):
      if bit>>j&1 == 1:
        bitsum += 1
        tmp[j] = 1
    ispossible = True
    for j in range(n):
      if tmp[j] == 1:
        check = query[j]
        
        for x,y in check:
          if tmp[x] == y:
            continue
          else:
            ispossible = False
    if ispossible:
      ans = max(ans,bitsum)
  print(ans)
        
        
solve()

Submission status: Accepted

Solution code:
N = int(input())
E = []
for n in range(N):
    A = int(input())
    for _ in range(A):
        x, y = list(map(int, input().split()))
        E.append((n, x - 1, y))
ans = 0
for k in range((1 << N) - 1, -1, -1):
    status = [(k >> i) & 1 for i in range(N)]
    no_paradox = True
    for Xa, Xb, yb in E:
        if (status[Xa] == 1 and status[Xb] != yb):
            no_paradox = False
            break
    if no_paradox:
        ans = max(ans, sum(status))
print(ans)

Submission status: Accepted

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

for i in range(2**N):
  flg = True
  for j in range(len(L)):
    #jの情報は、(hito=x, singi = y=1,0)
    #iの情報は、(singi = (1/0,...,1/0))
    for x,y in L[j]:
      #jさんの情報      
      #i[j] :sinngi　正解
      #y:sinngi　を変換
      if (i >> j) & 1 == 1:
        if i>>(x-1) & 1 !=y:
          flg = False
          break
  if flg:
    cnt = max(cnt,bin(i).count('1'))
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
L = []
for i in range(N):
  A = int(input())
  LA = []
  for j in range(A):
    LA.append(list(map(int,input().split())))
  L.append(LA)
from itertools import product
LL = list(product(range(2), repeat=N))
cnt = 0
for i in LL:
  flg = True
  for j in range(len(L)):
    #jの情報は、(hito=x, singi = y=1,0)
    #iの情報は、(singi = (1/0,...,1/0))
    for x,y in L[j]:
      #jさんの情報      
      #i[j] :sinngi　正解
      #y:sinngi　を変換
      if i[j]==1:
        if i[x-1]!=y:
          flg = False
          break
  if flg:
    cnt = max(cnt,sum(i))
print(cnt)

Submission status: Accepted

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

res = 0
for state in range(2**N):
  for person in range(N):
    if (state >> person) & 1:
      for x, y in graph[person]:
        x -= 1
        if (state >> x & 1) != y:
          break
      else:
        continue
      break
  else:
    res = max(res, bin(state).count('1'))
print(res)

Submission status: Accepted

Solution code:
N = int(input())
A = []
W = [[] for i in range(N)]
for i in range(N):
    a = int(input())
    A.append(a)
    for j in range(a):
        a, b = input().split()
        W[i].append((int(a) - 1, int(b)))

L = 2 ** N
max_cnt = 0
for G in range(L):
    n = 0
    ok = True
    while n < N:
        if G & (1 << n) > 0:
            for i in range(A[n]):
                no = W[n][i][0]
                hl = W[n][i][1]
                c = 1 << no
                if (c & G > 0 and hl == 0) or (c & G == 0 and hl == 1):
                    ok = False
                    break

            if not ok:
                break
        n += 1
    if ok:
        cnt = bin(G)[2:].count('1')
        max_cnt = max(cnt, max_cnt)

print(max_cnt)

Submission status: Accepted

Solution code:
N = int(input())
A = []
W = [[] for i in range(N)]
for i in range(N):
    a = int(input())
    A.append(a)
    for j in range(a):
        a, b = input().split()
        W[i].append((int(a) - 1, int(b)))

L = 2 ** N
max_cnt = 0
for G in range(L):
    b = 1
    n = 0
    ok = True
    while n < N:
        if G & b > 0:
            for i in range(A[n]):
                no = W[n][i][0]
                hl = W[n][i][1]
                c = 1 << no
                if (c & G > 0 and hl == 0) or (c & G == 0 and hl == 1):
                    ok = False
                    break

            if not ok:
                break
        b <<= 1
        n += 1
    if ok:
        cnt = bin(G)[2:].count('1')
        max_cnt = max(cnt, max_cnt)

print(max_cnt)

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

result = 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:
        result = max(result, bin(i)[2:].count('1'))
print(result)

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

result = 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 s[j]:
            if (i >> x) & 1 != y:
                consistent = False
                break
    if consistent:
        result = max(result, bin(i)[2:].count('1'))
print(result)

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

result = 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 s[j]:
            if (i >> x) & 1 != y:
                consistent = False
                break
        if not consistent:
            break
    if consistent:
        result = max(result, bin(i)[2:].count('1'))
print(result)

Submission status: Accepted

Solution code:
N=int(input())
L=2**N
#print(bin(10),bin(10)[1])
#print(N)

data=[]
for i in range(N):
  A=int(input())
  kari=[]
  for j in range(A):
    kari.append(list(map(int,input().split())))
#  print(kari)
  data.append(kari)
                
#print(data)   
answer=0
for i in range(L):
  cond=0
  ansatz=bin(i)
  m=len(ansatz)
  for j in range(m-2):
    if cond==1:
      break
    if int(ansatz[m-j-1])==1:
      for k in range(len(data[j])):
        x=data[j][k][0]
        y=data[j][k][1]
        if x>m-2:
         if y==1:
           cond=1
           break
        else:
          if y != int(ansatz[m-x]):
           cond=1 
           break
  if cond==0:
    sum=0
    for j in range(m-2):
      sum += int(ansatz[m-j-1])
    if sum > answer:
      answer=sum
      
print(answer)

Submission status: Accepted

Solution code:
import sys
bbn=1000000007
	
#+++++

def get_m(says, state, person):
	if person == len(state):
		return sum(state)
	
	if state[person] == 0:
		return get_m(says,state,person+1)
		
	if state[person]==1:
		sss=state[:]
		for x,y in says[person]:
			if sss[x] == -1:
				sss[x]=y
			elif sss[x] != y:
				#mujun
				return 0
			else:
				continue
			
		return get_m(says,sss,person+1)
		
	
	sa=state[:]
	sa[person]=0
	a = get_m(says, sa, person+1)
	
	sb=state[:]
	sb[person]=1
	for x,y in says[person]:
		if sb[x] == -1:
			sb[x]=y
			
		elif sb[x] != y:
			#mujun
			return a
		else:
			continue
		
	b=get_m(says,sb,person+1)
	
	return max(a, b)
		
def main():
	n = int(input())
	says = [[] for _ in range(n)]
	for i in range(n):
		aij=int(input())
		for j in range(aij):
			x,y=map(int, input().split())
			says[i].append([x-1,y])
			
	a=[-1]*n
	
	ret=get_m(says, a,-1)
	print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
import itertools
 
N = int(input())
 
evidence_dit = {}
 
for i in range(N):
    A = int(input())
    x_y = []
    if A == 0:
        evidence_dit[i] = []
    for j in range(A):
        x_y.append(list(map(int,input().split())))
        
        evidence_dit[i] = x_y 

attribute = [0,1]
ans = 0
 
for i in itertools.product(attribute,repeat=N):
    flag = False
    
    for j in range(N):
       
        if i[j] == 1:
            for k in evidence_dit[j]:
                
                
                if i[k[0]-1] != k[1]:
                    flag = True
                    break
            if flag:
                break
 
    if flag == False:
        
        ans = max(ans,sum(i))
             
 
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
 
n = int(input())
r = range(n)
a = [(set(), set()) for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y].add(x - 1)
 
fail = lambda x: not all(a[i][0].isdisjoint(x) and a[i][1] < x for i in x)
 
while all(map(fail, map(set, combinations(r, n)))):
  n -= 1
print(n)

Submission status: Accepted

Solution code:
from itertools import combinations

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

fail = lambda x: not all(x.isdisjoint(a[i][0]) and x.issuperset(a[i][1]) for i in x)

while all(map(fail, map(set, combinations(r, n)))):
  n -= 1
print(n)

Submission status: Accepted

Solution code:
n = int(input())
lst = [[-1 for _ in range(n)] for _ in range(n)]
for _ in range(n):
    c = int(input())
    for c1 in range(c):
        x, y = map(int, input().split())
        x -= 1
        lst[_][x] = y
        
ans = 0
for bit in range(2**n):
    flg = True
    for a in range(n):
        if (bit >> a) & 1:
            for x in range(n):
                if lst[a][x] != -1 and ((bit >> x) & 1) != lst[a][x]:
                  flg = False
                  break
    if flg:
        ans = max(ans, bin(bit).count('1'))
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

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

fail = lambda x: not all(a[i][1] < x and a[i][0].isdisjoint(x) for i in x)

while all(map(fail, map(set, combinations(r, n)))):
  n -= 1
print(n)

Submission status: Accepted

Solution code:
from itertools import combinations

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

fail = lambda x: not all(a[i][0].isdisjoint(x) and a[i][1] < x for i in x)

while all(map(fail, map(set, combinations(r, n)))):
  n -= 1
print(n)

Submission status: Accepted

Solution code:
from itertools import combinations

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

fail = lambda x: not all(a[i][0].isdisjoint(x) and a[i][1].issubset(x) for i in x)

while all(map(fail, combinations(r, n))):
  n -= 1
print(n)

Submission status: Accepted

Solution code:
from itertools import combinations

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

fail = lambda x: not all(a[i][0].isdisjoint(x) and a[i][1] < x for i in x)

while n and all(map(fail, map(set, combinations(r, n)))):
  n -= 1
print(n)

Submission status: Accepted

Solution code:
N = int(input())
xy = []
for i in range(N):
    A = int(input())
    xy.append([])
    for j in range(A):
        xy[i].append(tuple(map(int, input().split())))
 
ans = 0
 
for i in range(2 ** N):
    h = [0] * N
 
    for j in range(N):
        if (i >> j) & 1:
            h[j] = 1
    
    flag = False
    for i in range(N):
        if h[i] == 1:
            for x, y in xy[i]:
                if h[x-1] != y:
                    flag = True
                    break
            if flag:
                break
    
    if not flag:
        ans = max(ans, sum(h))
 
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

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

fail = lambda x: (not all(a[i][0].isdisjoint(x) and a[i][1] < x for i in x))

while n and all(map(fail, map(set, combinations(r, n)))):
  n -= 1
print(n)

Submission status: Accepted

Solution code:
n = int(input())
lst = [[-1 for _ in range(n)] for _ in range(n)]
for _ in range(n):
    c = int(input())
    for c1 in range(c):
        x, y = map(int, input().split())
        x -= 1
        lst[_][x] = y
        
ans = 0
for bit in range(2**n):
    flg = True
    for a in range(n):
        if (bit >> a) & 1:
            for x in range(n):
                if lst[a][x] != -1:
                    if ((bit >> x) & 1) != lst[a][x]:
                        flg = False
                        break
    if flg:
        ans = max(ans, bin(bit).count('1'))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
peaple = []
for i in range(n):
  a = int(input())
  tests = []
  for j in range(a):
    x, y = input().split()
    tests.append((int(x) - 1, y))
  peaple.append(tests)
  
maximum = 0
for h_bit in range(1, 1<<n):
  h_str = format(h_bit, '0{}b'.format(n))
  flag = False
  for i in range(n):
    if h_str[i] == '1':
      for test in peaple[i]:
        if h_str[test[0]] != test[1]:
          flag = True
          break
    if flag:
      break
  if not flag:
    maximum = max(maximum, h_str.count('1'))
print(maximum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
n = int(input())
lst = []
for _ in range(n):
    a = int(sys.stdin.readline())
    lst.append([[int(i) for i in sys.stdin.readline().split()] for _ in range(a)])
m = 0
for i in range(2 ** n):
    a = True
    d = 0
    for j in range(n):
        if i >> j & 1:
            d += 1
            for x, y in lst[j]:
                if (i >> (x - 1) & 1) != y:
                    a = False
                    break
    if a:
        m = max(m, d)
print(m)

Submission status: Accepted

Solution code:
n=int(input())
a=[[list(map(int,input().split()))for _ in'_'*int(input())]for _ in'_'*n]
m=0
for i in range(2**n):
  *s,=map(int,bin(i)[2:].zfill(n))
  f=1
  for j,t in enumerate(a):
    if s[~j]:
      for x,y in t:f&=s[-x]==y
  m=max(m,sum(s)*f)
print(m)

Submission status: Accepted

Solution code:
n = int(input())
lst = []
for _ in range(n):
    a = int(input())
    lst.append([[int(i) for i in input().split()] for _ in range(a)])
m = 0
for i in range(2 ** n):
    a = True
    for j in range(n):
        if i >> j & 1:
            for x, y in lst[j]:
                if (i >> (x - 1) & 1) != y:
                    a = False
                    break
    if a:
        m = max(m, sum(map(int, bin(i)[2:])))
print(m)

Submission status: Accepted

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

N=int(input())
L=[[] for _ in range(N)]
for i in range(N):
    A=int(input())
    for _ in range(A):
        x,y=map(int,input().split())
        x-=1
        L[i].append((x,y))
ans=0
for i in range(2**N):
    H=[]
    for j in range(N):
        if (i>>j)&1 ==1:
            H.append(j)
    S=[-1]*N
    for j in H:
        for x,y in L[j]:
            if S[x]==-1 or S[x]==y:S[x]=y
            else:break
        else:continue
        break
    else:
        for k,x in enumerate(S):
            if (x==0 and k in H)or (x==1 and k not in H):break
        else:
            ans=max(ans,len(H))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=[]
for i in range(n):
  n1=int(input())
  l1=[]
  for j in range(n1):
    a,b=map(int,input().split())
    l1.append([a,b])
  l.append(l1)
num=2**n
bitlist=[]
for i in range(1,1+num):
  num1=num-i
  b1=[]
  while num1!=0 or len(b1)<n:
    b1.append(num1%2)
    num1//=2
  bitlist.append(b1)
#各b1の要素が1の時その人は正直者
ans=0
for i in range(num):
  b=bitlist[i]
  bool1=True
  for j in range(n):
    if not bool1:
      pass
    elif b[j]==0:
      pass
    else:#jは正直者だから発言は全て本当 整合性必要
      for k in l[j]:
        n1=k[0]
        n2=k[1]
        if b[n1-1]!=n2:
          bool1=False
  count=0
  if bool1:
    for j in b:
      if j==1:
        count+=1
    if count>ans:
      ans=count
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
l = []
for _ in range(N):
    A = int(input())
    ll = []
    for _ in range(A):
        x, y = map(int, input().split())
        ll.append([x, y])
    l.append(ll)

b = 2 ** N
ans = 0

for i in range(2 ** N):
    flag = True
    for j in range(N):
        if i >> j & 1 == 1:
            for x, y in l[j]:
                if y == 1 and i >> (x - 1) & 1 != 1 or y == 0 and i >> (x - 1) & 1 == 1:
                    flag = False
    if flag:
        ans = max(ans, bin(i).count('1'))
        # print(bin(i))

print(ans)

Submission status: Accepted

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


def main():
    N = int(input())
    A = [[set(), set()] for _ in range(N)]
    for i in range(N):
        m = int(input())
        for j in range(m):
            x, y = map(int, input().split())
            A[i][y].add(x)

    ans = 0
    for i in range(1 << N):
        h, u = set(), set()
        for j in range(N):
            if (i >> j) & 1:
                h.add(j+1)
                h |= A[j][1]
                u |= A[j][0]
            else:
                u.add(j+1)
        if not (h & u):
            ans = max(ans, len(h))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    N = int(input())
    A = [[set(), set()] for _ in range(N)]
    for i in range(N):
        m = int(input())
        for j in range(m):
            x, y = map(int, input().split())
            A[i][y].add(x)

    ans = 0
    for i in range(1 << N):
        h, u = set(), set()
        for j in range(N):
            if (i >> j) & 1:
                h.add(j+1)
                h |= A[j][1]
                u |= A[j][0]
            else:
                u.add(j+1)
        if not (h & u):
            ans = max(ans, bin(i).count("1"))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [0] * N
XY = [0] * N
for i in range(N):
  A[i] = int(input())
  XY[i] = [list(map(int, input().split())) for _ in range(A[i])]

count = lambda x: sum([(x>>i)&1 for i in range(15)])
ans = 0
for i in range(1<<N):
  ok = True
  for j in range(N):
    if (i>>j)&1 == 0: continue
    for k in range(A[j]):
      if (i>>(XY[j][k][0]-1)&1)^XY[j][k][1]:
        ok = False
        break
  ans = max(ans, count(i)) if ok else ans
print(ans)

Submission status: Accepted

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


#1：正直者
#0：嘘つき
#最大数
ans=0
#全探索
for i in range(1<<n):
    #全候補
    c_list=[]
    for j in range(n):
        c_list.append((i>>j)%2)

    check=1
    for j in range(n):
        #1ならばTrue
        if c_list[j]:
            
            for z in arr[j]:
                
                if c_list[z[0]]!=z[1]:
                    check=0
    if check:
        ans=max(ans,sum(c_list))
print(ans)

Submission status: Accepted

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


def main():
    N = int(input())
    A = [[set(), set()] for _ in range(N)]
    for i in range(N):
        m = int(input())
        for j in range(m):
            x, y = map(int, input().split())
            A[i][y].add(x)

    ans = 0
    for i in range(1 << N):
        h, u = set(), set()
        for j in range(N):
            if (i >> j) & 1:
                h.add(j+1)
            else:
                u.add(j+1)
        for k in list(h):
            h |= A[k-1][1]
            u |= A[k-1][0]
        if not (h & u):
            ans = max(ans, bin(i).count("1"))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def counter(x):
        if x == 0:
                return 0
        return counter(x >> 1) + (x & 1)

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

ans = 0 
for bits in range(1, 1 << N): 
        flag = 1 
        for i in range(N):
                if not bits & (1 << i): 
                        continue
                for j in range(A[i]):
                        if (bits >> (x[i][j][0] - 1) & 1) ^ x[i][j][1]:
                                flag = 0 
        if flag:
                ans = max(ans, counter(bits))
print(ans)

Submission status: Accepted

Solution code:
def cnt_honest(bit):
    for i in range(n):
        if bit[i] == "1":
            for x, y in hf[i]:
                if bit[x - 1] != str(y):
                    return 0
    return bit.count("1")


n = int(input())
hf = [[] for i in range(n)]

for i in range(n):
    for j in range(int(input())):
        hf[i].append(list(map(int, input().split())))

ans = 0
for i in range(2 ** n):
    ans = max(ans, cnt_honest(format(i, "b").zfill(n)))
print(ans)

Submission status: Accepted

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


def main():
    N = int(input())
    A = [[set(), set()] for _ in range(N)]
    for i in range(N):
        m = int(input())
        for j in range(m):
            x, y = map(int, input().split())
            A[i][y].add(x)

    ans = 0
    for i in range(1 << N):
        h = set()
        u = set()
        for j in range(N):
            if (i >> j) & 1:
                h.add(j+1)
            else:
                u.add(j+1)
        b = True
        for k in list(h):
            k -= 1
            h |= A[k][1]
            u |= A[k][0]
            if h & u:
                b = False
                break
        if b:
            ans = max(ans, bin(i).count("1"))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    N = int(input())
    A = [[set(), set()] for _ in range(N)]
    for i in range(N):
        m = int(input())
        for j in range(m):
            x, y = map(int, input().split())
            A[i][y].add(x)

    ans = 0
    for i in range(1 << N):
        h = set()
        u = set()
        for j in range(N):
            if (i >> j) & 1:
                h.add(j+1)
            else:
                u.add(j+1)
        b = True
        for k in list(h):
            k -= 1
            h |= A[k][1]
            u |= A[k][0]
            if h & u:
                b = False
        if b:
            ans = max(ans, bin(i).count("1"))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, os
import collections

class Dectation:
  def __init__(self, target, is_honest):
    super().__init__()
    self.target = target
    self.is_honest = is_honest

def solve(input_stream):
  number_of_people = read_int(input_stream)
  dectation_list = [[] for i in range(number_of_people)]

  for people_index in range(number_of_people):
    number_of_dectation = read_int(input_stream)
    for dectate_index in range(number_of_dectation):
      target_people, is_honest = read_ints(input_stream)
      dectation_list[people_index].append(Dectation(target_people, is_honest))
  ans = 0
  for bits in range(1, 1 << number_of_people):
    ok = True
    for index in range(number_of_people):
      if not ok:
        continue
      if ( ( (bits >> index) & 1 ) & 1) == 0:
        continue
      for dectation in dectation_list[index]:
        if (( bits >> (dectation.target - 1) ) & 1 ) ^ dectation.is_honest:
          ok = False
          break
    if ok:
      ans = max(ans, count(bits, 0))
  return [str(ans)]

def count(bits, ans):
  if bits == 0:
    return ans
  ans += bits & 1
  return count(bits >> 1, ans)

def read_ints(input_stream):
  return  map(int, input_stream.readline().strip().split())

def read_int(input_stream):
  return int(input_stream.readline().strip())

if __name__ == "__main__":
    outputs = solve(sys.stdin)
    for line in outputs:
      print(line)

Submission status: Accepted

Solution code:
def counter(x):
    if x==0:
        return 0
    return counter(x >> 1) + (x & 1)
N=int(input())
A=[[]]
X=[[]]
Y=[[]]
for i in range(1,N+1):
    a=int(input())
    A.append(a)
    x=[[]]
    y=[[]]
    for j in range(a):
        b=list(map(int,input().split()))
        x.append(b[0])
        y.append(b[1])
    X.append(x)
    Y.append(y)
ans=0
for bits in range(1 << N):
    #print(bin(bits))
    ok=True
    for i in range(1,N+1):
        if not (bits & (1<<i-1)):
            continue
        for j in range(1,A[i]+1):
            if(((bits >> (X[i][j]-1)) & 1) ^ Y[i][j]):
                ok = False
        
    if ok:
#        print(ok,bin(bits))
        ans = max(ans, counter(bits))
print(ans)