Problem:


Score : 300 points

Problem Statement

There are N people numbered 1 to N. Each of them is either an honest person whose testimonies are always correct or an unkind person whose testimonies may be correct or not.

Person i gives A_i testimonies. The j-th testimony by Person i is represented by two integers x_{ij} and y_{ij}. If y_{ij} = 1, the testimony says Person x_{ij} is honest; if y_{ij} = 0, it says Person x_{ij} is unkind.

How many honest persons can be among those N people at most?

Constraints

All values in input are integers.

1 \leq N \leq 15

0 \leq A_i \leq N - 1

1 \leq x_{ij} \leq N

x_{ij} \neq i

x_{ij_1} \neq x_{ij_2} (j_1 \neq j_2)

y_{ij} = 0, 1

Input

Input is given from Standard Input in the following format:

N
A_1
x_{11} y_{11}
x_{12} y_{12}
:
x_{1A_1} y_{1A_1}
A_2
x_{21} y_{21}
x_{22} y_{22}
:
x_{2A_2} y_{2A_2}
:
A_N
x_{N1} y_{N1}
x_{N2} y_{N2}
:
x_{NA_N} y_{NA_N}

Output

Print the maximum possible number of honest persons among the N people.

Sample Input 1

3
1
2 1
1
1 1
1
2 0

Sample Output 1

2

If Person 1 and Person 2 are honest and Person 3 is unkind, we have two honest persons without inconsistencies, which is the maximum possible number of honest persons.

Sample Input 2

3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0

Sample Output 2

0

Assuming that one or more of them are honest immediately leads to a contradiction.

Sample Input 3

2
1
2 0
1
1 0

Sample Output 3

1



Sample input:
3
1
2 1
1
1 1
1
2 0


Sample output:
2

Submission status: Accepted

Solution code:
N = int(input())

reply = [[-1] * N for _ in range(N)]

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

ans = 0

for i in range(1<<N):
    flag = True
    for j in range(N):
        if i>>j&1 == 1:
            for k in range(N):
                if reply[j][k] == 1:
                    if i>>k&1 == 0:
                        flag = False
                        break
                elif reply[j][k] == 0:
                    if i>>k&1 == 1:
                        flag = False
                        break
            if not flag:
                break
    if flag:
        count = 0
        for j in range(N):
            if i>>j&1:
                count += 1
        ans = max(ans, count)

print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import product
#from collections import defaultdict
input = sys.stdin.readline
def main():
    N = int( input())
    A = [[0]*N for _ in range(N)]
    C = [0]*N
    for i in range(N):
        C[i] = int( input())
        for _ in range(C[i]):
            x, y = map( int, input().split())
            A[i][x-1] = -1+y*2
    ans = 0
    T = [-1, 1]
    for P in product( range(-1, 2, 2), repeat = N):
        check = True
        for i in range(N):
            if P[i] == -1:
                continue
            for j in range(N):
                if A[i][j] == 0:
                    continue
                if A[i][j]*P[i] != P[j]:
                    check = False
                    break
        if check:
            if ans < (sum(P) + N)//2:
                ans = (sum(P) + N)//2
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
def two(x):
	p=bin(x)
	ans=p[2:]
	if len(ans)<n:
		ans="0"*(n-len(ans))+ans
	return ans
n=int(input())
aa=[]
aaa=[]
for i in range(n):
	a=int(input())
	aaa.append(a)
	qw=[]
	for j in range(a):
		x,y=map(int,input().split())
		qw.append([x,y])
	aa.append(qw)
anst=0
for i in range(2**n):
	p=two(i)
	flag=True
	syojiki=[]
	for u in range(n):
		if p[u]=="1":
			syojiki.append(1)
		else:
			syojiki.append(0)
	ans=p.count("1")
	for j in range(n):
		if flag==False:
			break
		if p[j]=="0":
			continue
		for k in range(aaa[j]):
			if aa[j][k][1]==0:
				if syojiki[aa[j][k][0]-1]==1:
					flag=False
					break
				syojiki[aa[j][k][0]-1]=0
			else:
				if syojiki[aa[j][k][0]-1]==0:
					flag=False
					break
				syojiki[aa[j][k][0]-1]=1
	if flag:
		anst=max(anst,ans)
print(anst)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop
from itertools import product
from math import sqrt
from collections import defaultdict
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))
N = int(input())
D = [[-1]*N for i in range(N)]

for i in range(N):
    a = int(input())
    for _ in range(a):
        x, y = inpl()
        D[i][x-1] = y

ans = 0
for X in product(range(2), repeat=N):
    OK = True
    for i in range(N):
        if X[i] == 0:
            continue
        for j in range(N):
            if D[i][j] == -1:
                continue
            if D[i][j] != X[j]:
                OK = False
                break
    if OK:
        ans = max(ans, sum(X))
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
g=[[] for i 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))
N=2**n
ans=0
for i in range(N):
    c_list=[]
    for j in range(n):
        c_list.append((i>>j)%2)
    check=1
    for j in range(n):
        if c_list[j]:
            for z in g[j]:
                if not c_list[z[0]]==z[1]:
                    check=0
    if check:
        ans=max(ans,sum(c_list))
print(ans)

Submission status: Accepted

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

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


def bc(x):
    return bin(x).count("1")

ans = 0
for i in range(2**n):
    is_ok = True
    for j in range(n):
        if (i>>j) & 1:
            for x, y in xys[j]:
                if ((i>>(x-1)) & 1) != y :
                    is_ok = False
                    break
    if is_ok:
        cnt = bc(i)
        if ans < cnt:
            ans = cnt
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

c = 0
check = [0]*n
ans = 0
while c < (2 ** n):
    count = 0
    wari = c
    while wari > 0:
        #print(count,wari)
        check[count] = ((wari % 2 != 0) + 0)
        wari //= 2
        count += 1
    c += 1
    wari = 0
    #karikotae = 0
    mujyun = 0

    for v in check:
        if v == 0:
            wari += 1
            continue
        for a,b in ls[wari]:
            a -= 1
            if b != check[a]:
                mujyun = 1
                break
        if mujyun != 0:
            break
        wari += 1
    if mujyun != 0:continue
    else:ans = max(ans,sum(check))
print(ans)

Submission status: Accepted

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

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


def check(_ts):
    _ts = list(_ts)
    ts = list(_ts[:])
    a = [-1] * n
    while ts:
        t = ts.pop()
        for i in range(n):
            if a[i] == -1:
                a[i] = graph[t][i]
                if graph[t][i] == 1:
                    ts.append(i)
                    _ts.append(i)
            if graph[t][i] == -1:
                pass
            elif a[i] != graph[t][i]:
                return False
    for t in _ts:
        if a[t] == 0:
            return False
    return True


for m in range(n, 0, -1):
    for p in itertools.combinations(range(n), r=m):

        if check(p):
            print(m)
            exit()
print(0)

Submission status: Accepted

Solution code:
n = int(input())
say = [[] for _ in range(n)]
for i in range(n):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split())
        say[i].append([x, y])
# print(say)
ans = 0
for i in range(1 << n):
    for j in range(n):
        count_j = True
        if i & 1 << j:
            for say_j in say[j]:
                if say_j[1] == 1:
                    if not i & 1 << (say_j[0] - 1):
                        count_j = False
                        break
                else:
                    if i & 1 << (say_j[0] - 1):
                        count_j = False
                        break
        if not count_j:
            break
    if  count_j:
        cnt = 0
        for j in range(n):
            if i & 1 << j:
                cnt += 1
        ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
arr = []
for i in range(n):
    A = int(input())
    t = []
    for _ in range(A):
        t.append(list(map(int, input().split())))
    arr.append(t)
ans = 0
for i in range(2 ** n):
    tmp = ''
    for k in range(n):
        if 1 & i>>k:
            tmp = '1' + tmp
        else:
            tmp = '0' + tmp
    flg = True
    for k in range(n):
        if tmp[k] == '1':
            for l in arr[k]:
                if (l[1] == 1 and tmp[l[0]-1] == '1') or (l[1] == 0 and tmp[l[0]-1] == '0'):
                    continue
                else:
                    flg = False
    if flg:
        ttmp = 0
        for k in tmp:
            ttmp += int(k)
        if ans < ttmp:
            ans = ttmp
print(ans)

Submission status: Accepted

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

# 引数はNが正直者か嘘つきかの組み合わせを表すリスト
# 戻り値は矛盾があるか、ないか
def check(arr):
    for idx, a in enumerate(A):
        # 嘘つきだと判断されているインデックス番号の人物は無視
        if arr[idx] == 0:
            continue
        # 一つ一つの証言をチェックする
        for x, y in a:
            if arr[x-1] != y:
                return False
    return True

all_comb = []
for i in range(2**N):
    comb = []
    for j in range(N):
        if (i >> j) & 1:
            comb.append(1)
        else:
            comb.append(0)
    all_comb.append(comb)
ret = 0
for comb in all_comb:
    if check(comb):
        ret = max(ret, sum(comb))

print(ret)

Submission status: Accepted

Solution code:
import copy
import itertools
def main():
    n = int(input())
    m = []
    for i in range(n):
        a = int(input())
        am = []
        for j in range(a):
            am.append(tuple(map(int,input().split())))
        m.append(copy.deepcopy(am))
    it = itertools.product([0,1],repeat=n)
    ans = 0
    for i in it:
        flag = True
        for x in range(len(i)):
            if i[x] == 1:
                if not all([k==i[j-1] for j,k in m[x]]):
                    flag = False
                    break
        if flag:
            ans = max([ans,sum(i)])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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

ans = 0
for i in range(1<<n):
    l = [i&(1<<j)!=0 for j in range(n)]
    f = True
    for j in range(n):
        if l[j]:
            if not all(G[j][k] == -1 or l[k] == G[j][k] for k in range(n)):
                f = False
                break
    if f:
        ans = max(ans, sum(l))

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
a_xy = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = [int(item) for item in input().split()]
        a_xy[i].append((x-1, y))
    
ans = 0
# Decide true or not
for i in range(2**n):
    ok = True
    for j in range(n):
        # Who Saying true
        if i & (1 << j):
            for x, y in a_xy[j]:
                if y == 1:
                    if not (i & (1 << x)):
                        ok = False
                        break
                else:
                    if i & (1 << x):
                        ok = False
                        break
        if not ok:
            break
    if ok:
        ans = max(ans, bin(i).count("1"))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
lis = [[] for _ in range(N)]

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

ans = 0
for i in range(2**N):
    s = True
    person =[]
    for _ in range(N):
        person.append(i%2)
        i = i // 2
    for j in range(N):
        if person[j]==1:
            for k in lis[j]:
                if person[k[0]-1] != k[1]:
                    s = False
                    break
            if not s:
                break
    if s and ans < person.count(1):
        ans = person.count(1)
print(ans)

Submission status: Accepted

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

po = {}

for i in range(n):
  ai = int(input())
  po_dict = {}
  for j in range(ai):
    x,y = map(int, input().split())
    po_dict[x-1]=y
  po[i]=po_dict

#print(po)
  
def check(lis):
  for i, yi in enumerate(lis):
    if yi==1:
      #print(po[i])
      for k,v in po[i].items():
        if lis[k]!=v:
          return False
  return True

ys=[0,1]
max_t=0
for lis in itertools.product(ys,repeat=n):
  if check(lis):
    if max_t <sum(lis):
      max_t = sum(lis)

print(max_t)

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = [0]*n
z = [ [] for i in range(n) ]
for i in range(n):
    aa = inn()
    a[i] = aa
    for j in range(aa):
        x,y = inm()
        x -= 1
        z[i].append((x,y))

mx = 0
for i in range(2**n):
    honest = [ ((i>>j)&1 == 1) for j in range(n) ]
    nbits = sum([ ((i>>j)&1) for j in range(n) ])
    ok = True
    for j in range(n):
        if not honest[j]:
            continue
        for u in z[j]:
            x,y = u
            if honest[x] and y==0 or not honest[x] and y==1:
                ok = False
                break
        if not ok:
            break
    #print("i {} honest {} nbits {} ok {}".format(i,honest,nbits,ok))
    if ok and nbits>mx:
        mx = nbits

print(mx)

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):
    XY[i].append(list(map(int,input().split())))

ans=0
for k in range(2**N):
  hu=list(map(int,bin(k)[2:].zfill(N)))
  j=0
  for i in range(len(XY)):
    if hu[i]==1:
      for x,y in XY[i]:
        if hu[x-1]!=y:
          j=1
  if j==0:
    ans=max(ans,hu.count(1))
print(ans)

Submission status: Accepted

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

N = int(input().split()[0])
# a_list = list(map(int, input().split()))
a_list = []
xy_list_list = []

for _ in range(N):
    a = int(input().split()[0])
    a_list.append(a)
    xy_list = []
    for _ in range(a):
        x, y = list(map(int, input().split()))
        xy_list.append((x, y))
    xy_list_list.append(xy_list)

# 2 ** 3 パターン
p_list = list(itertools.product([0, 1], repeat=N))
max_c = 0

for pattern in p_list:  # 2 ** 15
    is_ok = True
    for i in range(N):  # 15
        if pattern[i] == 0:
            # 真偽不明
            continue
        for xy in xy_list_list[i]:  # 15
            x, y = xy
            x = x - 1
            if pattern[x] != y:
                # 矛盾
                is_ok = False
                break
        if not is_ok:
            # 矛盾
            break
    if is_ok:
        max_c = max(max_c, sum(pattern))

ans = max_c
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = []
X = [[] for _ in range(N)]
for i in range(N):
    a = int(input())
    A.append(a)
    for j in range(a):
        X[i].append(list(map(int,input().split())))
ans = 0
for i in range(2**N):
    flag = False
    for j in range(N):
        if ((i >> j) & 1):
            for k in range(A[j]):
                if X[j][k][1]==1 and not ((i>>X[j][k][0]-1)&1):
                    flag = True
                    break
                if X[j][k][1]==0 and ((i>>X[j][k][0]-1)&1):
                    flag = True
                    break
        if flag:
            break
    if not flag:
        tmp = 0
        for j in range(N):
            if ((i >> j) & 1):
                tmp += 1
        ans = max(tmp,ans)
print(ans)

Submission status: Accepted

Solution code:
import queue
import math
import copy
"""
N = int(input())
#S = input()
# (N,M) = (int(i) for i in input().split(" "))
# A = [int(i) for i in input().split()]
A = []
for i in range(N):
	A.append(int(input()))

print(A)

"""
P = 0
N = int(input())
ans = 0
mp =[]
for i in range(N):
	a = int(input())
	mp.append([])
	for j in range(a):
		(s,t) = (int(i) for i in input().split(" "))
		mp[-1].append([s-1,t])
#print(mp)
for P in range(1 << N):
	p_num = P
	pp = []
	for i in range(N):
		pp.append(p_num&1)
		p_num >>= 1
	p_len = sum(pp)
	##print(pp)
	ch = True
	for i in range(N):
		for info in mp[i]:
			if pp[i]==1 and (pp[info[0]] != info[1]):
				ch = False
				break
	#print(ch)
	if ch and p_len > ans:
		ans = p_len
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
from itertools import count
from functools import lru_cache
from collections import defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    N = ii()
    P = [tuple(tuple(mis()) for _ in range(ii())) for __ in range(N)]
    ho = [None] * N
    ans = 0
    for b in range(2**N):
        for i in range(N):
            ho[i] = bool(b & (1<<i))
        if ans >= sum(ho):
            continue
        flag = True
        for i in range(N):
            if not flag:
                break
            if ho[i]:
                for x, y in P[i]:
                    x -= 1
                    if bool(y) !=  ho[x]:
                        flag = False
                        break
        
        if not flag:
            continue

        ans = sum(ho)
    print(ans)




main()

Submission status: Accepted

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

ans = 0
for i in range(1<<N):
    h=[]
    for j in range(N):
        if(i&(1<<j)):
            h.append(j)

    for j,x,y in T:
        if(j in h):
            if(not((x in h)==y)):
                break
    else:
        ans = max(ans,len(h))

print(ans)

Submission status: Accepted

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


def main():
    N = int(input())
    X = []
    for i in range(N):
        a = int(input())
        X.append([])
        for j in range(a):
            x, y = [int(x) for x in input().split()]
            X[i].append([x, y])

    ans = 0
    for i in range(2 ** N):
        tmp = 0
        is_mujun = False
        for j in range(N):
            if i >> j & 1:
                tmp += 1
                for k in X[j]:
                    if k[1] == 1:
                        if not i >> (k[0] - 1) & 1:
                            is_mujun = True
                            break
                    else:
                        if i >> (k[0] - 1) & 1:
                            is_mujun = True
                            break
                    if is_mujun:
                        break
        if not is_mujun:
            ans = max(ans, tmp)

    print(ans)







if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
for pattern in range(2 ** N):
    p = pattern
    numHonest = 0
    correct = True
    for i in range(N):
        if p & 1:
            numHonest += 1
            for evid in evids[i]:
                if (pattern >> (evid[0]-1)) & 1 != evid[1]:
                    correct = False
                    break
        #else:
        #    for evid in evids[i]:
        #        if (pattern >> (evid[0]-1)) & 1 == evid[1]:
        #            correct = False
        #            break
        if not correct:
            break
        p >>= 1
    if correct:
        ans = ans if ans > numHonest else numHonest
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
time = [0 for _ in range(n)]
def nex(time):
  for i in range(n):
    if time[i] == 0:
      time[i] = 1
      return time
      break
    else:
      time[i] = 0
  else:
    return 'over'
#print(nex([0,0,0]),nex([1,1,1]),nex([1,1,0]))
wit = []
for i in range(n):
  a = int(input())
  add = [2 for _ in range(n)] 
  add[i] = 1
  for _ in range(a):
    x,y = map(int,input().split())
    x -= 1
    add[x] = y
  wit.append(add)
can = []
while time != 'over':
  for i in range(n):
    if time[i] == 1:
      for j in range(n):
        if wit[i][j] == 1 - time[j]:
          break
      else:
        continue
      break
  else:
    can.append(sum(time))
  time = nex(time)
#print(wit)
print(max(can))
#print(can)

Submission status: Accepted

Solution code:
N = int(input())

shougen = []

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


m = 0
for i in range(2 ** N):
    flag = True
    for j in range(N):
        if (i >> j) & 1 == 1:
            for shou in shougen[j]:
                if shou[1] != (i >> shou[0]) & 1:
                    flag = False

    if flag:
        wa = 0
        for j in range(N):
            wa += (i >> j) & 1
        m = max(m, wa)

print(m)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
a = [None] * n
x = [[None] * 15 for _ in range(n)]
y = [[None] * 15 for _ 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

m = 0
for b in range(1 << n):
    f = True
    for i in range(n):
        if b >> i & 1 == 0:
            continue
        for j in range(a[i]):
            if y[i][j] == 1:
                if b >> x[i][j] & 1 == 0:
                    f = False
                    break
            else:
                if b >> x[i][j] & 1 == 1:
                    f = False
                    break

    if f:
        m = max(m, sum(map(int, bin(b)[2:])))

print(m)

Submission status: Accepted

Solution code:
N = int(input())
xs = [[] for i in range(N)]
for i in range(N):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        xs[i].append((x-1,y))
ans = 0
for b in range(1<<N):
    mujun = False
    for k,z in enumerate(xs):
        for x,y in z:
            if b&(1<<k):
                if b&(1<<x):
                    if y==0:
                        mujun = True
                else:
                    if y==1:
                        mujun = True
            if mujun:
                break
        if mujun:
            break
    if not mujun:
        tmp = bin(b).count('1')
        ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
import itertools

N = int(input())
A = []
lst = [[] for _ in range(N)]

for i in range(N):
	A.append(int(input()))
	for j in range(A[-1]):
		a, b = map(int, input().split())
		lst[i].append([a, b])
		
ans = 0
		
for cur in itertools.product(list(range(2)), repeat = N):
	flg = 0
	for i in range(N):
		if flg: break
		if cur[i] == 0: continue
		for j in range(len(lst[i])):
			if not cur[lst[i][j][0] - 1] == lst[i][j][1]:
				flg = 1
				break
	if not flg:
		ans = max(ans, sum(cur))
		
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
g = [[[],[]] for _ in range(n)]
for i in range(n):
  a = int(input())
  g[i]=[tuple(map(int,input().split())) for _ in range(a)]
ans = 0
for num in range(1<<n):
  p = [j for j in range(n) if num&(1<<j)]
  fl = 0
  for v in p:
    for x,y in g[v]:
      if bool(num&(1<<(x-1))) != y:
        fl = 1
        break
    if fl:
      break
  else:
    if ans < len(p):
      ans = len(p)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N = int(input())
A = [[] 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 = x - 1
        A[i].append([x, y])


ans = 0
flg = False
for pattern in product([0, 1], repeat=N):
    Y = list(pattern)
    Truth = set()

    for i, p in enumerate(pattern):
        if p == 0:
            continue

        for j, yi in A[i]:
            if Y[j] == yi:
                continue
            else:
                flg = True
                break

        if flg:
            flg = False
            break

    else:
        ans = max(ans, sum(pattern))


print(ans)

Submission status: Accepted

Solution code:
import sys
n = int(input())
maps = []
for i in range(n):
    ud = []
    a = int(sys.stdin.readline().rstrip())
    for j in range(a):
        x, y = map(int, sys.stdin.readline().split())
        ud.append([x, y])
    maps.append(ud)
result = 0
for i in range(2**n)[::-1]:
    bf = False
    for j in range(n):
        if (i >> j) &1 > 0:
            for k in maps[j]:
                if (i >> (k[0]-1))&1 != k[1]:
                    bf = True
                    break
        if bf:
            break
    if bf == False:
        rc = bin(i).count('1')
        if rc > result:
            result = rc


print(result)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect, string
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**7)
inf = float('inf')
mod = 10**9+7
ans = 0 ;count = 0 ;pro = 1

n=int(input())
A=[[] for i in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        A[i].append(tuple(map(int,input().split())))
for i in range(2**n):
    tr=set()
    fr=set()
    f=1
    count=0
    for k in range(n):
        if i>>k & 1:
            if (k+1) in fr:
                f=0
            tr.add(k+1)
            count+=1
            for xi,yi in A[k]:
                if yi:
                    if xi in fr:
                        f=0
                    tr.add(xi)
                else:
                    if xi in tr:
                        f=0
                    fr.add(xi)
        else:
            if (k+1) in tr:
                f=0
            fr.add(k+1)
    if f:
        ans=max(ans,count)
print(ans)

Submission status: Accepted

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



N = int(input())

T = [[]for i in range(N)]

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


ans = 0
def judge():
	global ans
	f=True
	for i in range(N):
		if l[i]==1:
			for g in T[i]:
				if l[g[0]] != g[1]:
					f=False
					break

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





def dfs(x):
	if x>=N:
		judge()
		return

	l[x] = 1
	dfs(x+1)
	l[x] = 0
	dfs(x+1)

l=[0]*N
dfs(0)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n=int(input())
l=[[-1 for i in range(n)] for j in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        l[i][x-1] = y
m=0
for v in list(itertools.product(range(2), repeat=n)):
    f = True
    for i in range(n):
        if v[i]==1:
            for j in range(n):
                if l[i][j] == -1 or v[j]==l[i][j]:
                    continue
                else:
                    f=False
                    break
    if f:
        m = max(sum(v),m)
print(m)

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[-1 for _ in range(N)] for i in range(N)]
    for i in range(N):
        a = int(input())
        for j in range(a):
            x, y = map(int, input().split())
            A[i][x-1] = y

    ans = 0
    for i in range(2 ** N):
        bit = format(i, "b").zfill(N)
        #print(bit)
        one = 0
        flag = True
        for j in range(N):
            if bit[j] == "1":
                for k in range(N):
                    if A[j][k] >= 0 and A[j][k] != int(bit[k]):
                        flag = False
                        break
                one += 1    
        if flag: ans = max(ans, one)

    print(ans)

    return 0

if __name__ == "__main__":
    solve()

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):
        p,q=[int(k) for k in input().split()]
        xy[i].append([p-1,q])
ans=0
for i in range(2**n):
    s=bin(i)[2:].rjust(n,'0')
    r,t=0,0
    for j in range(n):
        if s[j]=="1":
            p,q=0,0
            for x,y in xy[j]:
                p+=1
                if s[x]!=str(y):
                    break
                q+=1
            if p!=q:
                break
            else:
                r+=1
        else:
            r+=1
        t+=1
    if r==n:
        ans=max(ans,s.count("1"))
        
            
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
S = defaultdict(dict)
for i in range(N):
    Ai = int(input())
    for j in range(Ai):
        xi, yi = map(int, input().split())
        S[i][xi - 1] = yi

ans = 0
for i in range(1 << N):
    possible = True
    c = 0
    for j in range(N):
        if i >> j & 1:
            c += 1
            for xi, yi in S[j].items():
                if i >> xi & 1 != yi:
                    possible = False
                    break
    if possible:
        ans = max(ans, c)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

#print(a)

q = 2 ** n
ans = 0
for i in range(q):
    d = list(map(int, list(str(bin(q + i))[2:])))
    check = 0
    for j, x in enumerate(d[1:]):
        if x == 1:
            for c, b in a[j]:
                if d[c+1] != b:
                    check = 1
                    break
    if check == 1:
        continue
    else:
        ans = max(ans, d.count(1) - 1)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [0]*N
x = [0]*N
y = [0]*N
for _ in range(N):
    a = int(input())
    A[_] = a
    x[_] = [0]*a
    y[_] = [0]*a
    for __ in range(a):
        x[_][__],y[_][__] = map(int,input().split())
        x[_][__] -= 1

def bi(x):
    i = 0
    o = [0]*N
    while x > 0:
        o[i] = x % 2
        x //= 2
        i += 1
    return o

def b(o):
    for i in range(N):
        # 不親切な人間の証言は真偽不明なので無視する
        if o[i] == 0:
            continue
        # 正直者の証言は矛盾がなければ確実に正しい
        for j in range(A[i]):
            k = x[i][j]
            if o[k] != y[i][j]:
                return -1
    return sum(o)

a = 0
for i in range(2 ** N):
    # 2**N通りのそれぞれについて矛盾がないか確かめる
    o = bi(i)
    a = max(a,b(o))

print(a)