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

lst = []
for i in range(n):
    A = int(input())
    xy = []
    for j in range(A):
        xy.append(list(map(int, input().split())))
    lst.append(xy)


for i in reversed(range(2**n)):
    bi = format(i, 'b').zfill(n)
    flag = True
    for j, data in enumerate(lst):
        if bi[j] == '0':
            continue
        for x, y in data:
            if int(bi[x - 1]) != y:
                flag = False
                break
        
        if not flag:
            break

    if flag:
        break

if flag:
    print(bi.count('1'))
else:
    print(0)

Submission status: Accepted

Solution code:
N = int(input())

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

ans = 0
l = []
for i in range(2**N):
  l.append([(i >> j) & 1 for j in range(N)])
  
for a in l:
  for i in range(N):
    if a[i] == 0:
      continue
    
    for b in v[i]:
      if a[b[0]-1] != b[1]:
        break
    else:
      continue
    break
  else:
    ans = max(ans, sum(a))
      
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

N = int(input())
xyss = [[tuple(map(int, input().split())) for _ in range(int(input()))] for _ in range(N)]

def check(mask):
    m = [None] * N
    for i, xys in enumerate(xyss):
        if i in mask:
            continue
        for x, y in xys:
            x -= 1
            if m[x] != None and m[x] != y:
                # 矛盾が生じている
                return False
            elif  y == 1 and x in mask or y == 0 and x not in mask:
                # 矛盾が生じている
                return False
            else:
                m[x] = y
    return True

for i in range(N + 1):
    for k in combinations(range(N), i):
        mask = set(k)
        if check(mask):
            print(N - i)
            break
    else:
        continue
    break

Submission status: Accepted

Solution code:
N = int(input())
dic = []
ls = [[] for i in range(N)]
for i in range(N):
  a = int(input())
  dic += [a]
  for j in range(a):
    x, y = map(int, input().split())
    ls[i] += [(x-1,y)]
ans = 0
for i in range(2**N):
  inf = []
  m = 0
  for j in range(N):
    if i%2==0:
      inf += [1]
      m += 1
    else:
      inf += [0]
    i >>= 1
  flag = False
  for j in range(N):
    if inf[j]==0:
      continue
    for h in range(dic[j]):
      x, y = ls[j][h]
      if inf[x]!=y:
        flag = True
        break
    if flag:
      break
  else:
    if ans<m:
      ans = m
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

count = 0
for i in range(2 ** N):
    YorN = [0] * N
    for j in range(N):
        if ((i >> j) & 1):
            YorN[N - 1 - j] = 1
        True_people = []
    for j in range(N):
        if YorN[j] == 1:
            True_people.append(answer[j])
    flag = True
    for ans in True_people:
        for k in ans:
            if YorN[k[0]-1] != k[1]:
                flag = False
    if flag == True:
        if count <= sum(YorN):
            count = sum(YorN)

print(count)

Submission status: Accepted

Solution code:
import sys
from collections import deque
readline = sys.stdin.readline


N = int(readline())
A = []
X, Y = [], []
for i in range(N):
    a = int(readline())
    A.append(a)
    x, y = [], []
    for j in range(a):
        _x, _y = map(int, readline().split())
        x.append(_x - 1), y.append(_y)
    X.append(x)
    Y.append(y)

M = 2 ** N
count = 0
for code in range(M - 1, -1, -1):
    contra = False
    for i in range(N):
        if ((code >> i) & 1) == 1:
            x, y = X[i], Y[i]
            for j in range(len(x)):
                if y[j] != ((code >> x[j]) & 1):
                    contra = True
                    break
            if contra:
                break
    if not contra:
        _count = 0
        for i in range(N):
            _count += ((code >> i) & 1)
        count = max(count, _count)

print(count)

Submission status: Accepted

Solution code:
N = int(input())
l = [[] for i in range(N)]
for i in range(N):
    A = int(input())
    l[i] = [0 for j in range(A)]
    for j in range(A):
        x, y = map(int, input().split())
        l[i][j] = [x, y]
ans = 0
for i in range(2**N):
    cnt = 0
    flag = True
    for j in range(N):
        if (i >> j) & 1:
            cnt += 1
            for k in range(len(l[j])):
                if (i >> (l[j][k][0] - 1)) & 1 == l[j][k][1]:
                    pass
                else:
                    flag = False
                    break
    if flag:
        ans = max(ans, cnt)
    cnt = 0
print(ans)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n = onem()


on = []

Ma = 0

for i in range(n):
    kkk = []
    p = onem()
    for j in range(p):
        kkk.append(l())
    on.append(kkk)
for i in range(2**n):
    ppp = '{:015b}'.format(i)
    ppp = list(ppp[15-n:])
    ppp.reverse()
    su = 0
    for r in range(n):
        if ppp[r] == "1":
            su += 1
    f = False
    for j in range(n):
        if ppp[j] == "1":
            for k in range(len(on[j])):
                a,b = on[j][k]
                a -= 1
                if b ^ int(ppp[a]):
                    f = True
                    break
    if not f:
        Ma = max(Ma,su)
print(Ma)

Submission status: Accepted

Solution code:
N = int(input())
t = [[[],[]] for _ in range(N)]
for i in range(N):
	a = int(input())
	for _ in range(a):
		x,y = map(int, input().split())
		t[i][y].append(x)

def Base_10_to_n(X, n):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out

ans = 0

for i in range(2**N):
	c = Base_10_to_n(i,2).rjust(N,"0")
	c = list(map(int, c))
	cnt = [-1] * N
	cond = True
	for j in range(N):
		if c[j] == 1:
			for kind in t[j][1]:
				if cnt[kind-1] == 0:
					cond = False
				cnt[kind-1] = 1
			for unk in t[j][0]:
				if cnt[unk-1] == 1:
					cond = False
				cnt[unk-1] = 0
	if cond:
		for k in range(N):
			if cnt[k] != -1:
				cond = (cnt[k] == c[k])
				if cond == False:
					break
	if cond:
		ans = sum(c)

print(ans)

Submission status: Accepted

Solution code:

def main():
    n = int(input())
    bs = []
    xyss = []
    ans = 0
    for _ in range(n):
        bs.append(int(input()))
        xys = [[int(i) for i in input().split()] for __ in range(bs[-1])]
        xs = set(x-1 for x, y in xys if y == 1)
        ys = set(x-1 for x, y in xys if y == 0)
        # print(list(xs), list(ys))
        xyss.append((xs, ys))
    
    for i in range(2**n):
        # print("=== {0:b} ===".format(i))
        f = True
        for j in range(n):
            if i & (1 << j) > 0:
                xs, ys = xyss[j]
                for x in xs:
                    if (~i) & (1<<x) > 0:
                        f = False
                        # print(x)
                        #break
                for y in ys:
                    if i & (1<<y) > 0:
                        f = False
                        # print(y)
                        #break
            #if not f:
            #    break
        # print("{0}".format(f))
        if f:
            ans = max(ans, sum(1 for c in "{0:b}".format(i) if c == '1'))
    print(ans)

main()

Submission status: Accepted

Solution code:
n = int(input())
ls = list()
for _ in range(n):
    a = int(input())
    ls.append([list(map(int, input().split())) for _ in range(a)])


ans =0
for i in range(2**n):
    flag = True
    for j in range(n):
        if (1<<j) & i:
            for k in ls[j]:
                if bool(((1<<(k[0]-1)) & i)) != bool(k[1]):
                    flag = False

    if flag:
        count = 0
        for j in range(n):
            if (1<<j) & i:
                count += 1
        ans = max(ans, count)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
import functools
import itertools
import math
INF = float('inf')
MOD = 10**9+7

N = int(input())
As = [None] * N
ts = [[] for i in range(N)]
for i in range(N):
    As[i] = int(input())
    for j in range(As[i]):
        x, y = map(int, input().split())
        ts[i].append((x-1, y))
ans = 0
for ps in itertools.product([0, 1], repeat = N):
    # print(ps)
    qs = [None] * N
    flg = 1
    for i in range(N):
        if qs[i] != None and qs[i] != ps[i]:
            flg = 0
            break
        qs[i] = ps[i]
        if ps[i]:
            for j in range(As[i]):
                x, y = ts[i][j]
                if qs[x] == None:
                    qs[x] = y
                elif qs[x] != y:
                    flg = 0
                    break
        if flg == 0:
            break
    if flg:
        ans = max(ans, sum(ps))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xys = []
for i in range(n):
    a = int(input())
    xys.append([list(map(int, input().split())) for _ in range(a)])
ret = 0
for b in range(1 << n):
    ok = True
    c = 0
    for i in range(n):
        if (b >> i) & 1 != 0:
            c += 1
            for x, y in xys[i]:
                if y != (b >> (x - 1)) & 1:
                    ok = False
    if ok:
        ret = max(ret, c)
print(ret)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

# rstrip().decode('utf-8')
# map(int,input().split())


def main():
	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))
	
	ans=0
	
	for i in reversed(range(1<<n)):
		aa=[0]*n
		f=1
		for j in range(n):
			if (i>>j)&1==1:
				aa[j]=1
				
		for k in range(n):
			if aa[k]==1:
				for x,y in li[k]:
					if aa[x]!=y:
						f=0
		if f==1:
			ans=max(ans,str(bin(i)).count("1"))
	
	print(ans)
	
	
	
	
	
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
import math
from itertools import permutations
from itertools import combinations

#input = sys.stdin.readline
sys.setrecursionlimit(10**7)
N = int(input())
xys = []
for _ in range(N):
    A = int(input())
    xy = [list(map(int, input().split())) for _ in range(A)]
    xys.append(xy)


ok = [0] * N
maxv = 0
for i in range(2**N):
    flg = 1
    chk = [i>>n & 1 for n in range(N)]
    for ii, xy in enumerate(xys):
        if chk[ii] == 0:
            continue
        for xyi in xy:
            x = xyi[0]
            y = xyi[1]

            if chk[x-1] != y:
                flg = 0
                break
        if flg == 0:
            break
    if flg == 1:
        sumchk = sum(chk)
        if maxv < sumchk:
            maxv = sumchk

print(maxv)

Submission status: Accepted

Solution code:
import copy
shogen = {}
N = int(input())
for i in range(N):
    Ax = int(input())
    current_shogen = {}
    for j in range(Ax):
        x, y = list(map(int, input().split()))
        current_shogen[x-1] = y
    shogen[i] = current_shogen

def return_total(index, is_liar, hito_list):
    if not is_liar:
        if hito_list[index] is not None and hito_list[index] != 1:
            return 0
        hito_list[index] = 1
        current_shogen = shogen[index]
        for x,y in current_shogen.items():
            if hito_list[x] is not None:
                if hito_list[x] != y:
                    """mujun"""
                    return 0
            else:
                hito_list[x] = y
    else:
        if hito_list[index] is not None and hito_list[index] != 0:
            return 0
        hito_list[index] = 0
    if index == N-1:
        # print(hito_list)
        return sum(hito_list)
    else:
        return max(return_total(index+1, False, copy.deepcopy(hito_list)), return_total(index+1, True, copy.deepcopy(hito_list)))

print(max(return_total(0, False, [None for i in range(N)]), return_total(0, True, [None for i in range(N)])))

Submission status: Accepted

Solution code:
n = int(input())
test_list = [[[int(i) for i in input().split()] for j in range(int(input()))] for k in range(n)]

man_list = [[int(j) for j in bin(i)[2:].zfill(n)] for i in range(2**n)]

ans = 0
bad = 0

for man in man_list:
  for j in range(n):
    if man[j] == 1:
      for k in test_list[j]:
        x = k[0] - 1
        y = k[1]
        if man[x] != y:
          bad = 1
          break
    if bad == 1:
      bad = 0
      break
  else:
    ans = max(ans, sum(man))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
a = [[] for i in range(N)]
ans = 0
for i in range(N):
    times = int(input())
    for j in range(times):
        a[i].append(tuple(map(int, input().split())))

for i in range(2 ** N):
    flag2 = False
    cnt = 0
    flag = [0] * N
    for j in range(N):
        if (i >> j) & 1:
            flag[j] = 1
    for k in range(N):
        if flag[k] == 1:
            for m in range(len(a[k])):
                x, y = a[k][m]
                if flag[x - 1] != y:
                    flag2 = True
                    break
        if flag2:
            break
        if k == N - 1:
            cnt = flag.count(1)

    ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
info = [0]
for _ in range(N):
    A = int(input())
    tmp = []
    for i in range(A):
        x, y = map(int, input().split())
        tmp.append((x, y))
    info.append(tmp)

ans = 0
for i in range(2**N):
    i_bin = list(map(int, bin(i)[2:].zfill(N)))
    ok = 1
    for j in range(1, N+1):
        for x, y in info[j]:
            if i_bin[j-1] == 1:
                if i_bin[x-1] != y:
                    ok = 0
    if ok:
        ans = max(ans, sum(i_bin))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

ans = 0
for b in range(2**N):
    bit = str(bin(b))[2:].zfill(N)
    p = list(map(int, bit))
    for i in range(N):
        if p[i] == 0:
            continue
        for x, y in xy[i]:
            if p[x-1] != y:
                break
        else:
            continue
        break
    else:
        ans = max(ans, p.count(1))

print(ans)

Submission status: Accepted

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

for i in range(n):
    ai = int(input())
    for j in range(ai):
        xij,yij = map(int, input().split( ))
        xij -= 1
        Adj[i][xij] = yij###==ってなんぞ
#print(Adj)
ans = 0

bt = 1<<n

for b in range(bt):#全探索
    flag = True
    tmp = 0
    for i in range(n):
        for j in range(n):
            if Adj[i][j]>=0:
                if ((b>>i) &1) and (((Adj[i][j]==0) and ((b>>j) &1)) or ((Adj[i][j]==1) and (not (b>>j) &1))):#正直者の答えが矛盾,醜いがあとでビット演算子確認
                    flag = False
                    break
        if not flag:
            break
    if flag:
        for t in range(n):
            tmp += (b>>t)&1
            #print("test",b,tmp,flag)
    ans = max(tmp, ans)
    #print(b,ans)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
L=[[]]
for i in range(N):
    A=int(input())
    l=[]
    for j in range(A):
        x,y=map(int,input().split())
        l.append([x,y])
    L.append(l)
#print(L,N)
ans=0
for i in range(2**N):
    X=[0]
    I=i
    for j in range(N):
        X.append(I//(2**(N-1-j)))
        I%=(2**(N-1-j))
    #print(X)
    F=1
    for k in range(1,N+1):
        #print(X,k,N)
        if X[k]==1:
            for z in range(len(L[k])):
                a,b=L[k][z]
                #print(X,k,a,b)
                if X[a]!=b:
                    F=0
                    break
        
    if F==1:
        if ans<sum(X):
            ans=sum(X)
    #print(F,sum(X))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = []
for _ in range(N):
    a = int(input())
    xy = []
    for __ in range(a):
        xy.append(tuple(map(int,input().split())))
    A.append(xy)

ok = []
for i in range(2**N):
    v = [0] * (N+1)
    n = i
    for j in range(1, N+1):
        v[j] = n % 2
        n >>= 1
    for k, xys in enumerate(A):
        if v[k+1] == 1:
            for xy in xys:
                if xy[1] != v[xy[0]]:
                    break
            else:
                continue
            break
    else:
        ok.append(v)

ans = 0
for a in ok:
    ans = max(ans,sum(a))
print(ans)

Submission status: Accepted

Solution code:
def read_valus():
    return map(int, input().split())


def read_list():
    return list(read_valus())


def read_lists(N):
    return [read_list() for n in range(N)]


def f(T, n):
    N = len(T)
    b = format(n, "015b")[::-1][:N]
    
    for n, s in enumerate(b):
        if s == "1":
            for x, y in T[n]:
                if int(b[x]) != y:
                    return False
    return True


def main():
    N = int(input())
    T = [[] for n in range(N)]
    for n in range(N):
        A = int(input())
        for _ in range(A):
            x, y = read_valus()
            x -= 1
            T[n].append((x, y))

    res = 0
    for n in range(2 ** N - 1, -1, -1):
        bit_count = bin(n).count("1")
        if res >= bit_count:
            continue

        if f(T, n):
            res = max(res, bit_count)  

    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
statement = []
for _ in range(N):
    A = int(input())
    temp = {}
    for _ in range(A):
        x, y = map(int, input().split())
        temp[x-1] = y
    statement.append(temp)
ans = 0
for i in range(2**N):
    honest = []
    for j in range(N):
        if (i >> j) & 1: honest.append(j)
    for h in honest:
        contradiction = False
        for j, y in statement[h].items():
            if (y == 1 and j not in honest) or (y == 0 and j in honest): contradiction = True; break
        if contradiction: break
    else:
        ans = max(format(i, 'b').count('1'), ans)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
comments=[]
for i in range(n):
    num=int(input())
    comment=[]
    for j in range(num):
        comment.append(list(map(int,input().split(" "))))
    comments.append(comment)
#print(comments)

ans=0
for i in range(2**n):
    judges=[[] for i in range(n)]
    condition=list(str(format(i,'b').zfill(n)))
    conflict=False
    #print(condition)
    for idx,j in enumerate(condition):
        person_num=idx
        if j=='1':
            for comment in comments[person_num]:
                judges[comment[0]-1].append(comment[1])
    for jdx,judge in enumerate(judges):
        if len(judge)==0:
            pass
        if judge.count(int(condition[jdx])) != len(judge):
            conflict=True
            break
    if not conflict:
        ans=condition.count('1')
    #print(judges)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    ans = 0
    M = [[None] * (N) for _ in range(N)]

    for k, v in A.items():
        for x, y in v:
            M[k-1][x-1] = y

    for i in range(N, 0, -1):
        for m in combinations(range(N), r=i):
            sm = set(m)
            f = True
            for j in m:
                for k, v in enumerate(M[j]):
                    if v == 1 and k not in sm:
                        f = False
                        break
                    elif v == 0 and k in sm:
                        f = False
                        break
                if not f:
                    break

            if f:
                return i
    return 0


def main():
    N = read_int()
    A = {}
    for i in range(1, N+1):
        n = read_int()
        XY = [read_int_n() for _ in range(n)]
        A[i] = XY
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

t = [[] for i in range(n)]
s = [[] for i in range(n)]

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

print(res)

Submission status: Accepted

Solution code:
n = int(input())
a = []
xy = [[] for i in range(n)]
for i in range(n):
    ai = int(input())
    a.append(ai)
    for j in range(ai):
        xyi = list(map(int, input().split()))
        xy[i].append(xyi)
res = 0
for i in range(2 ** n):
    flag = [(1 if i & 2 ** b == 2 ** b else 0) for b in range(n)]
    outs = 0
    for j in range(n):
        if flag[j] == 1:
            for k in range(a[j]):
                x, y = xy[j][k]
                x -= 1
                if flag[x] != y:
                    outs = 1
                    break
    if outs == 0:
        res = max(sum(flag), res)

print(res)

Submission status: Accepted

Solution code:
n = int(input())
matrix = [[-1 for j in range(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())
    matrix[i][x - 1] = y

ans = 0
for i in range(2 ** n):
  str_i = format(i, "0" + str(n) + "b")
  flag = True
  for j in range(n):
    if str_i[j] == "1":
      for k in range(n):
        if matrix[j][k] >= 0 and matrix[j][k] != int(str_i[k]):
          flag = False
          break
  if flag:
    ans = max(ans, str_i.count('1'))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

talk = [[] for i in range(n)]

for i in range(n):
    messages = int(input())
    for _ in range(messages):
        talk[i].append(tuple(map(int, input().split())))

res = 0

for key in range(2 ** n):
    flag = True
    answer = [0 for i in range(n)]
    for i in range(n):
        if key & (1 << i) > 0:
            answer[i] = 1

    for i in range(n):
        if answer[i] == 0:
            continue
        for t in talk[i]:
            person = t[0] - 1
            if t[1] != answer[person]:
                flag = False
                break

    if flag:
        res = max(res, sum(answer))

print(res)

Submission status: Accepted

Solution code:
def honest_or_unkind_2(N: int, testimonies: dict)->int:
    ans = 0
    for i in range(1 << N):
        honest_num = 0
        for j in range(N):
            if i & (1 << j) == 0:
                continue
            honest_num += 1

            # 正直者の場合はその人の証言が全て正しいことをチェックする
            for k, is_honest in testimonies[j]:
                if bool(i & (1 << k)) != is_honest:
                    # 証言の矛盾
                    break
            else:
                # 証言に矛盾なし。次の人をチェック
                continue
            # 証言に矛盾があった
            break
        else:
            # 正直者全員の証言に矛盾なし。この組み合わせは成り立つ。
            ans = max(ans, honest_num)
        # i の表す正直者と嘘つきの組み合わせは証言に矛盾がある

    return ans


if __name__ == "__main__":
    N = int(input())
    testimonies = {}

    for i in range(N):
        A = int(input())
        testimonies[i] = [None] * A
        for a in range(A):
            x, y = map(int, input().split())
            testimonies[i][a] = (x-1, bool(y))

    ans = honest_or_unkind_2(N, testimonies)
    print(ans)

Submission status: Accepted

Solution code:
def is_same_as_ptypes(j, ptypes):
  for x,y in A[j]:
    if ptypes[x] != str(y):
      return False
  return True  
  

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

ans = 0
for i in range(2**N):
  ptypes = bin(i)[2:].zfill(N)
  flag = True
  for j in range(len(ptypes)):
    if ptypes[j] == '0':continue
    if is_same_as_ptypes(j,ptypes) is False:
      flag = False
  if flag is True: ans = max(ptypes.count('1'), ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
XY_LIST = [[list(map(int, input().split())) for _ in range(int(input()))] for _ in range(N)]

def count_honest(i):
    l = [(i>>j)%2 for j in range(N)]
    for j in range(N):
        if (i>>j)%2 == 0:
            continue
        for x, y in XY_LIST[j]:
            x = x-1
            if l[x] == y:
                continue
            return 0
    return sum(l)

max_honest = 0
for i in range(1<<N):
    honest = count_honest(i)
    max_honest = max(max_honest, honest)

print(max_honest)

Submission status: Accepted

Solution code:
N=int(input())
matrix=[[-1 for _ in range(N+1)] for _ in range(N+1)]
for i in range(1, N+1):
    Ai=int(input())
    for j in range(Ai):
        x, y=map(int, input().split())
        matrix[i][x]=y
ans=0
for i in range(1, 2**N):
    honests=[]
    tmp=i
    j=1
    while tmp>0:
        if tmp%2==1:
            honests.append(j)
        tmp=tmp//2
        j+=1
    flag=True
    for j in honests:
        for k in range(1, N+1):
            if (matrix[j][k]==1 and k not in honests) or (matrix[j][k]==0 and k in honests):
                flag=False
                break
        if not flag:
            break
    if flag:
        ans=max(ans, len(honests))
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
H=[[] for i in range(N+1)];H[0]=None # 人iがjを正直者だというようなj
U=[[] for i in range(N+1)];U[0]=None
for i in range(1,N+1):
    A=int(input())
    for j in range(A):
        x,y=map(int,input().split())
        if y==1:
            H[i].append(x)
        elif y==0:
            U[i].append(x)

# print(H)
# print(U)

ans=0
for k in range(1<<N):
    f=[None]
    f.extend([k>>i&1 for i in range(N)])
    # print(f) #DB
    m=sum(f[1:]) # 正直者の人数
    if m<=ans:
        continue
    g=True # フラグ
    for i in range(1,N+1): # 人iについて
        if not g:
            break
        if not f[i]: # 正直者である場合に限る
            continue
        for j in H[i]: # 人iが正直者であると言及する人jについて
            if not f[j]: # jが不親切であったならば
                g=False
                break
        for j in U[i]: # 
            if f[j]:
                g=False
                break
    if g:
        ans=m

print(ans)

Submission status: Accepted

Solution code:
import itertools
n = int(input())

A = [0]*n
x = []
y = []
for i in range(n):
    A[i] = int(input())
    xx = []
    yy = []
    for j in range(A[i]):
        xxx,yyy = map(int,input().split())
        xx.append(xxx)
        yy.append(yyy)
    x.append(xx)
    y.append(yy)


max = 0
B = (0,1)
false = 0
for i in itertools.product(B, repeat=n):
    for j in range(n):
        for k in range(A[j]):
            if i[j] == 1 and (i[x[j][k]-1] != y[j][k]):
                false = 1
                break
        if j == n-1:
            if max <= i.count(1) and not(false):
                max = i.count(1)
                ans = i
    false = 0


print(max)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
xy=[]
for i in range(n):
  a+=[int(input())]
  tmp=[]
  for j in range(a[-1]):
    tmp+=[list(map(int,input().split()))]
  xy+=[tmp]

ans=0
for i in range(2**n):
  flg=list(map(int,bin(i)[2:].zfill(n)))
  s=0
  for j in range(n):
    if flg[j]==1:
      for k in range(a[j]):
        if flg[xy[j][k][0]-1]!=xy[j][k][1]:
          s=1
  if s==0:
    ans=max(ans,sum(flg))
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**n):
  TF = [ 1 & i >> j for j in range(n)]
  bool = True
  for j in range(n):
    if TF[j] == 1:
      for says in people[j]:
        if TF[says[0]-1] == says[1]:
          pass
        else:
          bool = False
          break
    else:
      pass

  if bool:
    ans = max(ans,TF.count(1))

print(ans)