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:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N = I()
A = [0]*N
x = []
y = []
for i in range(N):
    A[i] = I()
    x0,y0 = Line(A[i],2)
    for j in range(len(x0)):
        x0[j] -= 1
    x.append(x0)
    y.append(y0)

ans = 0
from itertools import product
a = list(product([0,1],repeat=N))

for b in a:
    flag = True
    for i in range(N):
        if b[i]==1:
            for k in range(len(x[i])):
                if b[x[i][k]]!=y[i][k]:
                    flag=False
                    break
    if flag:
        now = sum(b)
        if now>ans:
            ans = now
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

ans = 0
for i in range(1<<N):
	i = "{:b}".format(i).zfill(N)
	flag = 0
	for j in range(N):
		if i[j] == '1': # 正直者
			for x, y in xy[j]:
				if y != int(i[x-1]):
					flag = 1
					break
		if flag == 1:
			break
	else:
		tmp = sum(map(int, list(i)))
		ans = ans if ans >= tmp else tmp
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = []
L = [[] for _ in range(N)]
for i in range(N):
    a = int(input())
    A.append(a)
    for _ in range(a):
        x,y = map(int, input().split())
        L[i].append((x, y))
        
ans = 0
for i in range(2**N, 2**(N+1)):
    f = 0
    b = bin(i)
    human = [0]*N
    for j in range(3, len(b)):
        if b[j] == "1":
            human[j-3] = 1
    for j in range(N):
        if human[j] == 0:
            continue
        for k in range(A[j]):
            if human[L[j][k][0]-1] != L[j][k][1]:
                f = 1
                break
    if f == 0:
        ans = max(ans, sum(human))
        
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=[]
xy=[]
for i in range(N):
  A.append(int(input()))
  temp=A[-1]
  xy_temp=[]
  for j in range(temp):
    x, y=map(int, input().split())
    x-=1
    xy_temp.append([x, y])
    
  xy.append(xy_temp)
  
def num2bi(x, k):
  #10進数xを2進数k桁(string)で出力
  out=format(x, '0'+str(k)+'b')
  return out

n=2**N
counter=0
for i in range(n):
  temp=num2bi(i, N)
  a=True
  for i in range(N):
    if temp[i]=='1':
      for j in range(A[i]):
        if temp[xy[i][j][0]]!=str(xy[i][j][1]):
          a=False
        
  if a==True:
    count=0
    for i in range(N):
      if temp[i]=='1':
        count+=1
    counter=max(counter, count)
    
print(counter)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))



def main():
    n = ii()
    a = [0 for i in range(n+1)]
    shougen = [[] for i in range(n+1)]

    for i in range(1,n+1):
        a[i] = ii()
        for j in range(a[i]):
            x,y = mi()
            shougen[i].append([x,y])
    

    ans = 0
    for itr in range(2**n):
        ilist = [0]
        tmp = itr
        while tmp > 0:
            ilist.append(tmp%2)
            tmp//=2
        if len(ilist) < n+1:
            for i in range(n+1-len(ilist)):
                ilist.append(0)
        flag = True
#        print(ilist)
        for i in range(n+1):
            if ilist[i] == 0:
                continue
            else:
                for hatugen in shougen[i]:
                    if not ilist[hatugen[0]] == hatugen[1]:
                        flag = False
                        break
            if not flag:
                break
        if flag:
            ans = max(ans,sum(ilist))
    print(ans)

        


main()

Submission status: Accepted

Solution code:
N=int(input())
XY=[[] for i in range(N)]

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

ans=0
for i in range(2**N):
  ch=1
  cnt=0
  for j in range(N):
    if i>>j & 1:
      cnt+=1
      for xy in XY[j]:
        if xy[1]==1 and (i>>(xy[0]-1)&1) or xy[1]==0 and (i>>(xy[0]-1)&1)==0:
          continue
        else:
          ch=0
          break
    if ch==0:
      break
  if ch:
    ans=max(ans,cnt)

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**N):
    kind = [False]*N
    for j in range(N):
        if (i >> j) % 2 == 1:
            kind[j] = True

    flag = True
    tmp = 0
    for j in range(N):
        if kind[j]:
            tmp += 1

            for x, y in xy[j]:
                if (y == 1 and kind[x-1]) or (y == 0 and kind[x-1] == False):
                    continue

                else:
                    flag = False
                    tmp = 0
                    break

        if flag == False:
            tmp = 0
            break

    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

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

def check(honest) :
    for i in range(N) :
        for j in range(N) :
            if honest[i] and ((honest[j] == 0 and A[i][j] == 1) or (honest[j] == 1 and A[i][j] == 0)) :
                return False
                
    return True

ret = 0
for i in range(2 ** N) :
    honest = [0] * N
    for j in range(N) :
        if i & 1 :
            honest[j] = 1
        i //= 2
    
    if check(honest) :
        ret = max(ret, sum(honest))
    
print(ret)

Submission status: Accepted

Solution code:
def main():
    n = input()
    aa = []
    for _ in xrange(n):
        a = []
        for _ in xrange(input()):
            x, y = map(int, raw_input().split())
            a.append([x - 1, y])
        aa.append(a)
    best = 0
    for x in xrange(2 ** n):
        xx = [bool(x & (1 << i)) + 0 for i in xrange(n)]
        if all(all(xx[i] == f for i, f in a) for x, a in zip(xx, aa) if x):
            best = max(best, sum(xx))
    print best


main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    edge=[[]for _ in range(N)]
    for i in range(N):
        a=I()
        for _ in range(a):
            x,y = MI()
            edge[i].append((x-1,y))

    max_bit = 1<<N
    ans = 0
    for bit in range(max_bit):
        cnt = 0
        T = []
        people = [0]*N
        for i in range(N):
            if (1<<i)&bit:
                people[i]=True
                cnt += 1
                T.append(i)
            else:
                people[i]= 2
        ok = True
        visited = set()
        while T:
            u = T.pop()
            visited.add(u)
            for v,tf in edge[u]:
                if tf==1:
                    if people[v]==0:
                        ok = False
                        break
                    people[v] = True
                    if v not in visited:
                        T.append(v)
                        visited.add(v)
                else:
                    if people[v]==1:
                        ok=False
                        break
                    people[v] = False
        if ok:
            ans = max(ans,cnt)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
tf = [0]*N
for bit in range(2**N):
    jdg = True
    for i in range(N):
        tf[i] = bit%2
        bit = bit >> 1
    for a in range(N):
        if tf[a] == 1:
            for i in range(N):
                if arr[a][i] != -1:
                    if arr[a][i] != tf[i]:
                        jdg = False
                        break
        if not jdg:
            break
    if jdg:
        ans = max(ans,tf.count(1))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

# print(xy)
ans = 0
for i in range(2 ** n):
    h = [0] * n
    for j in range(n):
        if (i >> j) & 1:
            h[j] = 1

    f = True
    for j in range(n):
        for k in range(len(xy[j])):
            x = xy[j][k][0] - 1
            y = xy[j][k][1]

            if y == 1:
                if (h[j] == 1 and h[x] == 0):
                    f = False
            else:
                if (h[j] == 1 and h[x] == 1):
                    f = False

    if f:
        ans = max(ans, sum(h))

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

Ps, ans = itertools.product([0, 1], repeat=N), 0
for P in Ps:
    right = True
    for i, p in enumerate(P):
        if p == 1:
            for x, y in S[i]:
                if (y == 1 and P[x - 1] == 0) or (y == 0 and P[x - 1] == 1):
                    right = False
    if right:
        ans = max(ans, sum(P))

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=[[]for i in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        s[i].append([x-1,str(y)])
an=0
for i in range(2**n):
    b=bin(i)[2:]
    b="0"*(n-len(b))+b
    c=["a"]*n
    d=0
    for i in range(n):
        if b[i]!=c[i] and c[i]!="a":
            break
        else:
            c[i]=b[i]
            if b[i]=="1":
                for (j,h) in s[i]:
                    if c[j]!="a" and h!=c[j]:
                        d=1
                        break
                    else:
                        c[j]=h
        if d==1:
            break
    else:
        an=max(an,b.count("1"))
print(an)

Submission status: Accepted

Solution code:
def f(t,a,n,hist):
    if t != n:
        return max(f(t+1,a,n,hist+[0]),f(t+1,a,n,hist+[1]))
    for i in range(n):
        if hist[i] == 1:
            for j in range(n):
                if a[i][j] == -1:
                    continue
                if a[i][j] != hist[j]:
                    return 0
    return hist.count(1)

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

Submission status: Accepted

Solution code:
n=int(input())
a=[[] for i in range(n)]
b=[[] for i in range(n)]
for i in range(n):
    ai=int(input())
    for j in range(ai):
        x,y=map(int,input().split())
        x-=1
        if y==1:
            a[i].append(x)
        else:
            b[i].append(x)
ok=0
for i in range(2**n):
    j=i
    k=0
    cnt=0
    flag=True
    while(j>0 and flag):
        if j&1:
            cnt+=1
            for x in a[k]:
                if i|(1<<x)!=i:
                    flag=False
                    break
            for x in b[k]:
                if i&(1<<x)!=0:
                    flag=False
                    break
        j//=2
        k+=1
    if flag:
        ok=max(ok,cnt)
print(ok)

Submission status: Accepted

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

ans = 0
for i in range(2 ** N):
    flg = True
    for j in range(N):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            for x, y in G[j]:
                if (i >> x) & 1 != y:
                    flg = False
    if flg:
        c = 0
        for k in range(N):
            if ((i >> k) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
                c += 1
        ans = max(ans, c)

print(ans)

Submission status: Accepted

Solution code:

N = int(input())
ans = 0

dic = {}

for i in range(N):

    dic[i] = []

    A = int(input())

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

ans = 0
for i in range(2 ** N):

    si = format(i,"b")
    si = si.zfill(N)

    num = 0
    for j in si:
        if j == "1":
            num += 1

    flag = True
    #print (si,dic)
    for j in range(N):

        if si[j] == "1":

            for k in dic[j]:
                x = k[0]
                y = k[1]

                
                if int(si[x-1]) != y:
                    #print (si,x-1,y)
                    flag = False

    if flag:
        ans = max(ans,num)

print (ans)

Submission status: Accepted

Solution code:
n = int(input())

ans = 0
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-1, y))

for bit in range(1<<n):
    flag = 0
    for j in range(n):
        if (bit & (1<<j)) > 0:
            for x, y in xy[j]:
                if y == 1 and ((bit & (1<<x)) == 0):
                    flag = 1
                    break
                elif y == 0 and ((bit & (1<<x)) > 0):
                    flag = 1
                    break
    if flag:
        continue
    count = 0
    for j in range(n):
        if (bit & (1<<j)) > 0:
            count += 1
    ans = max(ans, count)

print(ans)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	L = [[] for i in range(N)]
	for i in range(N):
		A = int(input())
		for j in range(A):
			x, y = getlist()
			x -= 1
			L[i].append([x, y])
	#print(L)

	ans = 0
	for i in range(1 << N):
		output = [0] * N
		cnt = 0
		for j in range(N):
			if ((i >> j) & 1) == 1:
				output[j] = 1
				cnt += 1
		judge = "Yes"
		for j in range(N):
			if output[j] == 1:
				for x, y in L[j]:
					if output[x] != y:
						judge = "No"
						break

		if judge == "Yes":
			ans = max(ans, cnt)
	print(ans)



if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

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

def convert(i, n):
    ret = []
    for j in range(n):
        if i & (1<<j):
            ret.append(1)
        else:
            ret.append(0)
    return ret

def check(tf, people):
    for i in range(len(people)):
        if not tf[i]:
            continue
        for j in range(len(people[i])):
            say = people[i][j]
            if say[1] != tf[say[0]]:
                return False
    return True

def main():
    n = ri()
    people = []
    for i in range(n):
        a = ri()
        say = []
        for j in range(a):
            x, y = rli()
            x -= 1
            say.append([x, y])
        people.append(say)
    ans = 0
    for i in range(pow(2, n)):
        tf = convert(i, n)
        ok = check(tf, people)
        if not ok:
            continue
        ans = max(ans, sum(tf))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
X = []
for _ in range(N):
    a = int(input())
    X.append([[int(a) for a in input().split()] for __ in range(a)])

def chk(m):
    L = [m >> i & 1 for i in range(N)]
    for i in range(N):
        for x, y in X[i]:
            x -= 1
            if L[i] and L[x] != y: return 0
    return 1

ma = 0
for i in range(1<<N):
    if chk(i):
        ma = max(ma, bin(i).count("1"))
print(ma)

Submission status: Accepted

Solution code:
n = int(input())

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

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

ret = 0
for mask in range(1 << n):
    t = [(mask >> i) & 1 for i in range(n)]
    flg = True
    for i in range(n):
        if t[i]:
            for x, y in e[i]:
                if t[x] != y:
                    flg = False
                    break
            if not flg:
                break
    if flg:
        ret = max(ret, sum(t))

print(ret)

Submission status: Accepted

Solution code:
N = int(input())

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

ans = 0
for mask in range(1 << N):
    can = True
    for i, s in enumerate(M):
        if (mask & (1 << i)) != 0:
            for x, y in s:
                v = 1 if (mask & (1 << x)) != 0 else 0
                if v != y:
                    can = False
                    break
    if can:
        cnt = 0
        for i in range(N):
            if (mask & (1 << i)) != 0:
                cnt += 1
        ans = max(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A = [None]*N
for i in range(N):
    m = int(input())
    A[i] = [list(map(int,input().split())) for _ in [0]*m]

ans = 0
for i in range(2**N):
    done = [-1]*N
    for j in range(N):
        if (i>>j)&1==0:
            if done[j] == 1: break
            done[j] = 0
            continue
        if done[j] == 0 : break
        done[j] = 1
        breakFlg = False
        for x,y in A[j]:
            x -= 1
            if done[x] == -1:
                done[x] = y
            elif done[x] != y:
                breakFlg = True
                break
        if breakFlg: break
    else:
        tmp = sum(map(int,bin(i)[2:]))
        ans = max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
n = int(input())
l = [[] for _ in range(n)]
for i in range(n):
    for _ in range(int(input())):
        l[i].append(list(map(int, input().split())))

people = list(range(1, n + 1))

for res in people[::-1]:
    for c in combinations(people, res):
        s = set(c)
        valid = True
        for i in c:
            for p, y in l[i - 1]:
                if y == 0:
                    valid &= not p in s
                else:
                    valid &= p in s
            if not valid:
                break
        if valid:
            print(res)
            exit()
print(0)

Submission status: Accepted

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

def popcount(i):
    assert 0 <= i < 0x100000000
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24

N = int(readline())

G = [0]*N
H = [0]*N
for i in range (N):
    A = int(readline())
    for _ in range(A):
        x, y = map(int, readline().split())
        if y == 1:
            G[i] |= 1<<(x-1)
        else:
            H[i] |= 1<<(x-1)

ans = 0

for s in range(1<<N):
    for i in range(N):
        if (1<<i) & s:
            g, h = G[i], H[i]
            if g != (g&s):
                break
            if h != (h&(~s)):
                break
            
    else:
        ans = max(ans, popcount(s))
print(ans)

Submission status: Accepted

Solution code:
from itertools import chain, combinations


def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))


n = int(input())
x = []
for i in range(n):
    xi = []
    a = int(input())
    for j in range(a):
        xij, yij = map(int, input().split())
        xi.append((xij-1, bool(yij)))
    x.append(xi)

res = 0
for cands in powerset(range(n)):
    cands = set(cands)
    for c in cands:
        flagc = True
        for xc, yc in x[c]:
            if yc != (xc in cands):
                flagc = False
                break
        if not flagc:
            break
    else:
        res = max(len(cands), res)
print(res)

Submission status: Accepted

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

ans = 0
for bit in range(2 ** N):
    tmp = [False] * N
    cnt = 0
    for k in range(N):
        if bit & (1 << k):
            tmp[k] = True
            cnt += 1
    # print(tmp)
    check = True
    for k in range(N):
        if tmp[k]:
            res = items[k]
            for r in res:
                x = r[0]
                y = r[1]
                if y == 1:
                    if tmp[x]:
                        continue
                    else:
                        check = False
                else:
                    if tmp[x]:
                        check = False
                    else:
                        continue
    if check:
        ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n=int(input())
l=[[] for i in range(n)]
for i in range(n):
    m=int(input())
    for j in range(m):
        l[i].append(list(map(int,input().split())))
ans=0
it=list(itertools.product([0,1],repeat=n))
for i in it:
    tmp=[]
    for num,j in enumerate(i):
        if j==1:
            for k in l[num]:
                tmp.append(k)
    if all (i[j[0]-1]==j[1] for j in tmp):ans=max(ans,sum(i))
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
arr = [[] for i in range(N+1)]
bm = [0 for i in range(N+1)]
maxs = 0
cnt = 0

def slv(curInd):
  global N,arr,bm,maxs,cnt
  if curInd==N:
    good = True
    for i in range(N+1):
      if good == False:
        break
      if bm[i]:
        for el in arr[i]:
          if bm[el[0]]!=el[1]:
            good = False
            break
    if good == True:
      maxs = max(maxs,cnt)
    cnt += 1
    bm[curInd] = 1
    good = True
    for i in range(N+1):
      if good == False:
        break
      if bm[i]:
        for el in arr[i]:
          if bm[el[0]]!=el[1]:
            good = False
            break
    if good == True:
      maxs = max(maxs,cnt)
    bm[curInd] = 0
    cnt -= 1
  else:
    slv(curInd+1)
    cnt += 1
    bm[curInd] = 1
    slv(curInd+1)
    cnt -= 1
    bm[curInd] = 0

for i in range(N):
  A=int(input())
  for j in range(A):
    arr[i+1].append(list(map(int,input().split())))
slv(1)
print(maxs)

Submission status: Accepted

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

def int2bit(n):
	ret = [0 for i in range(N)]
	i = 0
	while n > 0:
		ret[i] = n % 2
		n = n // 2
		i += 1
	return ret

ans = 0
for i in range(2**N - 1, -1, -1):
	bit = int2bit(i)
	flg = True
	for n in range(N):
		if bit[n] == 0:
			continue
		for x in a[n]:
			if bit[x[0]] != x[1]:
				flg = False
				break
		if not flg:
			break
	if flg:
		ans = max(ans, sum(bit))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
Axyss = []
for i in range(N):
  A = int(input())
  xys = []
  for j in range(A):
    x, y = map(int, input().split())
    x = x-1
    xys.append((x, y))
  Axyss.append((A, xys))
r = 0
for n in range(2**N):
  ss = [0]*N
  for i in range(N):
    if n&(1<<i) != 0:
      ss[i] = 1
  c = ss.count(1)
  if c <= r:
    continue
  ok = True
  for i in range(N):
    s = ss[i]
    A, xys = Axyss[i]
    for x, y in xys:
      if s == 1 and ss[x] != y:
        ok = False
        break
  if ok:
    r = max(r, c)
print(r)

Submission status: Accepted

Solution code:
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
XY = []
for _ in range(N):
    a = int(sys.stdin.buffer.readline())
    xy = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(a)]
    XY.append([(x - 1, y) for x, y in xy])

ans = 0
for choice in itertools.product([0, 1], repeat=N):
    ok = True
    for i in range(N):
        if choice[i] == 0:
            continue
        # choice[i] == 1 のとき正直者
        for x, y in XY[i]:
            ok &= (choice[x] == y) == choice[i]
    if ok:
        ans = max(ans, sum(choice))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [0] * N
xy = [[] for _ in range(N)]
for i in range(N):
  A[i] = int(input())
  xy[i] = [list(map(int, input().split())) for _ in range(A[i])]
  
def nasu(n):
  D = [0] * N
  x = n
  for i in range(N):
    if x & 1:
      D[i] = 1
    x >>= 1
  for i in range(N):
    if D[i] == 0: continue
    for j in range(A[i]):
      if D[xy[i][j][0] - 1] != xy[i][j][1]:
        return False
  return True

ans = 0
for i in range(1, N + 1):
  n = (1 << i) - 1
  while n < (1 << N):
    if nasu(n):
      ans = i
      break
    x = n & -n
    y = n + x
    n = ((n & ~y) // x >> 1) | y
    
print(ans)

Submission status: Accepted

Solution code:
import math

def makelist(n, m):
    return [[[] for _ in range(m)] for _ in range(n)]

# n
# a, b = list(map(int, input().split()))
# s = input()


N = int(input())
A = [0]*(N+1)
x = [[] for _ in range(N+1)]
for i in range(1, N+1):
    A[i] = int(input())
    for _ in range(A[i]):
        a, b = list(map(int, input().split()))
        x[i].append((a, b))

ans = 0
for i in range(1<<N):
    dp = [False]*(N+1)
    flag = True

    ind = 1
    hoge = i
    while i > 0:
        if i % 2 == 1:
            dp[ind] = True
            
        ind += 1
        i //= 2

    
    for i in range(1, N+1):
        if dp[i]:
            for (a, b) in x[i]:
                if b == 1:
                    if not dp[a]:
                        flag = False
                        break
                elif b == 0:
                    if dp[a]:
                        flag = False
                        break
        if not flag:
            break
        

    if flag:
        ans = max(ans, dp.count(True))
print(ans)

Submission status: Accepted

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

ans = 0
for bit in range(2**N):
    ok = True
    P = [-1]*N
    c = 0
    for i in range(N):
        M, XY = data[i]
        if bit & (1<<i):
            c += 1
            if P[i] == 0:
                ok = False
                break
            P[i] = 1
            for x, y in XY:
                if P[x-1] == -1:
                    P[x-1] = y
                elif P[x-1] != y:
                    ok = False
                    break
        else:
            if P[i] == 1:
                ok = False
            P[i] = 0
    if ok:
        ans = max(ans, c)
print(ans)

Submission status: Accepted

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

import itertools


def max_honests(n, statements):
    g = itertools.product((True, False), repeat=n)
    res = 0
    for is_hon in g:
        flag = True
        for i in range(n):
            if is_hon[i]:
                for x, y in statements[i]:
                    if is_hon[x] != y:
                        flag = False
        if flag:
            res = max(res, sum(is_hon))
    return res


def main():
    n = int(input())
    statements = [set() for _ in range(n)]
    for i in range(n):
        a = int(input())
        for _ in range(a):
            x, y = (int(z) for z in input().split())
            statements[i].add((x - 1, bool(y)))
    res = max_honests(n, statements)
    print(res)


if __name__ == "__main__":
    main()