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 = []
x = [[] for _ in range(n)]

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

# print(x)
ans = 0
for i in range(1<<n):
    
    cnt = bin(i).count("1")
    if ans > cnt:
        continue
    flag = True
    for j in range(n):
        # if i==3:
        #     print(i,j,i>>j&1,cnt)
        if i>>j & 1:
            # True if 1
            # if i==3:
                # print(i,j)
            for t in x[j]:
                # 証言:testimony
                # if i == 3:
                    # print(i,t[0]-1, i>>t[0]-1, t[1])
                if (i>>(t[0]-1) &1 ) != t[1]:
                    flag = False
                    break
    # if flag == False:
    #     break
    if flag == True:
        # print(i) # 0 000
        ans = cnt

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

a = []
x = [[] for _ in range(n)]

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

# print(x)
ans = 0
for i in range(1<<n):
    
    cnt = bin(i).count("1")
    if ans > cnt:
        continue
    flag = True
    for j in range(n):
        # if i==3:
        #     print(i,j,i>>j&1,cnt)
        if i>>j & 1:
            # True if 1
            # if i==3:
                # print(i,j)
            for t in x[j]:
                # 証言:testimony
                # if i == 3:
                    # print(i,t[0]-1, i>>t[0]-1, t[1])
                if (i>>(t[0]-1) &1 ) != t[1]:
                    flag = False
                        # break
            # if flag == False:
            #     break
    # if flag == False:
    #     break
    if flag == True:
        # print(i) # 0 000
        ans = cnt

print(ans)

Submission status: Accepted

Solution code:
import sys

def read():
    return sys.stdin.readline().rstrip()

def main():
    n = int(read())
    xy = [list() for _ in range(n)]
    for i in range(n):
        a = int(read())
        xyi = [tuple() for _ in range(a)]
        for j in range(a):
            xyi[j] = tuple(map(int, read().split()))
        xy[i] = xyi
    p = sorted([[int(j) for j in "{:0{}b}".format(i, n)] for i in range(2**n)], key=sum, reverse=True)
    for pi in p:
        flag = True
        for a in range(n):
            if not flag:
                break
            if pi[a] == 0:
                continue
            for x, y in xy[a]:
                if y ^ pi[x - 1]:
                    flag = False
                    break
        if flag:
            print(sum(pi))
            break

if __name__ == '__main__':
    main()

Submission status: Accepted

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


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(input())
    X = [[-1 for j in range(N)] for i in range(N)]
    for i in range(N):
        a = int(input())
        for j in range(a):
            xx, yy = map(int, input().split())
            X[i][xx-1] = yy
    mx = 0
    for i in range(1<<N):
        flag = True
        for j in range(N):
            if (i>>j) & 1 == 1:
                for k in range(N):
                    if (i>>k)&1 != X[j][k] and X[j][k] != -1:
                        flag = False
                        break
        if flag == True:
            mx = max(mx, bin(i)[2:].count('1'))
    print(mx)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
xy = []
for i in range(n):
    a = int(input())
    xy.append([])
    for j in range(a):
        tmp = list(map(int, input().split()))
        xy[i].append(tmp)
# bit全探索
# 範囲
ans = 0
s = 0
for i in range(2 ** n):
    # 判断用のリストを準備
    judge = []
    # 探索
    for j in range(n):
        if (i >> j) & 1:
            judge.append(1)
        else:
            judge.append(0)

    count = 0
    tmp_j = True
    for l in range(n):
        count = 1
        if judge[l] == 1:
            for a in range(len(xy[l])):
                if judge[xy[l][a][0] - 1] == xy[l][a][1]:
                    count = 1
                if judge[xy[l][a][0] - 1] != xy[l][a][1]:
                    count = 0
                    tmp_j = False
                    break
        if tmp_j == False:
            break

    if count == 1:
        s = sum(judge)
    if ans <= s:
        ans = s
print(ans)

Submission status: Accepted

Solution code:
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 = 0
    for j in range(N):
        if (i>>j)&1 == 1:
            for x, y in XY[j]:
                if (i>>x)&1 != y:
                    flag = 1
                    break
    if flag == 0:
        ans = max(ans, bin(i)[2:].count('1'))

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a = [[] for _ in range(n)]
for i in range(n):
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        a[i].append((x - 1, y))
ans=0
for i in range(2**n):
    count=0
    flag=True
    for j in range(n):
        if (i>>j)&1:
            for k in range(len(a[j])):
                if a[j][k][1]!=(i>>a[j][k][0])&1:
                    flag=False
                    break
            count+=1
    if flag:
        ans=max(count,ans)

print(ans)

Submission status: Accepted

Solution code:
#abc 147 c bit全探索の問題 binはstr型を返す
#bin()をつかわなくてもそのままbit演算すればよし i>>k k桁右シフト
def ninzu(x):
    bit=bin(x)
    return bit.count("1")

n=int(input())
xy=[]
an=[]
ans=0
for i in range(n):
    z=[]
    a=int(input())
    an.append(a)
    for j in range(a):
        x,y=map(int,input().split())
        z.append([x,y])
    xy.append(z)
for i in range(2**n):
    flag=True
    for j in range(n):
        if (i>>j)&1:
            for x1,y1 in xy[j]:
                if y1==1:
                    if ((i>>x1-1)&1)!=1:
                        flag=False
                else:
                    if ((i>>x1-1)&1)!=0:
                        flag=False
            if flag==False:
                break
        if flag==False:
            break
    if flag:
        ans=max(ans,ninzu(i))
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(1 << n):
    s = '{:0>{n}b}'.format(i, n=n)
    d = list(s[::-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, d.count('1'))

print(ans)

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict
    d = defaultdict(list)
    n = int(input())
    for i in range(n):
        a = int(input())
        for _ in range(a):
            x, y = [int(x) for x in input().split()]
            d[i].append((x-1, y))

    ans = 0
    from itertools import product
    for ts in product([0, 1], repeat=n):
        if all([ts[x] == y for i in range(n) for x, y in d[i] if ts[i]==1]):
            ans = max(ans, sum(ts))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product
n = int(input())
xy = []

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


ans = 0

for ts in product([0,1], repeat=n):
    for i, t in enumerate(ts):
        if t:
            if not all(ts[q-1] == z for q,z in xy[i]):
                break
    else:
        ans = max(ans, sum(ts))

print(ans)

Submission status: Accepted

Solution code:
import itertools
 
n=int(input())
H,L=[[] for _ in range(n)],[[] for _ in range(n)]
 
for i in range(n):
  m=int(input())
  for j in range(m):
    x,y=map(int,input().split())
    if y==1:
      H[i].append(x-1)
    else:
      L[i].append(x-1)
      
N=set(range(n))
ans=0
for num in range(1,n+1):
  pat=set(itertools.combinations(range(n),num))
  for h in pat:
      h=set(h)
      num=len(h)
      nh=N-h
      t=sum([H[i] for i in h],[])
      l=sum([L[i] for i in h],[])
      if set(t)<=h and set(l)<=nh:
        ans=max(ans,num)
print(ans)

Submission status: Accepted

Solution code:
import itertools
 
n=int(input())
H,L=[[] for _ in range(n)],[[] for _ in range(n)]
 
for i in range(n):
  m=int(input())
  for j in range(m):
    x,y=map(int,input().split())
    if y==1:
      H[i].append(x-1)
    else:
      L[i].append(x-1)
      
N=set(range(n))
ans=0
pat=set()
for num in range(1,n+1):
  pat=pat|set(itertools.combinations(range(n),num))
for h in pat:
    h=set(h)
    num=len(h)
    nh=N-h
    t=sum([H[i] for i in h],[])
    l=sum([L[i] for i in h],[])
    if set(t)<=h and set(l)<=nh:
      ans=max(ans,num)
print(ans)

Submission status: Accepted

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

import numpy
from itertools import combinations

def main():
  n = int(input())
  remarks = numpy.full((n, n), -1)
  As = []
  to_binary = lambda x , y=[]: y if x==0 else to_binary(x>>1, [x%2]) + y
  for i in range(n):
    As.append(int(input()))
    for _ in range(As[-1]):
      x, y = map(int, input().strip().split())
      remarks[i, x-1] = y
  ids = list(range(n))
  for i in range(2**n-1, -1, -1):
    ihonests = to_binary(i)
    ihonests = numpy.array([0] * (n-len(ihonests)) + ihonests)
    remarks_of_honests = remarks[ihonests==1, :]
    if all(map(lambda remark: all((remark == ihonests) + (remark == -1)), remarks_of_honests)):
      print(sum(ihonests))
      return

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
n = int(input())
g = [[-1 for j in range(n)] for i 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
        
ans = 0
for s in range(2**n):
    ok = True
    k = 0
    for i in range(n):
        if (s >> i & 1) == 1:
            k += 1
            for j in range(n):
                if g[i][j] == -1:
                    continue
                if (s >> j & 1) != g[i][j]:
                    ok = False
    if ok:
        ans = max(ans, k)

print(ans)

Submission status: Accepted

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

x = [[x1-1 for x1 in x0] for x0 in x]

def check_honest():
    flag = True
    for ii in range(len(honest)):
        if int(honest[ii]) == 1:
            for jj in range(A[ii]):
                if int(honest[x[ii][jj]]) != y[ii][jj]:
                    flag = False
    return flag

max_sum = 0
for i in range(2**N):
    honest = bin(2**N | i)[3:]
    if check_honest():
        max_sum = max(max_sum, sum(list(map(int, list(honest)))))

print(max_sum)

Submission status: Accepted

Solution code:
n = int(input())

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


def is_honest(people, number):
    return (bool)(people & (1 << number))


ans = 0
for assumption in range(2 ** n):
    contradicted = False
    for i in range(n):
        if not is_honest(assumption, i):
            continue
        for x, y in testimonies[i]:
            if is_honest(assumption, x) ^ y:
                contradicted = True
    if not contradicted:
        ans = max(ans, bin(assumption).count('1'))

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = int(1e09) + 7
INF = int(1e15)


def calc(N):
    return sum(int(x) for x in str(N))


def main():
    # sys.stdin = open("sample.txt")
    N = Scanner.int()
    G = [[-1 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        a = Scanner.int()
        for _ in range(a):
            x, y = Scanner.map_int()
            x -= 1
            G[i][x] = y
    ans = 0
    for i in range(1 << N):
        V = [0 for _ in range(N)]
        for j in range(N):
            if (i >> j) & 1:
                V[j] = 1
        isOk = True
        for j in range(N):
            for k in range(N):
                if V[k] == 0:
                    continue
                if G[k][j] == -1:
                    continue
                if G[k][j] != V[j]:
                    isOk = False
        if isOk:
            ans = max(ans, V.count(1))
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
tableh = [0 for _ in range(n)]
tableuk = [0 for _ in range(n)]

for i in range(n):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        x -= 1
        if y == 1:
            tableh[i] |= 1 << x
        else:
            tableuk[i] |= 1 << x

ans = 0


def popcount(n):
    return bin(n)[2:].count('1')


def same(x, y):
    return popcount(x) + popcount(y) == popcount(x ^ y)

for i in range(1 << n):
    honest = 0
    unkind = 0
    for j in range(n):
        if (i >> j) & 1 != 0:  # P_j is honest
            honest |= tableh[j]
            unkind |= tableuk[j]
    if ((~i & honest) == 0) and ((i & unkind) == 0):
        ans = max(ans, popcount(i))

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
def main():
	N=int(input())
	shougen = [[] for n in range(N)]
	for n in range(N):
		A=int(input())
		for a in range(A):
			x,y = map(int, input().split())
			shougen[n].append([x,y])
	
	OKlis = []
	for n in range(2**N):
		isOK = True
		bit = '{n:0{width}b}'.format(n=n,width=N)
		for i,v in enumerate(bit):
			if v == '0':
				continue
			for x,y in shougen[i]:
				if bit[x-1] != str(y):
					isOK = False
					break
			if isOK == False:
				break
		if isOK:
			OKlis.append(bit)
	OKlis = [ i.count('1') for i in OKlis]
	print(max(OKlis))

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from sys import stdin
n = int(stdin.readline().rstrip())
li = []
for i in range(n):
    s = int(stdin.readline().rstrip())
    lin = [list(map(int,stdin.readline().rstrip().split())) for _ in range(s)]
    li.append(lin)
ma = 0
def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)
for i in range(2**n):
    keta = Base_10_to_n(i,2).zfill(n)
    point = keta.count("1")
    flag = False
    for j,k in enumerate(keta):
        if k == "1":
            for l in li[j]:
                if keta[l[0]-1] != str(l[1]):
                    flag = True
    if flag:
        continue
    ma = max(ma,point)
print(ma)

Submission status: Accepted

Solution code:
N = int(input())
li = [[] for i in range(N)]
for i in range(N):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        li[i].append((x-1, y))
num = (1<<N)-1
ans = 0
for i in range((1<<N)-1):
    ok = True
    for j in range(N):
        if (num>>j)&1:
            for xy in li[j]:
                (x, y) = xy
                if not (num>>x) & 1 == y:
                    ok = False
    if ok:
        cnt = 0
        for i in range(N):
            if num>>i&1:
                cnt += 1
        ans = max(ans, cnt)
    num -= 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

N = int(input())

#2^N通りの全仮説　e.g. [[0,0],[0,1],[1,0],[1,1]]　0:不親切 1:正直
L = list(product([0,1], repeat=N))

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

ans= 0

for l in L:
  F  = True
  for i,katei in enumerate(l):
    if katei == 1:#正直者のみを確認(正直者でなければ証言は矛盾しても良い)
      for j in T[i]:#正直者のiさんの証言T[i]とlの整合性を確認
        #j[0]-1 :対象　j[1]: 証言内容　
        #l[j[0]-1]:　j[0]-1さんのが正直かの仮定
        if l[j[0]-1] != j[1]:#仮定lと証言が矛盾(iさんは正直者ではなかった)
          F = False
  if F:
    ans = max(ans,sum(l))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

N = int(input())

L = list(product([0,1], repeat=N))

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

ans= 0

for l in L:
  F  = True
  for i,k in enumerate(l):
    if k == 1:
      for j in T[i]:
        if l[j[0]-1] != j[1]:
          F = False
  if F:
    ans = max(ans,sum(l))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
# 人の証言の組み合わせ
say=[]
for _ in range(n):
    a = int(input())
    a_say=[]
    for _ in range(a):
        a_say.append(list(map(int,input().split())))
    say.append(a_say)

ans = 0
for hyp in range(2**n):
    # 正直者=1
    s_hyp = format(hyp,'b').zfill(n)
    
    conflict = False
    for i,say_list in enumerate(say):
        if s_hyp[i] == '0':
            continue

        for a,b in say_list:
            if s_hyp[a-1] != str(b):
                conflict = True 
                exit
        if conflict:
            exit
        
    if conflict:
        continue
    ans=max(ans,s_hyp.count('1'))

print(ans)

Submission status: Accepted

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

N = INT()

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

maxv = 0
for i in range(2**N):
	s = "{:0" + str(N) + "b}"
	F = [int(i) for i in s.format(i)]
	flag = 0
	for j in range(N):
		if F[j] == 1:
			for k in range(len(a[j])):
				if a[j][k][1] == 1:
				 	if F[a[j][k][0] - 1]*a[j][k][1] == 0:
				 		flag = 1
					 	break
				else:
					if F[a[j][k][0] - 1] == 0:
						continue
					if F[a[j][k][0] - 1]*a[j][k][1] == 0:
						flag = 1
						break

	if flag == 1:
		continue

	wa = sum(F)
	if maxv < wa:
		maxv = wa

print(maxv)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

a_list = []
xy_list = []
ans = 0

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

for i in range(2**n):
    h = [0]*n
    flag = True
    for j in range(n):
        if (i >> j) & 1:
            h[j] = 1
    for j in range(n):
        if h[j] == 1:
            a = a_list[j]
            xy = xy_list[j]
            for k in range(a):
                l = xy[k]
                x = l[0]
                y = l[1]
                if h[x-1] != y:
                    flag = False
                    break
            if not flag:
                break
    if flag:
        ans = max(sum(h), ans)

print(ans)

Submission status: Accepted

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

cnt = 0
for i in range(2**n):
    x = i
    for j in range(n):
        a[j] = x % 2
        x = x // 2

    for j in range(n):
        for k in range(j,n):
            if a[j] == 1 and a[k] == 1:
                if m[j][k] == 0 or m[k][j] == 0:
                    break
            elif a[j] == 1 and a[k] == 0:
                if m[j][k] == 1:
                    break
            elif a[j] == 0 and a[k] == 1:
                if m[k][j] == 1:
                    break
        else:
            continue
        break
    else:
        if a.count(1) > cnt:
            cnt = a.count(1)
print (cnt)

Submission status: Accepted

Solution code:
n=int(input())
al=[]
info=[]
for i in range(n):
    a=int(input())
    al.append(a)
    temp=[]
    for j in range(a):
        x,y=map(int,input().split())
        temp.append([x,y])
    info.append(temp)

ans=0

for i in range(2**n):
    n_honest=0
    dic={}
    flag=True
    for j in range(n):
        if ((i >> j) & 1):
            n_honest+=1
            dic[j]=1
        else:
            dic[j]=0
    for j in range(n):
        if ((i >> j) & 1):
            temp=info[j]
            a=al[j]
            for k in range(a):
                l=temp[k]
                x=l[0]
                y=l[1]
                if dic[x-1]!=y:
                    flag=False
                    break
        if not flag:
            break
    if flag:
        ans=max(n_honest,ans)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [[-1for _ in range(n)]for _ in range(n)]

ans = 0

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

for i in range(2**n):
  #bit全探索
  #d:正直者と仮定してる人
  d = []
  p = len(bin(i))
  q = bin(i)
  for j in range(p-2):
    q = bin(i>>j)
    if int(q[len(q)-1]) == 1:
      d.append(j)
  
  res = True
  for j in d:
    for k in range(n):
      #jさんがkさんの事を正直者だと思ってた時
      if a[j][k] == 1:
        if k not in d:
          res = False
      #jさんがkさんのことを不親切な人と思ってた時
      elif a[j][k] == 0:
        if k in d:
          res = False
  if res:
    ans = max(ans,len(d))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [[-1for _ in range(n)]for _ in range(n)]

ans = 0

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

for i in range(2**n):
  #bit全探索
  #d:正直者と仮定してる人
  d = []
  p = len(bin(i))
  q = bin(i)
  for j in range(p-2):
    q = bin(i>>j)
    if int(q[len(q)-1]) == 1:
      d.append(j)
  #print(d)

  res = True
  for j in d:
    for k in range(n):
      #jさんがkさんの事を正直者だと思ってた時
      if a[j][k] == 1:
        if k not in d:
          res = False
      #jさんがkさんのことを不親切な人と思ってた時
      elif a[j][k] == 0:
        if k in d:
          res = False
  if res:
    ans = max(ans,len(d))

print(ans)

Submission status: Accepted

Solution code:
import sys

n = int(input())

# user_dic = {user_id:{user_id: user_condition}}
user_dic = {}
for i in range(1, n+1):
    words_num = int(input())
    words_dic = {}
    for t in range(words_num):
        word = list(map(int, input().split()))
        words_dic[word[0]] = word[1]
    user_dic[i] = words_dic

max_num = 0

# 全てのパターンについて探索
for i in range(2 ** n):
    # 矛盾があるならFalseにする
    flag = True

    # パターンを2進数化
    bin_num = str(bin(i))[2:].zfill(n)

    # ユーザーごとの証言を考える
    for member, words in user_dic.items():
        # 正しい人か否か判断

        # 正しいなら
        if int(bin_num[-1 * member]) == 1:
            # 証言1つずつに対して考える
            for idx, cond in words.items():
                if  int(bin_num[-1 * idx]) != cond:
                    flag = False
                    break
 

        # 正しくないなら
        # else:
        #     # 証言1つずつに対して考える
        #     for idx, cond in words.items():
        #         if  int(bin_num[-1 * idx]) == cond:
        #             flag = False 
    
    # 矛盾がない場合
    if flag:
        # 正直者をカウントし, 結果を比較し更新
        true_num = bin(i).count("1")
        if max_num < true_num:
            max_num = true_num

print(max_num)

sys.exit()

Submission status: Accepted

Solution code:
from itertools import product

N = int(input())
c = product(range(2), repeat=N)
d = [[] for _ in range(N)]

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


ans = 0
for l in c:
    is_conflict = False
    for i, j in enumerate(l):
        if j==0:continue
        for x, y in d[i]:
            if l[x-1]!=y:
                is_conflict = True
                break
        if is_conflict == True:
            break
    else:
        ans = max(ans, sum(l))

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

N = int(input())
c = product(range(2), repeat=N)
d = [[] for _ in range(N)]

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


ans = 0
for l in c:
    o = [None]*N
    is_conflict = False
    for i, j in enumerate(l):
        if j==0:continue
        for x, y in d[i]:
            if (o[x-1]!=None and o[x-1]!=y) or l[x-1]!=y:
                is_conflict = True
                break
            o[x-1] = y
        if is_conflict == True:
            break
    else:
        ans = max(ans, sum(l))

print(ans)

Submission status: Accepted

Solution code:
from math import log10
from math import ceil


N =  int(input())
all_evidences = []
for i in range(N):
    oneman_evidences = []
    A = int(input())
    for _ in range(A):
        x,y= list(map(int,input().split(" ")))
        x-=1
        oneman_evidences.append((x,y) )
    all_evidences.append(oneman_evidences)


ans = 0
for all_people_states in range(2 ** N ): # 1→ honest 0→ not
    temp = 0
    people_is_honest = []
    for j in range(N):
        is_honest = (all_people_states >> j) & 1
        temp += is_honest
        people_is_honest.append(is_honest)
    people_is_honest.reverse()
    HONEST_FLAG = True
    for human_num,human in enumerate(people_is_honest):
        if human == 1:
            human_evidence= all_evidences[human_num]
            for evidence in human_evidence:
                state_human,is_honest = evidence
                if people_is_honest[state_human] != is_honest:
                    HONEST_FLAG = False
    if HONEST_FLAG:
        ans = max(ans,temp)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = []
x = []
y = []

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

n = 2**N
ans = 0
for i in range(n):
    flag = True
    honest_person = [0]*N
    #j番目の人が正直者であるかどうか
    for j in range(N):
        honest_person[j] = i>>j & 1
    for j in range(N):
        #j番目の人が正直者ならば...
        if(honest_person[j]):
            for k in range(A[j]):
                #j番目の人の証言は矛盾がないはず
                if honest_person[x[j][k]-1] != y[j][k]:
                    flag = False
    if flag:
        ans = max(ans,honest_person.count(1))
print(ans)