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())
testimony = []  # 各iの証言

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


best = 0  # 正直者の最大人数

# 「<<」はビット演算を表す
# 1 << 1 ならば　0001 → 0010　なので 2
# 1 << 2 ならば　0001 → 0100　なので 4
# 1 << 3 ならば　0001 → 1000　なので 8
# 3人なら 000, 001, 010, 011, 100, 101, 110, 111 の8通りが考えられる
# 1の部分が正直者、0が不親切者、111だと3人とも正直者
# honest=0 ならば 正直者は0、honest=1　ならば　正直者は1(index=0)
# honest=2 ならば 正直者は2(index=1)、honest=3　ならば　正直者は1と2(011 2進数)
for honest in range(1 << n):  # 正直者をあらかじめ仮定して破綻を確認する
    for i in range(n):  # 証言者i
        if not (honest >> i) & 1:  # iが不親切な人なら証言を聞かない
            continue # 「continue」はfor文スキップを表す
        for j, t in testimony[i]:  # iによるjに対する証言t
            if (honest >> j) & 1 != t:  # jに対する仮定とtが食い違えば破綻
                break # for文を抜ける
        else:
            continue
        break
    else:  # 全ての正直者に話を聞いて破綻が無ければ更新
        best = max(best, bin(honest).count('1'))

print(best)

Submission status: Accepted

Solution code:
N=int(input())
L=[[] for i in range(N)]
for i in range(N):
  M=int(input())
  L[i]=[list(map(int,input().split())) for j in range(M)]
#print(L)

L_2=[[i,None] for i in range(N)]
L_3=[0 for i in range(N)]
ans=0
for k in range(2**N):
	L_3=[0 for i in range(N)]
	Y_N=True
	count=0
	for a in range(N):
		if ((k >> a) & 1):  # 正直者のリストを作る
			L_3[a]=1
	for a in range(N):  # このループが一番のポイント
		if ((k >> a) & 1):  # 正直者のリスト
			count += 1
			for b in range(len(L[a])):
				if L_3[a] == 0: #もし正直者じゃないとされてたら
					Y_N=False #破綻
				person = L[a][b][0]-1
				if L_3[person]==1-L[a][b][1]: #すでに言われてることと矛盾
					Y_N=False #破綻
				L_3[person]=L[a][b][1] #証言の内容で人となりをアップデート
				#print(L_3,a,b)
	#print(L_3,count,Y_N)
	if Y_N:
		ans = max(ans, count)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
testimony = []  # 各iの証言
for i in range(n):
    t = []
    for _ in range(int(input())):
        x, y = map(int, input().split())
        t.append((x - 1, y))
    testimony.append(t)
best = 0  # 正直者の最大人数
for honest in range(1 << n):  # 正直者をあらかじめ仮定して破綻を確認する
    for i in range(n):  # 証言者i
        if not (honest >> i) & 1:  # iが不親切な人なら証言を聞かない
            continue
        for j, t in testimony[i]:  # iによるjに対する証言t
            if (honest >> j) & 1 != t:  # jに対する仮定とtが食い違えば破綻
                break
        else:
            continue
        break
    else:  # 全ての正直者に話を聞いて破綻が無ければ更新
        best = max(best, bin(honest).count('1'))
print(best)

Submission status: Accepted

Solution code:
n = int(input())
testimony = []  # 各iの証言
for i in range(n):
    t = []
    for _ in range(int(input())):
        x, y = map(int, input().split())
        t.append((x - 1, y))
    testimony.append(t)
best = 0  # 正直者の最大人数
for honest in range(1 << n):  # 正直者をあらかじめ仮定して破綻を確認する
    tmp = 0
    for i in range(n):  # 証言者i
        if not (honest >> i) & 1:  # iが不親切な人なら証言を聞かない
            continue
        tmp += 1
        for j, t in testimony[i]:  # iによるjに対する証言t
            if (honest >> j) & 1 ^ t:  # jに対する仮定とtが食い違えば破綻
                break
        else:
            continue
        break
    else:  # 全ての正直者に話を聞いて破綻が無ければ更新
        best = max(best, tmp)
print(best)

Submission status: Accepted

Solution code:
n = int(input())
testimony = []  # 各iの証言
for i in range(n):
    t = []
    for _ in range(int(input())):
        x, y = map(int, input().split())
        t.append((x - 1, y))
    testimony.append(t)
best = 0  # 正直者の最大人数
for honest in range(1 << n):  # 正直者をあらかじめ仮定して破綻を確認する
    for i in range(n):  # 証言者i
        if not (honest >> i) & 1:  # iが不親切な人なら証言を聞かない
            continue
        for j, t in testimony[i]:  # iによるjに対する証言t
            if (honest >> j) & 1 ^ t:  # jに対する仮定とtが食い違えば破綻
                break
        else:
            continue
        break
    else:  # 全ての正直者に話を聞いて破綻が無ければ更新
        best = max(best, bin(honest).count('1'))
print(best)

Submission status: Accepted

Solution code:
def spline(func_=int, iter_=None):
    if iter_ is None:
        iter_ = input().split()
    return map(func_, iter_)


n = int(input())
testimony = [[] for _ in range(n)]  # 各iの証言
for i in range(n):
    for _ in range(int(input())):
        x, y = spline()
        x -= 1
        testimony[i].append((x, y))
best = 0  # 正直者の最大人数
for honest in range(1 << n):  # 正直者をあらかじめ仮定して破綻を確認する
    for i in range(n):  # 証言者i
        if not (honest >> i) & 1:  # iが不親切な人なら証言を聞かない
            continue
        for j, t in testimony[i]:  # iによるjに対する証言t
            if (honest >> j) & 1 ^ t:  # jに対する仮定とtが食い違えば破綻
                break
        else:
            continue
        break
    else:  # 全ての正直者に話を聞いて破綻が無ければ更新
        best = max(best, bin(honest).count('1'))
print(best)

Submission status: Accepted

Solution code:
n = int(input())

#証言のリスト
l = [[-1] * n for i in range(n)]

for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        #証言の記録
        l[i][x-1] = y

ans = 0

for i in range(2**n):
    Val = True
    for j in range(n):
        if (i >> j & 1) == 1:   #iにおけるjビット目が、1であれば
            for k in range(n):
                if l[j][k] == -1: continue
                if (i >> k & 1) != l[j][k]: Val = False
    if Val:
        res = 0
        num = i
        while num > 0:
            res += num % 2
            num //= 2
            ans = max(ans, res)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
rel=[{'good':set(),'bad':set()} for _ 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:
      rel[i]['good'].add(x-1)
    else:
      rel[i]['bad'].add(x-1)
ans=0
for i in range(2**n):
  true=set()
  c=0
  for j in range(n):
    if (i>>j) & 1==1:
      true.add(j)
  for j in true:
    if len(rel[j]['bad']&true)>0 or not rel[j]['good']<=true:
      break
    c+=1
  if c==len(true):
    ans=max(ans,c)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
xy = [0] * N
ans = 0
for i in range(N):
    a = int(input())
    xy[i] = [list(map(int, input().split())) for _ in range(a)]
is_honest = [False for i in range(N)]
for i in range(2 ** (N)):
    for j in range(N):
        if i >> j & 1:
            is_honest[j] = True
        else:
            is_honest[j] = False
    broke = False
    for j in range(N):
        if is_honest[j]:
            for k in xy[j]:
                if is_honest[k[0]-1] != bool(k[1]):
                    broke = True
                    break
            if broke:
                break
    if broke == False:
        ans = max(ans, is_honest.count(True))
print(ans)

Submission status: Accepted

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


ans = 0
for bit in range(1<<n):
  #2のn乗まで捜査
	ok = True
	is_honest = [(bit>>i) & 1 for i in range(n)]
	#bitをiずらして末尾が1のひとは正直
	for i in range(n):
		if not is_honest[i]:
			continue
		for x, y in words[i]:
			if is_honest[x] != y:
				ok = False
	if ok:
		ans = max(ans, sum(is_honest))
print(ans)

Submission status: Accepted

Solution code:
# N = 3
# ARR = [[[2],[3]], [[3],[1]], [[1],[2]]]

# N = 2
# ARR = [[[], [2]], [[], [1]]]


# N = 3
# ARR = [[[2],[]],[[1],[]],[[],[2]]]

N = int(input())
ARR = []
for i in range(N):
    A = int(input())
    X = []
    Y = []
    for j in range(A):
        x, t = map(int, input().split())
        if t == 1:
            X.append(x)
        else:
            Y.append(x)
    ARR.append([X,Y])

def calculate(n,arr):
    result = []
    for i in range(2**n):
        cases = []
        goods = set()
        suspicious = set()
        for j in range(n):
            cases.append(i >> j & 1)
            if i >> j & 1:
                goods.add(j)
            else:
                suspicious.add(j)
        res = judge(arr,cases,goods,suspicious)
        if res:
            result.append(len(goods))

    if len(result) == 0:
        print(0)
    else:
        print(max(result))

def judge(arr,cases,goods,suspicious):
        tempGoods = set()
        tempSuspicious = set()

        if sum(cases) == 0:
            return False

        for index,ca in enumerate(cases):
            if ca == 1:
                for g in arr[index][0]:
                    tempGoods.add(g - 1)
                for s in arr[index][1]:
                    tempSuspicious.add(s - 1)

        if len(list(tempGoods & suspicious)) > 0:
            return False

        if len(list(tempSuspicious & goods)) > 0:
            return False

        return True


calculate(N,ARR)

Submission status: Accepted

Solution code:
def abc147_c():
  # クエリ受け取り
  n = int(input())
  query = []
  for _ in range(n):
    a = int(input())
    q = [tuple(map(int, input().split())) for _ in range(a)]
    query.append(q)

  # bit全探索
  ans = 0
  for mask in range(1, 2**n):
    # i番目がTrueの人が正直者と仮定する
    honest = [False] * n
    for i in range(n):
      if (mask >> i) & 1: honest[i] = True

    # Trueの人の証言だけ拾って、矛盾があるかないか
    succ = True
    for i, q in enumerate(query):
      if (mask >> i) & 1:
        for x, y in q:
          if y == 1 and (not honest[x-1]):
            succ = False
            break
          elif y == 0 and honest[x-1]:
            succ = False
            break
      if not succ: break

    # 成り立っていれば、答えを更新
    if succ:
      ans = max(ans, honest.count(True))
  print(ans)

abc147_c()

Submission status: Accepted

Solution code:
from itertools import product
# 微妙にわからない
N = int(input())
B = list(product([1, 0], repeat=N))
L = []
for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split())
        L.append([x, y, i+1])
ans = 0
for b in B:
    for l in L:
        if b[l[2]-1] == 1 and l[1] != b[l[0]-1]:
            break
    else:
        if ans < b.count(1):
            ans = b.count(1)
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 j in range(a)])
 
ans=0
for i in range(2**n):
  honest=[]
  for j in range(n):
    if (i>>j)&1:
      honest.append(1)
    else:
      honest.append(0)
  p=0
  for j,k in enumerate(honest):
    if k==1:
      r=0
      for l in xy[j]:
        if honest[l[0]-1]!=l[1]:
          r=1
          break    
      if r==0:
        p=p+1
  if p==sum(honest) and p>ans:
    ans=p
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 j in range(a)])

ans=[]
for i in range(2**n):
  honest=[]
  for j in range(n):
    if (i>>j)&1:
      honest.append(1)
    else:
      honest.append(0)
  p=0
  q=0
  for j,k in enumerate(honest):
    if k==1:
      q=q+1
      r=0
      for l in xy[j]:
        if honest[l[0]-1]==l[1]:
          r=r+1
      if r==len(xy[j]):
        p=p+1
  if p==q:
    ans.append(p)
print(max(ans))

Submission status: Accepted

Solution code:
n=int(input())
xy=[]
ans=0
for i in range(n):
  a=int(input())
  xy.append([list(map(int,input().split())) for _ in range(a)])
for i in range(2**n):
  cnt=[]
  k=0
  for j in range(n):
    if (i >> j) & 1:
      cnt.append(1)
    else:
      cnt.append(0)
  for p,j in enumerate(cnt):
    e=0
    if j==0:
      for o in xy[p]:
        if cnt[o[0]-1]==o[1]:
          break
        e+=1
      if e==len(xy[p]):
        k+=1
      else:
        k=0
        break
  if ans < k:
    ans=k
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

#
# N = 3
# ARR = [[[2],[3]], [[3],[1]], [[1],[2]]]

# N = 3
# ARR = [[[2],[]],[[1],[]],[[],[2]]]


# N = 2
# ARR = [[[], [2]], [[], [1]]]

N = int(input())
ARR = []

for i in range(N):
    A = int(input())
    X = []
    Y = []
    for j in range(A):
        x, t = map(int, input().split())
        if t == 1:
            X.append(x)
        else:
            Y.append(x)
    ARR.append([X,Y])

def calculate(n, arr):
    result = []
    for i in range(2 ** n):
        q = deque()
        possibilities = []
        teacherGoods = set()
        teacherBads = set()
        for j in range(n):
            identity = (i >> j & 1) == 1
            if identity:
                q.append(j)
                possibilities.append(identity)
                teacherGoods.add(j + 1)
            else:
                teacherBads.add(j + 1)
            # j 第几号人
            # i >> j & 1 第几号人是好人还是坏人
        res = judge(q, arr, teacherGoods, teacherBads)
        if res == True:
            result.append(sum(possibilities))

    print(max(result))


def judge(possibilities, arr, teacherGoods, teacherBads):
    goodMans = set()
    badMans = set()
    trueStatus = {}
    result = True
    while len(possibilities) > 0:

        trueIndex = possibilities.popleft()
        if trueStatus.get(trueIndex) == True:
            continue
        trueStatus.__setitem__(trueIndex, True)
        for g in arr[trueIndex][0]:
            goodMans.add(g)
            possibilities.append(g - 1)
        for b in arr[trueIndex][1]:
            badMans.add(b)

        if len(list(goodMans & teacherBads)) > 0:
            result = False
            break

        if len(list(badMans & teacherGoods)) > 0:
            result = False
            break
    return result


calculate(N, ARR)

Submission status: Accepted

Solution code:
N = int(input())
A_list = []
XY_list = []
for i in range(N):
    a = int(input())
    xy = [list(map(int, input().split())) for i in range(a)]
    A_list.append(a)
    XY_list.append(xy)

result = 0

for i in range(2 ** N):
    bit = str(format(i, 'b')).zfill(N)
    flag = 0
    for j in range(N):
        if bit[j] == '1':
            for k in range(A_list[j]):
                man = XY_list[j][k][0]
                judge = XY_list[j][k][1]
                if int(bit[man - 1]) != judge:
                    flag = 1
                    break
        if flag == 1:
            break
    if flag == 0:
        tmp = 0
        for j in range(N):
            tmp += int(bit[j])
        if tmp > result:
            result = tmp
print(result)

Submission status: Accepted

Solution code:
N=int(input())
A=[]
g=[[-1]*(N) for i in range(N)]#g[i][j]はi番目からのj番目に対する証言

for i in range(N):
    a=int(input())
    A.append(a)
    for j in range(a):
        x,y=map(int,input().split())
        x-=1
        g[i][x]=y
"""
num=[]
for i in range(2 **N):
  chars = list(f"{i:0{N}b}")
  chars=list(map(int,chars))
  num.append(chars)
"""
num=[]
for i in range(2**N):
    x=[]
    for j in range(N):
        if i>>j & 1:
            x.append(1)
        else:
            x.append(0)
    num.append(x)

ans=[]
for x in num:
    ok = True
    for k in range(N):#k番目の人
        if x[k]:
            for j in range(N):
                if g[k][j]==-1:
                    continue
                elif g[k][j]!=x[j]:
                    ok=False
    if ok:
        ans.append(x.count(1))
print(max(ans))

Submission status: Accepted

Solution code:
N=int(input())
A=[]
g=[[-1]*(N) for i in range(N)]#g[i][j]はi番目からのj番目に対する証言

for i in range(N):
    a=int(input())
    A.append(a)
    for j in range(a):
        x,y=map(int,input().split())
        x-=1
        g[i][x]=y
""""
num=[]
for i in range(2 **N):
  chars = list(f"{i:0{N}b}")
  chars=list(map(int,chars))
  num.append(chars)
"""
num=[]
for i in range(2**N):
    x=[]
    for j in range(N):
        if i>>j & 1:
            x.append(1)
        else:
            x.append(0)
    num.append(x)

ans=[]
for x in num:
    ok = True
    for k in range(N):#k番目の人
        if x[k]:
            for j in range(N):
                if g[k][j]==-1:
                    continue
                elif g[k][j]!=x[j]:
                    ok=False
    if ok:
        ans.append(x.count(1))
print(max(ans))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
import numpy as np

N = int(readline())
info = []
for i in range(N):
    A = int(readline())
    for _ in range(A):
        x,y = map(int,readline().split())
        info.append((i,x-1,y))
        
A = np.array(list(itertools.product([0,1],repeat=N)),np.bool)
for i,x,y in info:
    bl = (~A[:,i]) | (A[:,x] == bool(y))
    A = A[bl]

answer = A.sum(axis = 1).max()
print(answer)

Submission status: Accepted

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

ans=0
for i in range(2**n):
    s=bin(i)[2:].zfill(n)  #[2:]はbinにしたときに最初につく0bをのぞく．zfillはn桁の0埋め．
    f=True
    for j,k in enumerate(lst):  #kは証言，jはそれを言った人の番号
        for x,y in k:   #xは人番号なので，インデックスのときは-1する
            if s[x-1]!=str(y) and s[j]=='1':    #仮定したsとjの人の証言を照らし合わせる．jの人が不親切という仮定の時，証言に意味はないので無視．
                f=False                                #仮定と証言で一致しないものがあったとき，flagを消す．
    if f:                                   #全ての証言と照らし合わせてもokのとき，仮定したsは正しい．
        ans=max(ans,s.count('1'))   #ansを更新
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = [[]]*n

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

mx = 0
for i in range(2**n):
  B = [[0]*3 for _ in range(n)]
  uso = 0
  men_cnt = 0
  for j in range(n):
    if i>>j&1:
      men_cnt += 1
      B[j][2] = 1
      for k in range(len(A[j])):
        x, y = A[j][k]
        B[x][y] = 1
  for i in range(n):
    if (B[i][0] and B[i][1]) or (B[i][1] and B[i][2]==0) or (B[i][0] and B[i][2]):
      uso = 1
  if uso==0:
    if men_cnt>mx:
      mx = men_cnt
   
      
print(mx)

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


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


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

    res = 0
    for i in range(2 ** N):
        honest = []
        for j in range(N):
            if ((i >> j) & 1):
                honest.append(j)
        if len(honest) == 0:
            continue
        feasible = True
        for h in honest:
            for x, y in all_A[h]:
                if y == 1:
                    if x not in honest:
                        feasible = False
                        break
                else:
                    if x in honest:
                        feasible = False
                        break
        if feasible:
            res = max(res, len(honest))

    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
for i in range(1<<n):
  honests = [0 for _ in range(n)]
  for j in range(n):
    if (i>>j) &1:
      honests[j] = 1 
  ok = True
  for j in range(n):
    if honests[j]:
      for k in range(n):
        if g[j][k] == -1: continue
        if g[j][k] != honests[k]: ok = False
  if ok:
    ans = max(ans, honests.count(1))

print(ans)

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

ans = 0
for i in range(2**n):
    flag = True
    for j in range(n):
        if i >> j & 1 == 1:  # 右からｊ番目の人は正直もの
            for k in range(a[j]):
                if xy[j][k][1] == 1 and i >> (xy[j][k][0]-1) & 1 != 1:
                    flag = False
                    break
                elif xy[j][k][1] == 0 and i >> (xy[j][k][0]-1) & 1 != 0:
                    flag = False
                    break
            else:
                continue
            break
    if flag and ans < str(bin(i)).count("1"):
        ans = str(bin(i)).count("1")


print(ans)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

def solve():
    N = int(input())
    testimonies = []
    for n in range(N):
        A = int(input())
        XYs = []
        for a in range(A):
            x, y = list(map(int, input().split()))
            XYs.append((x-1, y))
        testimonies.append(XYs)

    # bit全探索する
    ans = 0
    for bit in range(2**N):
        is_continue = False
        total = 0
        # bitが1のやつが正直者と仮定する
        for i in range(N):
            if bit>>i&1:
                # iが正直者の場合
                total += 1
                for testimony in testimonies[i]:
                    x, y = testimony
                    if bit>>x&1 != y:
                        # 矛盾発生
                        is_continue = True
                        break
            if is_continue:
                break
        if is_continue:
            continue
        ans = max(ans, total)

    print(ans)



if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def check(pat):
  honest = [1 if i in pat else 0 for i in range(N)]
  li = pat + [i for i in range(N) if i not in pat]
    
  for i in li:
    if honest[i] == 1:
      n = len(x[i])
      for j in range(n):
        y = x[i][j]
        if honest[y[0]] != y[1]:
          return -1
    
  return len(pat)

N = int(input())
x = [0]*N
for i in range(N):
  A = int(input())
  x[i] = []
  for j in range(A):
    y1,y2 = map(int,input().split())
    x[i].append((y1-1,y2))
max_honest = 0
l = [i for i in range(N)]
n = len(l)
for i in range(2 ** N):
    pat = []
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            pat.append(l[j])  # フラグが立っていたら bag に果物を詰める
    max_honest = max(max_honest,check(pat))
print(max_honest)

Submission status: Accepted

Solution code:
n = int(input())
testimony = [[] for _ in range(n)]

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

honest = 0
for i in range(1, 2**n):
    flag = 0
    for j in range(n):
        if (i>>j)&1 == 1:
            for x, y in testimony[j]:
                if (i>>x)&1 != y:
                    flag = 1
    if flag == 0:
        honest = max(honest, bin(i)[2:].count('1'))

print(honest)

Submission status: Accepted

Solution code:
import itertools

n = int(input())
xy_map = []
for i in range(n):
    xy_map.append([9]*n)

for i in range(n):
    ai = int(input())
    for j in range(ai):
        xj, yj = [int(_) for _ in input().split()]
        xy_map[i][xj-1] = yj

def judge_ox(i, j, set_01):
    if set_01[j] == '1':
        if 0 in [xy_map[i][j], xy_map[j][i]]:
            return False
        else:
            return True
    else:
        if xy_map[i][j] in [0, 9]:
            return True
        else:
            return False

res = 0
for set_01 in itertools.product('01', repeat=n):
    flag = 1
    for i in range(n):
        if set_01[i] != '1':
            continue
        for j in range(n):
            if i == j:
                continue
            if not judge_ox(i, j, set_01):
                flag = 0
                break
    if flag:
        res = max(res, sum([int(x) for x in set_01]))
print(res)

Submission status: Accepted

Solution code:
import itertools

n = int(input())
an_list = []
xy_list = []
for _ in range(n):
  an_list.append(int(input()))
  xy_list.append([list(map(int, input().split())) for __ in range(an_list[-1])])

#print(an_list)
#print(xy_list)

max_honest = 0

h_or_u = [0, 1]
for i in itertools.product(h_or_u, repeat=n):
  honest = []
  unkind = []
  for j in range(n):
    if i[j] == 1:
      honest.append(j+1)
      for k in range(an_list[j]):
        if xy_list[j][k][1] == 1:
          honest.append(xy_list[j][k][0])
        else:
          unkind.append(xy_list[j][k][0])
    else:
      unkind.append(j+1)
  b = 0
  for l in set(honest):
    if l in unkind:
      b += 1
  if b == 0:
    max_honest = i.count(1)
  #print(honest)
  #print(unkind)
    

print(max_honest)

Submission status: Accepted

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

ans=0
for i in range(2**n):
    flag=0
    for j in range(n):
        if (i>>j)&1:
            for k in l[j]:
                if (i>>k[0])&1 != k[1]:
                    
                    flag=1
                    break
    if flag==0:
        ans=max(ans,bin(i)[2:].count("1"))

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.buffer.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
from collections import deque
N = int(input())
xy = [[0,0]]*N
A = [0]*N
for i in range(N):
    a = int(input())
    A[i] = a
    xy[i] = [list(map(int,input().split())) for _ in range(a)]
Max = 0
for i in range(2**N):
    bitlist = deque()
    for j in range(N):
        if ((i >> j) & 1): #2進数表示のj桁目(0桁目から数える)が1かどうか
            bitlist.appendleft(1)
        else:
          	bitlist.appendleft(0)
    bitlist = list(bitlist)
    cc = 0
    for i in range(N):
        c = 0
        if bitlist[i] == 1:
            for k in range(A[i]):
                if xy[i][k][1] == 1:
                    if bitlist[xy[i][k][0]-1] == 0:
                        c = 1
                        break
                else:
                    if bitlist[xy[i][k][0]-1] == 1:
                        c = 1
                        break
        if c == 1:
            cc = 1
            break
    if cc == 0:
        ss = 0
        for jj in bitlist:
            ss += jj
        Max = max(Max,ss)
print(Max)

Submission status: Accepted

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

def main():
    n = int(input())
    #ビット全探索を行う
    import itertools
    li = list(itertools.product([0, 1], repeat=n)) # ０が不親切もの、１が親切もの

    #dd[i][x] = y:人iが人xをy（０なら不親切,１なら親切)だと思っていることを収納
    NIL = -1
    dd = [[NIL]*n for _ in range(n)]
    for i in range(n):
        a = int(input())
        for j in range(a):
            x, y = map(int, input().split())
            x = x-1
            dd[i][x] = y


    from copy import deepcopy
    max_sum = 0 #親切者の数の最大値
    for i in li: # i には親切者のタプルが入っている
        ppp = 0
        for ggg in i:
            ppp += ggg
        if ppp <= max_sum:
            continue
        sum_ = 0
        flag = True
        for k in range(len(i)): #全員の証言が矛盾しないかを考える
            if i[k] == 0: # 不親切ものの場合
                continue
            else: #以下k人目の証言を考える
                sum_ += 1
                for l in range(n):
                    if dd[k][l] != NIL and dd[k][l] != i[l]: #証言と一致していない場合
                        flag = False
                        break
        if flag:
            max_sum = max(max_sum, sum_)

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

Submission status: Accepted

Solution code:
N = int(input())

As = [[] for _ in range(N)]

for i in range(N):
    n = int(input())
    for j in range(n):
        person, state = map(int, input().split())
        As[i].append([person-1, state])

honest = 0
for i in range(1, 2**N):
    flag = 0
    for j in range(N):  # 人一人ごとにループを回す
        if (i>>j) & 1 == 1:   # 人jは正直と仮定
            for x, y in As[j]:
                if (i>>x) & 1 != y:  # 人jは正直だが矛盾を発見
                    flag = 1
                    break
    if flag == 0:
        # 1の数をカウントし最大となるものを選択
        honest = max(honest, bin(i)[2:].count('1'))

print(honest)

Submission status: Accepted

Solution code:
N = int(input())

testimony = [[] for _ in range(N)]

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

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    _true = [0]*n
    bl = True
    cnt = 0
    for j in range(n):
        if (i >> j) & 1:
            _true[j] = 1
    for j in range(n):
        if _true[j] == 1:
            for x, y in xy[j]:
                if _true[x-1] != y:
                    bl = False
                    break
    if bl:
        cnt = sum(_true)
    ans = max(ans, cnt)

print(ans)