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:
def main():

    n = int(input())
    a = [0] * n
    x = [[0] * n for i in range(n)]
    y = [[0] * n for i in range(n)]
    for i in range(n):
        a[i]=int(input())
        for j in range(a[i]):
            x[i][j],y[i][j] = map(int,input().split())
            x[i][j]-=1
    temp=[-1]*n
    ans=0
    for i in range(2**n):
        flg = 'OK'
        case = fill0(i)
        for j in range(n):
            if case[j] == 0:continue
            for k in range(a[j]):
                if case[x[j][k]]==0 and y[j][k]==1:
                    flg='NG'
                    break
                if case[x[j][k]]==1 and y[j][k]==0:
                    flg='NG'
                    break

        if flg == 'OK':
            ans=max(ans,sum(case))
    print(ans)
def fill0(i):
    temp=format(i,'015b')
    a=[]
    for j in range(len(temp)):
        a.append(int(temp[len(temp)-j-1]))
    return a


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
ans=0
a=[0 for i in range(n)]
x=[[0 for i in range(20)]for j in range(20)]
y=[[0 for i in range(20)]for j in range(20)]

for i in range(n):
    a[i] = int(input())
    for j in range(a[i]):
        x[i][j], y[i][j] = map(int,input().split())
        x[i][j]-=1 # 
        
for bits in range(2**n):
    ok=True
    for i in range(n):
        if (bits>>i)&1 == 0:
            continue
        for j in range(a[i]):
            if y[i][j]^((bits>>x[i][j])&1):
                ok = False
    if ok:
        ans = max(ans,str(bin(bits)).count('1'))

print(ans)

Submission status: Accepted

Solution code:
#ABC-147
#参考 https://atcoder.jp/contests/abc147/submissions/8896111
N = int(input())
evidences = [[] for i in range(N)]

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

result = 0
for i in range(1, 2**N):
    consistent = True
    for j in range(N):
        #すでに矛盾するパターンのiとわかっているならば飛ばす。
        if consistent == False:
            break
        #jが正しいと仮定する。(もし0ならcontinueで飛ばされる。)
        if (i >> j) & 1 == 0:
            continue
        #jの証言を一個ずつ確認していく。
        for x, y in evidences[j]:            
            if (i >> x) & 1 != y:
                consistent = False
                break
    #全ての人の証言で矛盾がないパターンのiだったら、1の数(=正直者の数)をresultに記録しておく。
    if consistent == True:
        result = max(result, bin(i)[2:].count("1"))

print(result)

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())
nin = []

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

# print(nin)
ans = 0

for i in range(2**n):
    f = True
    for j in range(n):
        if (i >> j) & 1:
            for x,y in nin[j]:
                if ((i >> (x-1)) & 1) == y:
                    pass
                else:
                    f = False
                    break
    else:
        if f:
            tmp = bin(i).count('1')
            ans = max(ans, tmp)
            # print(i)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

x = []
y = []

S = []

ans = 0

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

for i in range(2**N):
    flag = True
    t = bin(i).count('1')
    for j in range(N):
        if i & (1 << j):
            for p in S[j]:
                if ((i >> (p[0]-1)) & 1) != p[1]:
                    flag = False
                    break
    if flag == True:
        if ans < t:
            ans = t


print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = []
D = []
for i in range(n):
  a = int(input())
  A.append(a)
  l = []
  for j in range(a):
    k = list(map(int, input().split()))
    l.append(k)
  D.append(l)
  
def jud(s):
  fl = True
  for i in range(n):
    if s[i] == "1":
      for item in D[i]:
        if int(s[item[0]-1]) != item[1]:
          fl = False
  if fl:
    return s.count("1")
  else:
    return 0

cans = 0
  
for i in range(2**n):
  s = bin(i)
  s = s[2:]
  s = "0000000000000000" + s
  s = s[-n:]
  cans = max(cans,jud(s))
print(cans)

Submission status: Accepted

Solution code:
n=int(input())
a = [0]*20
x=[[0 for i in range(20)]for j in range(20)]
y=[[0 for i in range(20)]for j in range(20)]

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

ans=0
for bits in range(1<<n):
	isok=True
	for i in range(n):
		if (bits>>i)&1 == 0:
			continue
		for j in range(a[i]):
			if y[i][j]^((bits>>x[i][j])&1):
				isok=False
	if isok:
		tmp=bits
		an=0
		while(tmp):
			if tmp&1:
				an+=1
			tmp//=2
		ans = max(ans,an)
print(ans)

Submission status: Accepted

Solution code:
def solve():
    from itertools import combinations
    from sys import stdin
    f_i = stdin
    
    N = int(f_i.readline())
    
    evidence = dict(zip(range(N), [[] for i in range(N)]))
    for i in range(N):
        A_i = int(f_i.readline())
        for j in range(A_i):
            x, y = map(int, f_i.readline().split())
            x -= 1
            evidence[i].append((x, y))
    
    for num in range(N, 0, -1):
        for people in combinations(range(N), num):
            rec = [0] * N
            for person in people:
                rec[person] = 1
            
            for person in people:
                for x, y in evidence[person]:
                    if rec[x] != y:
                        break
                else:
                    continue
                break
            else:
                return num
    else:
        return 0

print(solve())

Submission status: Accepted

Solution code:
N = int(input())

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

ans = 0
for s in range(2**N-1,-1,-1):
    s = (N-len(bin(s))+2)*'0'+bin(s)[2:]
    pos = True
    for i in range(N):
        if s[i]=='1':
            for x,y in xy[i]:
                if s[x-1]!=str(y):
                    pos = False
                    break
    if pos:
        ans = s.count('1')
        break
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

# print('input >>')
N = int(input())
G = []
for i in range(N):
    A_i = int(input())
    edges = {}
    for n in range(A_i):
        edge = tuple(map(int, (input().split())))
        edges[edge[0]] = edge[1]
    G.append(edges)

prods = product([0,1], repeat=N)
ans = 0

for prod in prods:
    flg = True
    for i, h in enumerate(prod):
        if h == 1:  # 正直者ならその人の言うことを調べる
            shougens = G[i]
            for hito, docchi in shougens.items():
                if (docchi == 1 and prod[hito-1] == 0) or (docchi == 0 and prod[hito-1] == 1):
                    flg = False
    if flg:
        ans = max(ans, sum(prod)) # ここまで来れたら矛盾が生じなかった

# print('----------output----------')
print(ans)

Submission status: Accepted

Solution code:
import itertools

n = int(input())
saids = {}  # saids[i][j] は，人iの，人jについての証言(True:正直 False:不親切)
for i in range(1, n + 1):
    said = {}
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        said[x] = y
    saids[i] = said
ans = 0
for p in range(2**n):
    honest = [i + 1 for i in range(n) if p & 2 ** i != 0]
    for x, y in itertools.product(honest, range(1, n+1)):
        if y not in saids[x]:
            continue
        if saids[x][y] == 0 and y in honest:
            break
        if saids[x][y] == 1 and y not in honest:
            break
    else:
        ans = max(ans, len(honest))
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
say=[]
for _ in range(N):
  A=int(input())
  t=[]
  for __ in range(A):
    s = list(map(int,input().split()))
    t.append(s)
  say.append(t)

ans=0
for i in range(2**N):
  flag=True
  for j in range(N):
    if not flag:
      break
    if ((i>>j) & 1):
      for s in say[j]:
        if ((i>>s[0]-1)&1) !=s[1]:
          flag=False
  if flag:
    mount = bin(i).count("1")
    ans=max(ans,mount)
print(ans)

Submission status: Accepted

Solution code:
def solve():
    n=int(input())
    ev=[[] for _ in range(n)]
    for i in range(n):
        a=int(input())
        l=[]
        for j in range(a):#証言
        
            x,y=map(int,input().split())
            l.append([x-1,y])
        ev[i]=l
    
    ans=0
    
    for i in range(2**n):
        result=0
        honest=[]
        for j in range(n):
            
            if ((i>>j)&1): #jは正直者
                honest+=ev[j]
                #正直者と仮定した人の証言を集める    
                
        for j in range(n):
            
            if ((i>>j)&1): #jは正直者
                result+=1
                if [j,0] in honest:
                    result=0
                    break
            else:
                if [j,1] in honest:
                    result=0
                    break
                    
        ans=max(ans,result)
        
    print(ans)
    
solve()

Submission status: Accepted

Solution code:
N = int(input())
say = []
for i in range(N):
    A = int(input())
    t = []
    for j in range(A):
        s = list(map(int,input().split()))
        t.append(s)
    say.append(t)

a = 0
for i in range(2**N):
    judge = 1 
    
    for j in range(N):
        if judge == 0:
            break
        if ((i >> j) & 1):
            for k in range(len(say[j])):
                if ((i>>(say[j][k][0]-1))&1) != say[j][k][1]:
                    judge = 0
    
    if judge:
        c = bin(i).count("1")
        a = max(a,c)
print(a)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#include <bitset>

def judge(n, testimony, hypothesis):
    i = 0
    while i < n:
        if hypothesis & (1 << i):
            a, xlist, ylist = testimony[i]
            
            j = 0
            while j < a:                
                if (not (hypothesis & (1 << xlist[j])) and ylist[j] == 1) \
                    or ((hypothesis & (1 << xlist[j])) and ylist[j] != 1):
                    return False

                j += 1

        i += 1
    
    return True

# input
n = int(input())

i = 0
testimony = []
while i < n:
    a = int(input())
    xlist = []
    ylist = []

    j = 0
    while j < a:
        x, y = map(int, input().split())
        xlist.append(x - 1)
        ylist.append(y)

        j += 1

    tlist = [a, xlist, ylist]
    testimony.append(tlist)

    i += 1

# processing
num = 0

i = 0
bstr = ""
while i < n:
    bstr += "1"
    i += 1

b = int(bstr, 2)

hypothesis = 0b1
while hypothesis <= b:
    if judge(n, testimony, hypothesis):
        tnum = bin(hypothesis).count("1")
        if num < tnum:
            num = tnum

    hypothesis += 1

# output
print(num)

Submission status: Accepted

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

ans = 0

for i in range(2 ** n):
    fail = False #　うまく行かなかったとき,矛盾が生じたときTrue
    results = [None] * n # 結果用のリスト
    for j in range(n):
        # 嘘つきと仮定している人以外の証言の整合性を図る
        candidate = ((i >> j) & 1 ) == 1
        # iを2進数としてjだけビットシフトその一番下の桁が1かどうか判定する
        # i >> jでiをjだけシフトした10進数の値が得られる.
        # (i >> j) & 1 でビットのしもひと桁が1かどうか判定する
        # ((i >> j) & 1) == 1で下一桁が1のときTrue
        # Trueのとき,正直者認定
        if results[j] == None:
            results[j] = candidate
        elif results[j] != candidate:
            # 矛盾が生じたとき
            fail = True
            break
        if candidate == False:
            continue
        else:
            for comment in comments[j]:
                if results[comment[0]] == None:
                    results[comment[0]] = comment[1]
                if results[comment[0]] != comment[1]:
                    fail = True
                    break
            if fail:
                break
    if not fail:
        
        counter = 0
        for k in results:
            if k:
                counter += 1
        if counter >= ans:
            ans = counter
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
l=[0]*n
ans=0
for i in range(n):
	a.append(int(input()))
	l[i]=[list(map(int,input().split())) for i in range(a[-1])]
for i in range(2**n):
	i=format(i,'b').zfill(n)
	c=[]
	for j in range(n):
		if i[j]=='1':
			c.append(j)
	for j in c:
		for k in l[j]:
			if k[1]==1 and (k[0]-1 not in c):
				break
			elif k[1]==0 and (k[0]-1 in c):
				break
		else:
			continue
		break
	else:
		ans=max(ans,len(c))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
l=[0]*n
ans=0
for i in range(n):
	a.append(int(input()))
	l[i]=[list(map(int,input().split())) for i in range(a[-1])]
for i in range(2**n):
	i=format(i,'b').zfill(n)
	c=[]
	for j in range(n):
		if i[j]=='1':
			c.append(j)
	for j in c:
		for k in l[j]:
			#print(k)
			if k[1]==1 and (k[0]-1 not in c):
				break
			elif k[1]==0 and (k[0]-1 in c):
				break
		else:
			continue
		break
	else:
		ans=max(ans,len(c))
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
SyoMax=0
syo=[set() for i in range(N)]
hus=[set() 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==0:
      hus[i].add(x)
    else:
      syo[i].add(x)
syoflag=[0]*N
syomax=0
for i in range(2**N):
  I=i
  SYO=set()
  HUS=set()
  for j in range(N):
    if I%2==1:
      syoflag[j]=1
      SYO.add(j+1)
      SYO|=syo[j]
      HUS|=hus[j]
    else:
      HUS.add(j+1)
      syoflag[j]=0
    I=I//2
  if len(SYO&HUS)==0:
    syomax=max(syomax,sum(syoflag))
print(syomax)

Submission status: Accepted

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

ans = 0
for i in range(1,2**n):
	cur_bit = bin(i)[2:].zfill(len(bin(2**n-1)[2:]))
	res = list(map(int,cur_bit))
	j = 0
	cnt = 0
	# print(cur_bit)
	for c,xy in zip(cur_bit,XY):
		flag = 1
		if c == "0":
			continue
		for x,y in xy:
			if res[x] != y:
				flag = 0
				break
		if not flag:
			break
		cnt += 1
	# print(cnt)
	if flag:
		try:
			ans = max(ans,cnt)
		except ValueError:
			pass
print(ans)

Submission status: Accepted

Solution code:
def hou2(tarrs, s, N):
    def checkTestimony(s, t):
        scopy = s[:]
        for i in range(len(s)):
            if s[i] != t[i] and s[i] != 0 and t[i] != 0:
                return None
            if t[i]:
                scopy[i] = t[i]
        return scopy
 
    def search(pos, N, s, acc):
        if pos < N:
            check_tp = checkTestimony(s, tarrs[pos])
            if s[pos] == 1:
                s[pos] = -1
                if check_tp:
                    check_tp[pos] = 1
                    return search(pos + 1, N, check_tp, acc + 1)
                else:
                    return 0
            if check_tp and s[pos] == 0:
                s[pos] = -1
                check_tp[pos] = 1
                return max(search(pos + 1, N, check_tp, acc + 1), search(pos + 1, N, s, acc))
            else: # testimony unacceptable, assuming unkind
                s[pos] = -1
                return search(pos + 1, N, s, acc)
        else:
            return acc
 
    return search(0, N, s, 0)
    
 
if __name__ == "__main__":
    import sys
    in_arr = []
    for line in sys.stdin:
        in_arr.append([int(_) for _ in line.strip().split()])
    N = in_arr[0][0]
    i = 1
    tarrs = []
    s = [0] * N
    while i < len(in_arr):
        tnum = in_arr[i][0]
        tarr = [0] * N
        for j in range(tnum):
            x, y = in_arr[1 + j + i]
            tarr[x - 1] = 1 if y else -1 # -1 claimed unkind, 1 claimed honest
        if tarr[len(tarrs)] == -1: # claimed self to be unkind
            s[len(tarrs)] = -1
        tarrs.append(tarr)
        i += tnum + 1
    print(hou2(tarrs, s, N))

Submission status: Accepted

Solution code:
#input
N = int(input())

B = [[] for _ in range(N)]
for i in range(N):
    A = int(input())
    for _ in range(A):
        x, y  = map(int, input().split())
        B[i].append([x-1, y])
    
#output
answer = 0
for i in range(1, 2**N):
    Flag = True
    for j in range(N):
        if (i >>j) & 1 == 0:
            continue
        for x, y in B[j]:
            if (i >> x) & 1 != y:
                Flag = False
                break
        if not Flag:
            break
    if Flag:
        answer = max(answer, bin(i)[2:].count("1"))

print(answer)

Submission status: Accepted

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

for i in range(n):
      aa=int(input())
      a.append(aa)
      d=[]
      for j in range(aa):
            x,y=map(int,input().split())
            d.append((x,y))
      b.append(d)
cc=0
for i in range(2**n):
      L=[0]*n
      for j in range(n):
            if ((i>>j)&1):
                  L[j]=1
      if 1 in L:
            flag=True
            for k in range(n):
                  if L[k]==1:
                        for m in range(a[k]):
                              if L[b[k][m][0]-1]!=b[k][m][1]:
                                    flag=False
                                    break
            if flag:
                  cc=max(sum(L),cc)
print(cc)

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0

for i in range(2**N):
    bin_i = format(i, '0' + str(N) + 'b')
    flag = True
    for j in range(N):
        for k in range(A[j]):
            if bin_i[j] == '1' and xy[j][k][1] != int(bin_i[xy[j][k][0]-1]):
                flag = False
                break
        if not flag:
            break

    if flag is True:
        honest = bin_i.count('1')
        if honest > ans:
            ans = honest

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    consistent = True
    for j in range(n):
        if (i>>j) & 1 == 0:
            continue
        for x, y in evidences[j]:
            if (i>>x) & 1 != y:
                consistent = False
                break
    if consistent:
        ans = max(ans, bin(i)[2:].count('1'))

print(ans)

Submission status: Accepted

Solution code:
import itertools
n = int(input())
data = []
for x in range(n):
    for y in range(int(input())):
        k, l = map(int, input().split())
        data.append((x, k - 1, l))
ans = 0
for i in itertools.product([1,0], repeat=n):
    s = True
    for g in data:
        if i[g[0]] == 1 and i[g[1]] != g[2]:
            s = False
            break
    if s:
        ans = max(ans, sum(i))
print(ans)

Submission status: Accepted

Solution code:
import itertools
n = int(input())
data = []
for x in range(n):
    for y in range(int(input())):
        k, l = map(int, input().split())
        data.append((x, k - 1, l))
ans = 0
for i in itertools.product([1,0], repeat=n):
    s = sum(i)
    for g in data:
        if i[g[0]] == 1 and i[g[1]] != g[2]:
            s = 0
            break
    ans = max(ans, s)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import sys
input = sys.stdin.readline
n = int(input())
data = []
for x in range(n):
    for y in range(int(input())):
        k, l = map(int, input().split())
        data.append((x, k - 1, l))
ans = 0
for i in itertools.product([1,0], repeat=n):
    s = sum(list(i))
    for g in data:
        if i[g[0]] == 1 and i[g[1]] != g[2]:
            s = 0
            break
    ans = max(ans, s)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n = int(input())
data = []
for x in range(n):
    for y in range(int(input())):
        k, l = map(int, input().split())
        data.append((x, k - 1, l))
ans = 0
for i in itertools.product([1,0], repeat=n):
    s = sum(list(i))
    if ans > s:
        continue
    for g in data:
        if i[g[0]] == 1 and i[g[1]] != g[2]:
            s = 0
            break
    ans = max(ans, s)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n = int(input())
data = []
for x in range(n):
    for y in range(int(input())):
        k, l = map(int, input().split())
        data.append((x, k - 1, l))
ans = 0
for i in itertools.product([1,0], repeat=n):
    s = sum(list(i))
    for g in data:
        if i[g[0]] == 1 and i[g[1]] != g[2]:
            s = 0
            break
    ans = max(ans, s)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ip = []

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

max = 0    
for i in range(n) :
  max += 2**i

ans = 0
for i in range(0,max+1) :
  s = [2 for _ in range(n)]
  bit = i
  count = 0
  index = 0
  check = 0
  for j in range(n) :
    if bit%2 == 1 :
      if s[j] == 0 :
        check = 1
        break
      s[j] = 1
    else :
      if s[j] == 1 :
        check = 1
        break
      s[j] = 0
    bit = bit//2
    for k in range(ip[index]) :
      if s[j] == 1 :
        if ip[index+1+k][1] == 1 :
          if s[ip[index+1+k][0]-1] == 0 :
            check = 1
            break
          s[ip[index+1+k][0]-1] = 1
        elif ip[index+1+k][1] == 0 :
          if s[ip[index+1+k][0]-1] == 1 :
            check = 1
            break
          s[ip[index+1+k][0]-1] = 0
    if check == 1 :
      break
    index += ip[index] + 1
  if ans < s.count(1) and check ==0 :
    ans = s.count(1)

print(ans)

Submission status: Accepted

Solution code:
import itertools
n = int(input())
data = {}
for x in range(n):
    data[x] = []
    for y in range(int(input())):
        k, l = map(int, input().split())
        data[x].append((k - 1, l))

ans = 0
for i in itertools.product([1,0], repeat=n):
    h = True
    for x in range(n):
        if i[x] == 1:
            for g in data[x]:
                if i[g[0]] != g[1]:
                    h = False
        if h == False:
            break
    if h == True:
        ans = max(ans, sum(list(i)))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N = int(input())
A = [None]*N
xy = [None]*N
for n in range(N):
    A[n] = int(input())
    xy[n] = [(lambda u: (u[0]-1, u[1]))(inpl()) for _ in range(A[n])]
ans = 0
for c in product(range(1,-1,-1), repeat=N):
    if sum(c) <= ans:
        continue
    for i in range(N):
        if c[i]:
            for x, y in xy[i]:
                if c[x] != y:
                    break
            else:
                continue
            break
    else:
        ans = sum(c)
print(ans)

Submission status: Accepted

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


def main():
    N = int(input())
    H = [0]*N
    U = [0]*N
    for i in range(N):
        m = int(input())
        for j in range(m):
            x, y = map(int, input().split())
            x -= 1
            if y:
                H[i] += (1 << x)
            else:
                U[i] += (1 << x)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
xy=[]
for i in range(n):
    ai=int(input())
    xyi=[]
    for j in range(ai):
        xyj=list(map(int,input().split()))
        xyi.append(xyj)
    xy.append(xyi)
#print(xy)

ans=0
for i in range(2**n):
    bit_i=format(i,'b').zfill(n)
    person=list(bit_i)
    clear=True
    for j in range(n):
        if(person[j]=='0'):
            continue

        xyj=xy[j]
        for k in range(len(xyj)):
            if(person[xyj[k][0]-1] != str(xyj[k][1])):
                clear=False
                break

        if(not clear):
            break

    if(clear and (ans < person.count('1'))):
#        print(person)
        ans=person.count('1')

print(ans)

Submission status: Accepted

Solution code:
def popcount(n):
    return bin(n).count("1")


N = int(input())

A = [0] * N
x = [[0] * N for i in range(N)]
y = [[0] * N for j in range(N)]

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

# 各々が正直かそうでないかの2^N通りの全パターンについて、矛盾が起きないかどうかを調べる
# iビット目の 0/1 によって、正直かどうかを表す（1 → 正直、 0 → 不親切）
ans = 0
for bits in range(1 << N):
    is_ok = True
    for i in range(N):
        if not (bits & 1 << i):  # 不親切な人の証言は無視する
            continue
        for j in range(A[i]):
            target_is_honest_by_pattern = (bits >> (x[i][j] - 1)) & 1
            target_is_honest_by_testimony = y[i][j]
            if target_is_honest_by_pattern ^ target_is_honest_by_testimony:
                is_ok = False
    if is_ok:
        ans = max(ans, popcount(bits))

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n=inp()
    t=[[] for _ in range(n)]
    s=[[] for _ in range(n)]
    for i in range(n):
        a=inp()
        for _ in range(a):
            x,y=inpm()
            if y==1:
                t[i].append(x-1)
            else:
                s[i].append(x-1)
    res=0
    for k in range(pow(2,n),-1,-1):
        flag = True
        cnt = 0
        for i in range(n):
            if (k>>i)&1 == 1:
                for e in t[i]:
                    if (k>>e)&1 == 0:
                        flag = False
                for e in s[i]:
                    if (k>>e)&1 == 1:
                        flag = False
                cnt+=1
        if flag:
            res = max(res,cnt)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

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


def ok(i, shogens):
    for j in range(N):
        if (i >> j) & 1:
            for x, y in shogens[j]:
                if bin(i >> (x - 1))[-1] == str(y):
                    continue
                else:
                    return False
    return True


ans = 0
for i in range(2 ** N):
    if ok(i, shogens):
        ans = max(ans, bin(i).count('1'))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[[] for x in range(n)]
for i in range(n):
    ai =int(input())
    for j in range(ai):
        xi,yi=[int(x) for x in input().split()]
        xi-=1
        a[i].append((xi,yi))
ans=0
for i in range(2**n):
    validate=[0]*n
    for j in range(n):
        if (i >> j) & 1:
            validate[j]=1
    flag=True
    for k in range(n):
        if validate[k]==0:
            continue
        for xi,yi in a[k]:
            if validate[xi]!=yi:
                flag=False
                break
        if not flag:
            break
    if flag:
        ans=max(ans,sum(validate))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[0]*n
xy=[[] for _ in range(n)]
for i in range(n):
    aa = int(input())
    a[i]=aa
    for j in range(aa):
        xx,yy = map(int, input().split())
        xy[i].append([xx-1,yy])
ans=0
for i in range(2**n):
    str_bin = str(bin(i))[2:].zfill(n)
    f=True
    for j in range(n):
        if str_bin[j]=="1":
            for xxyy in xy[j]:
                if str_bin[ xxyy[0] ]!=str(xxyy[1]):
                    f=False
    if f:
        ans = max(ans,sum(int(i) for i in str_bin))
print(ans)