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:
from collections import defaultdict
N = int(input())
dic = defaultdict(list)
A = []
for i in range(N):
    a = int(input())
    A.append(a)
    for j in range(a):
        x,y = map(int,input().split())
        dic[i].append((x-1,y))
# print(dic)
 
from itertools import product
P = product(range(2),repeat=N)
# print(list(p))
 
ans = 0
for p in P:
    flg = True
    for i in range(N):
        if p[i] == 1:
            for xi,yi in dic[i]:
                if p[xi] != yi:
                    flg = False
        if not flg:
            break
    if flg: ans = max(ans, sum(p))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
lst = [[-1 for _ in range(n)] for __ in range(n)]
for i in range(n):
    ai = int(input())
    for j in range(ai):
        hito, which = map(int, input().split())
        lst[i][hito-1] = which

ans = 0
muri = 0
for i in range(2**n):
    kumi = list(format(i, '0'+str(n)+'b'))
    temp = 0
    muri = 0
    for j in range(n):
        if muri == 1:
            break
        elif kumi[j] == '1':
            for k in range(n):
                if (lst[k][j] == 0 and kumi[k] == '1') or (lst[j][k] == 1 and kumi[k] == '0'):
                    muri = 1
                    break
            if muri == 0:
                temp += 1
    if muri == 0:
        ans = max(ans, temp)

print(ans)

Submission status: Accepted

Solution code:
# C問題

from itertools import combinations
import numpy as np
N = int(input())

A = []
x = []
y = []
for i in range(N):
	# 人iの証言を格納する
	Ai = int(input())
	A.append(Ai)
	x.append([])
	y.append([])
	for j in range(Ai):
		xyij = input().split(" ")
		x[i].append(int(xyij[0]) - 1)
		y[i].append(int(xyij[1]))

def judge_contradiction(honest_index, N, A, x, y):
	# 大丈夫ならTrue、矛盾ならFalse
	all_people_judge = np.zeros(N, dtype="int")
	all_people_judge[:] = -1
	for i in honest_index:
		all_people_judge[i] = 1
	for ind in honest_index:
		# 人indは正直者。
		# この人の証言をもとに、all_people_judgeを完成させる
		for i in range(A[ind]):
			# 証言： 人x[ind][i]は、y[ind][i]である
			target, testimony = x[ind][i], y[ind][i]
			if all_people_judge[target] == -1:
				all_people_judge[target] = testimony
				continue
			elif all_people_judge[target] == testimony:
				continue
			else:
				# 矛盾が発生！
				return False
	# all_people_judgeで正直者と判定された人が、honest_indexでもそうなっているか判定
	for i in range(N):
		if all_people_judge[i] == 1:
			if np.any(np.array(honest_index) == i):
				continue
			else:
				return False
	return True

def doit(N, A, x, y):
	for numHonest in range(N, 0-1, -1):
		# numHonest 人が正直者であるとき
		for honest_index in combinations(np.arange(N), numHonest):
			# N人の正直者は、honest_indexに記載されたN人である
			# それで矛盾が生じないか、確かめる
			# import pdb; pdb.set_trace()
			if judge_contradiction(honest_index, N, A, x, y) == True:
				return numHonest
			else:
				continue
	return "hey"

print(doit(N, A, x, y))

Submission status: Accepted

Solution code:
import itertools

N = int(input())

ans = list()

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

for i in range(N):
    for x in itertools.combinations(range(N), N-i):
        for y in x:
            for c, d in ans[y]:
                if d == 0 and c in x:
                    break
                if d == 1 and not c in x:
                    break
            else:
                continue
            break
        else:
            print(N-i)
            exit()
print(0)

Submission status: Accepted

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

_n = int(input())

said = []
for i in range(_n):
    ai = int(input())
    said.append([list(map(int, input().split())) for _ in range(ai)])

ans = 0
for i in range(2 ** _n):
    ynflg = 1
    flg = format(i, 'b').zfill(_n)
    for sy, tag in zip(said, flg):
        if tag == '0':
            continue

        for s in sy:
            if flg[s[0] - 1] != str(s[1]):
                ynflg = 0
                break

        if ynflg == 0:
            break

    if ynflg == 1:
        ans = max(ans, flg.count('1'))

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
import sys
sys.setrecursionlimit(10**6)

def solve(Shogen, isHonests, manId):
  ans = True
  new_honests = []
  for x, y in Shogen[manId-1]:
    if isHonests[x-1] == -1:
      isHonests[x-1] = y
      if y == 1:
        new_honests.append(x)
    elif isHonests[x-1] != y:
      return False
  if new_honests:
    for nh in new_honests:
      ans = ans and solve(Shogen, isHonests, nh)
  return ans

N = int(input())
shogens = []
for _ in range(N):
  a = int(input())
  s = [list(map(int, input().split())) for _ in range(a)]
  shogens.append(s)
ishonests = [-1]*N
for begin in range(1, N+1):
  if ishonests[begin-1] == -1:
    tmphonests = ishonests.copy()
    tmphonests[begin-1] = 1
    if solve(shogens, tmphonests, begin):
      ishonests = tmphonests
    else:
      ishonests[begin-1] = 0
print(sum(ishonests))

Submission status: Accepted

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

def main():
    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())
            x-=1
            XY[i].append((x,y))
    ans=0
    for i in range(1<<n):
        tmp=0
        flag=True
        for j in range(n):
            if (i>>j)&1==0:
                continue
            tmp+=1
            for x,y in XY[j]:
                if (i>>x)&1!=y:
                    flag=False
        if flag:
            ans=max(ans,tmp)
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import product

# Generated by 1.1.5 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():
    # Failed to predict input format
    N = int(input())
    grid = [[None for _ in range(N)] for i in range(N)]
    for i in range(N):
        a = int(input())
        for _ in range(a):
            x, y = list(map(int, input().split()))
            grid[i][x-1] = y
    res = 0
    for p in product([0, 1], repeat=N):
        flag = True
        p = list(p)
        for i in range(N):
            if p[i] == 0:
                continue
            for j in range(N):
                if grid[i][j] is None:
                    continue
                if grid[i][j] == p[j]:
                    continue
                flag = False
                break
            if flag:
                continue
            break
        if flag:
            res = max(res, sum(p))
    print(res)
    pass

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

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


def chk(x,d):
    for l,xx in enumerate(x):
        if xx==1:
            for dd in d[l]:
                #print(dd)
                #print(x)
                if dd[1]==1 and x[dd[0]-1]==0:
                    return False
                if dd[1]==0 and x[dd[0]-1]==1:
                    return False
    return True


N=int(input())

d=[]
for k in range(N):
    aa=int(input())
    #print(aa)
    d.append([])
    for j in range(aa):
        d[-1].append(acinput())


#print(d)
res=0

for x in range(2**N):
    x=list(map(int,list(bin(x)[2:].zfill(N))))
    #print(x)
    if chk(x,d):
        res=sum(x)
    
print(res)

Submission status: Accepted

Solution code:
N = int(input())
ans = []
A = [0 for i in range(N)]
Axy = [0 for i in range(N)]
for i in range(N):
    A[i] = int(input())
    Axy[i] = [[int(i) for i in input().split()] for j in range(A[i])]

for i in range(1<<N):#2^N通りやる
    Truth = []
    maru = 0
    for j in range(N):
        Truth.append(((i>>j)&1)==1)
        maru += ((i>>j)&1)#〇の数
    syogen = [0 for i in range(N)]
    for k in range(N):
        if Truth[k]:
            syogen[k] = 1
    isMujun = True
    for k in range(N):
        if Truth[k] and isMujun:
            for x,y in Axy[k]:
                if syogen[x-1]==y:
                    pass
                else:#矛盾発生
                    ans.append(0)
                    isMujun = False
                    break
    if isMujun:
        ans.append(maru)
print(max(ans))

Submission status: Accepted

Solution code:

n = int(input())
people = {}

for i in range(n):
    sentenses = int(input())
    if sentenses > 0:
        for j in range(sentenses):
            v = list(map(int, input().split()))
            if i in people.keys():
                people[i].append(v)
            else:
                people[i] = [v]
            
ans = 0

for i in range(2**n):
    speaker = []
    p_list = [0] * n
    for j in range(n):
        if ((i >> j) % 2) == 1:
            speaker.append(j)
            p_list[j] = 1

    continue_flag = True
    for s in speaker:
        if continue_flag:
            if s in people.keys():
                sentenses = people[s]
            else:
                continue
            for sent in sentenses:
                if p_list[sent[0]-1] == sent[1]:
                    p_list[sent[0]-1] = sent[1]
                else:
                    continue_flag = False
                    break
        else:
            break
        
    if continue_flag:
        temp_ans = len(speaker)
        ans = max(temp_ans, ans)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
dic = defaultdict(list)
A = []
for i in range(N):
    a = int(input())
    A.append(a)
    for j in range(a):
        x,y = map(int,input().split())
        dic[i].append((x-1,y))
# print(dic)

from itertools import product
P = product(range(2),repeat=N)
# print(list(p))

ans = 0
for p in P:
    flg = True
    for i in range(N):
        if p[i] == 1:
            for xi,yi in dic[i]:
                if p[xi] != yi:
                    flg = False
        if not flg:
            break
    if flg: ans = max(ans, sum(p))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
arr=[]
for i in range(n):
    ansnum=int(input())
    for j in range(ansnum):
        a,b = map(int,input().split())
        arr.append((i,a,b))
#print(arr)
if len(arr)==0:
    print(n)
else:
    #スキップするユーザの選定
    maxcount=0
    for k in range(2**n):
        A=list(bin(k))[2:]
        #print(A[2:])
        while len(A)<n:
            A.insert(0,0)
        A=[int(i) for i in A]

        #d={}
        #print(A)
        for num,j in enumerate(arr):
            if A[j[0]]==0:
                pass
            #print(j)
            #print(j[2])
            #print(A[j[1]-1])
            elif A[j[1]-1]!=j[2]:
                break
            """
            if j[1] not in d:
                d[j[1]]=j[2]
            elif d[j[1]]!=j[2]:
                break
            """
            #print(num)
            if num==len(arr)-1: 
                maxcount=max(maxcount,sum(A))
    print(maxcount)

Submission status: Accepted

Solution code:
N = int(input())

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

ans = 0
for i in range(2 ** N):
    check = [-1] * N #1:正直者、0:不親切
    count = 0 #カウント用
    flag = True
    for j in range(N):
        if (i >> j) & 1: #正直者のとき
            if check[j] == 0: #矛盾しているとき
                flag = False
                break
            else:
                check[j] = 1

            # count += 1

            for x, y in lst[j]:
                if y == 1: #行き先が正直者
                    if check[x] != 0:
                        check[x] = 1
                    else: #矛盾しているとき
                        flag = False
                        break
                else: #y == 0
                    if check[x] != 1:
                        check[x] = 0
                    else:
                        flag = False
                        break
        else: #正直者でないとき
            if check[j] == 1:
                flag = False
                break
            else:
                check[j] = 0

        if flag == False:
            break
    if flag:
        tmp = 0
        for j in range(N):
            if (i >> j) & 1:
                tmp += 1
        # print (i)
        # print (check, flag)
        ans = max(ans, tmp)

print (ans)
# print (lst)

Submission status: Accepted

Solution code:
n = int(input())
a = list()
xy = list()
for i in range(n):
  A = int(input())
  XY = [tuple(map(int, input().split())) for i in range(A)]
  a.append(A)
  xy.append(XY)
honest = [None] * n
ans = 0
for i in range(2 ** n-1,-1,-1):
  mini_ans = 0
  honest = []
  for j in range(n):
    honest.append(i % 2)
    i = i // 2
  for k,v in enumerate(honest):
    if v:
      mini_ans += 1
      for x,y in xy[k]:
        x -= 1
        if honest[x] != y:
          break
      else:
        continue
      break
  else:
    ans = max(ans,mini_ans)
    continue
print(ans)

Submission status: Accepted

Solution code:
n  = int(input())
xs = []
hs = [1] * n

for _ in range(0, n):
	xs.append([None] * n)

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

def solve(hs, i):
	if i == n:
		for j in range(0, n):
			if hs[j] != 0:
				for k in range(0, n):
					if j != k and xs[j][k] != None and hs[k] != xs[j][k]:
						return 0
		return sum(hs)
	
	hs[i] = 1
	x     = solve(hs, i + 1)
	hs[i] = 0
	y     = solve(hs, i + 1)
	
	return max(x, y)

print(solve(hs, 0))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import copy
import itertools

N=input()

L=[ [ None for j in range(N)] for i in range(N)]

for i in range(N):  #i番目の人の意見
    A=input()
    for _ in range(A):
        x,y=map(int, raw_input().split())
        L[i][x-1]=y

CC=list(itertools.product((0,1),repeat=N))

ans=0


for C in CC:
    flag=True
    for i,c in enumerate(C):
        if flag==False: break
        if c==1:
            for x,y in zip(C,L[i]):
                if (x==1 and y==0) or (x==0 and y==1):
                    flag=False
                    break
    else:
        if flag==True:
            ans=max(ans,sum(C))
print ans

Submission status: Accepted

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

import itertools

def main():
    N = int(input())
    XY = []

    for _ in range(N):
        a = int(input())
        if a == 0:
            XY.append([])
            continue
        xy = []
        for _ in range(a):
            xy.append(list(map(int,input().split())))
        XY.append(xy)

    bit_list = list(itertools.product([0, 1], repeat=N))

    answer = 0
    for b in bit_list:
        for i in range(N):
            for x,y in XY[i]:
                if b[i] == 1:
                    if b[x-1] == y:
                        continue
                    else:
                        break
                # else:
                #     if b[x-1] != y:
                #         continue
                #     else:
                #         break
            else:
                continue
            break
        else:
            answer = max(sum(b),answer)
    print(answer)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def Jud(S,n,k):#S:証言、n:人数、
  ans=True
  k2d=format(k,'b').zfill(n)
  people=[]
  for i in range(n):
    if k2d[i]=='1':
      people.append(i)
  for j in people:
        for k in range(len(S[j])):
          if S[j][k][1]==1:
            if S[j][k][0]-1 not in people:
              ans=False
              break
          elif S[j][k][1]==0:
            if S[j][k][0]-1 in people:
              ans=False
              break
  return ans
                
n=int(input())#読み込み
S=[[] for i in range(n)]
for i in range(n):
  s=int(input())
  for j in range(s):
    S[i].append(list(map(int,input().split())))
#print(S)   
honests=[]

for i in range(2**n):
  if Jud(S,n,i)==True:
    i2d=format(i,'b')
    honests.append(i2d.count('1'))
#print(honests)
print(max(honests))

Submission status: Accepted

Solution code:
import itertools

N = int(input())
d = [0]*N
for i in range(N):
    A = int(input())
    d[i] = [list(map(int,input().split())) for _ in range(A)]
ans = 0
l = [0,1]
for s in itertools.product(l, repeat = N):
    flag = 0
    for i in range(N):
        if s[i] == 1:
            for a in d[i]:
                if a[1] == 1:
                    if s[a[0]-1] == 1:
                        pass
                    else:
                        flag = -1
                else:
                    if s[a[0]-1] == 0:
                        pass
                    else:
                        flag = -1
    if flag == 0:
        ans = max(ans, s.count(1))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product, groupby

N = int(input())

testimony = []
for n in range(1, N + 1):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        testimony.append((n, x, y))

ans = []
for pattern in product((1, 0), repeat=N):
    choice_index = tuple(idx + 1 for idx, value in enumerate(pattern) if value == 1)
    choice_answers = [t for t in testimony if t[0] in choice_index]
    groups = []
    for choice_answer in choice_answers:
        person, target, honest_or_kind = choice_answer
        if pattern[target-1] != honest_or_kind:
            break
    else:

        data = sorted(choice_answers, key=lambda z: z[1])
        for k, g in groupby(data, lambda z: z[1]):
            groups.append(list(g))

        for group in groups:
            all_ans = set(tuple(ans[2] for ans in group))
            if len(all_ans) == 2:
                break
        else:
            ans.append(sum(pattern))
print(max(ans))

Submission status: Accepted

Solution code:
N = int(input())
import itertools
TF = [0,1]
All = list(itertools.product(TF, repeat=N))
lis_A = [0]
lis_x = []
lis_y = []
ans = 0
for i in range(N):
  A = int(input())
  lis_A.append(A)
  for j in range(A):
    x,y = map(int,input().split())
    lis_x.append(x-1)
    lis_y.append(y)
for p in range(1,N+1):
  lis_A[p] = lis_A[p-1]+lis_A[p]
for k in range(len(All)):
  L = All[k]
  jud = True
  for g in range(N):
    if L[g] == 1:
      for q in range(lis_A[g],lis_A[g+1]):
        if L[lis_x[q]] != lis_y[q]:
          jud = False
          break
  if jud:
    ans = max(sum(L),ans)
print(ans)

Submission status: Accepted

Solution code:
##def tansaku(gen):
#    mada=False
#    keta=0
#    for i in range(n):
#        if(gen[i]==-1):
#            mada=True
#            keta=i
#    if(mada):
#        nex=gen
#        nex[keta]=0
#        tansaku(nex)
#        nex[keta]=1
#        tansaku(nex)
#    else:
#        print(gen)
#        return

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

#print(a)
#print(sinrai)
ans=0
for i in range(2**n):
    pat=[]
    kanou=True
    kazu=0
    for j in range(n):
        if((i>>j) & 1):
            pat.append(1)
            kazu+=1
        else:
            pat.append(0)
    #print(pat)
    for j in range(n):      #人
        if(pat[j]==0):
            continue
        for k in range(a[j]):   #発言
            hatu=sinrai[j][k]
            if(pat[hatu[0]-1] != hatu[1]):
                kanou=False
    if(kanou):
        ans=max(ans,kazu)

print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

people = int(input())
data = []
truthfulness = [None]*people
i = 0

def contradiction(t,data):
    for i in range(len(t)):
        if t[i] == True:
            for q in data[i]:
                if q[1] == 0:
                    a = False
                else:
                    a = True
                if not t[q[0]-1] == a:
                    return False
    return True

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

num = 0
for v in itertools.product([True,False], repeat=people):
    if(v.count(True) > num):
        if contradiction(v,data):
            num = max(v.count(True),num)
print(num)

Submission status: Accepted

Solution code:
def p_c():
    from itertools import combinations
    n = int(input())
    d = [[set() for _ in range(2)] for _ in range(n)]
    for i in range(n):
        a = int(input())
        for _ in range(a):
            x, y = map(int, input().split())
            d[i][y].add(x-1)
    ans = []
    for i in reversed(range(1, n + 1)):
        for cmb in combinations(range(n), i):
            true_set = set()
            false_set = set()
            for j in range(n):
                if j in cmb:
                    true_set = true_set | d[j][1]
                    false_set = false_set | d[j][0]
                else:
                    false_set.add(j)
            if not true_set & false_set:
                ans.append(n - len(false_set))
    if ans:
        print(max(ans))
    else:
        print(0)
        
p_c()

Submission status: Accepted

Solution code:
import sys
import collections
import itertools


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    dl = []
    for i in range(n):
        a = int(readline())
        d = collections.defaultdict(list)
        for j in range(a):
            x, y = list(map(int, readline().split()))
            d[x-1] += [y]
        dl.append(d)
    mt = 0
    for v in itertools.product([True, False], repeat=n):
        b = True
        for i, vv in enumerate(v):
            if vv:
                for kkk, vvv in dl[i].items():
                    if vvv[0] != v[kkk] :
                        b = False
        if b:
            mt = max(mt, v.count(True))
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

mem = []
for i in range(2 ** N):
  mem.append(("{:0=15}".format(int(bin(i)[2:])))[15-N:])

ans = 0
for m in mem:
  f = True
  for i in range(N):
    if m[i] == "1":
      for li in l[i]:
        if str(li[1]) != m[li[0]]:
          f = False
          break
  if f:
    ans = max(ans, m.count("1"))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
ans=0

for i in range(n):
  _=int(input())
  dic={}
  for j in range(_):
    x,y=map(int,input().split())
    dic[x]=y
  a.append(dic.copy())
  

for i in range(2 ** n):#bit全探索
    b=[]
    for j in range(n):
      if i>>j & 1:
        b.append(j)
    summ=0
    jdg=[-1]*n
    flgg=0
    for j in range(len(b)):
      if jdg[b[j]]==-1:
        jdg[b[j]]=1
      elif jdg[b[j]]!=1:
        flgg=1
        break
      dic=a[b[j]]
      key=list(dic.keys())
      flg=0
      for k in range(len(key)):
        if jdg[key[k]-1]==-1:
          jdg[key[k]-1]=dic[key[k]]
        elif jdg[key[k]-1]==dic[key[k]]:
          jdg[key[k]-1]=dic[key[k]]
        else:
          flg=1
          flgg=1
          break
      if flg==1:
        flgg=1
        jdg=[-2]*n
        break
    
    sumi=0
    if flgg==0:
      for j in range(len(jdg)):
        if jdg[j]==1:
          sumi+=1
    if sumi==len(b):
      summ=sumi
    ans=max(ans,summ)
print(ans)

Submission status: Accepted

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

n = int(input())

comment_list = [ [] for i in range(n) ]
for i in range(n):
    m = int (input())
    for j in range(m):
        a, b = [ int(v) for v in input().split() ]
        comment_list[i].append([a-1,b])

ans = 0
for i in range(2**n):
    s = bin(i)[2:].zfill(n)
    status = 1
    for j, v in enumerate(s):
        for x, y in comment_list[j]:
            if v == "1":
                if s[x] != str(y):
                    status = 0
    if status == 1:
        ans = max(ans, s.count("1"))
print(ans)

Submission status: Accepted

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


def honest(unkind: set, stack: list, s: int, max_num: int,testimony):
    if s < n:
        unkind0 = unkind.copy()
        unkind1 = unkind.copy()
        stack.append(0)
        for i in testimony[s][1]:
            unkind0.add(i)
        max_num = honest(unkind0, stack, s + 1, max_num,testimony)
        stack.pop()

        stack.append(1)
        for i in testimony[s][0]:
            unkind1.add(i)
        max_num = honest(unkind1, stack, s + 1, max_num,testimony)
        stack.pop()
        return max_num
    else:
        count = 0
        for i in range(n):
            if stack[i]:
                count += 1
                if i in unkind:
                    return max_num
        return max(count, max_num)


print(honest(set(), [], 0, 0,testimony))

Submission status: Accepted

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

c = 0
ans = 0
while c < 2 ** (n):
    q = format(c,'b').zfill(n)
    q = list(str(q))
    q = [int(m) for m in q]
    #print('---')
    #print(c, 'q : ' , q)
    #print('')
    p = [0] * n
    count = 0
    ans_tmp = 0
    for i in range(len(q)):
        if q[i] == 1:
            count += 1
            for j in range(len(A[i][1])):
                x,y = A[i][1][j]
                if y == 1:
                    if not int(q[x-1]) == 1:
                        ans_tmp = -1
                else:
                    if not int(q[x-1]) == 0:
                        ans_tmp = -1
    if ans_tmp == 0:
        ans_tmp = count

    if ans_tmp > ans:
        ans = ans_tmp
    c += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

N = int(input())

say = {i:[] for i in range(1, N+1)}
for i in range(N):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        say[i+1].append([x, y])

ans_list = list(itertools.product([0, 1], repeat=N))

max_count = 0
for ans in ans_list:
    flag = 0
    for i, an in enumerate(ans):
        if an == 1:
            for s in say[i+1]:
                # print(ans, s)
                if ans[s[0]-1] == s[1]:
                    continue
                else:
                    flag = 1
                    break
        if flag == 1:
            break
    if flag == 0:
        max_count = max(sum(ans), max_count)


print(max_count)

Submission status: Accepted

Solution code:
import itertools

n = int(input())

speak = [[] for _ in range(n)]


for i in range(n):
    s = int(input())
    for j in range(s):
        a,b = map(int,input().split())
        tal = (a-1,b)
        speak[i].append(tal)

check = 0

b = [i for i in range(n)]
c = len(b)

b_pairs = []
for i in range(1,n+1):
    b_pairs += list(itertools.combinations(b,i))

for i in b_pairs:
    tru = []
    for j in i:
        tru.append(j)
    
    leng = len(tru)
    if leng <= check:
        continue
    
    for k in tru:
        z = 1
        for d,e in speak[k]:
            if d in tru:
                if e == 1:
                    continue
                else:
                    z = 0
            else:
                if e == 0:
                    continue
                else:
                    z = 0
        if z == 0:
            break
    else:
        check = leng
            
print(check)

Submission status: Accepted

Solution code:
N = int(input())

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

result = 0
for i in range(1, 2 ** N):
  t = [-1] * N
  for j in range(N):
    t[j] = (i >> j) & 1
  m = False
  for j in range(N):
    if (i >> j) & 1 == 0:
      continue
    for x, y in s[j]:
      if t[x] != y:
        m = True
        break
  if not m:
    result = max(result, bin(i)[2:].count('1'))
print(result)

Submission status: Accepted

Solution code:
N = int(input())

xys = []

for i in range(N):
    tmp_xy = []
    for j in range(int(input())):
        tmp_xy.append(tuple(map(int, input().split())))
    xys.append(tmp_xy)
        



status = [0 for _ in range(N)]

ans = 0

for i in range(2**N):
    tmp = format(i, 'b').zfill(N)

    
    for j in range(N):
        status[j] = int(tmp[-j-1])
    
    tmp_ans = 0
    isCorrect = True
    for j in range(N):
        if(status[j] == 1):
            for xy in xys[j]:

                if(status[xy[0]-1] != xy[1]):
                    isCorrect = False
                    break
            tmp_ans += 1
        if(not isCorrect):
            tmp_ans = 0
            break

    ans = max(ans, tmp_ans)

print(ans)