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())
a = list()
x = []
y = []
for i in range(n):
    A = int(input())
    a.append(A)
    x_ = []
    y_ = []
    for j in range(A):
        X,Y = map(int,input().split())
        x_.append(X)
        y_.append(Y)
    x.append(x_)
    y.append(y_)
mat = [0 for i in range(2**n)]
for i in range(2**n): #一つの可能性
    flag = True
    binary = format(i,"b")
    binary = (n-len(binary))*"0"+binary
    for j in range(n):#一人一人について正直者か見る
        if flag and  len(binary) > j and binary[j] =="1":
            for k in range(a[j]):#一人の証言について順に見ていく
                if flag and len(binary) > x[j][k]-1 and binary[x[j][k]-1] != str(y[j][k]):
                    flag = False
                    break
    if flag:
        mat[i] = 1
ans = 0
for i in range(2**n):
    if mat[i] == 1:
        binary =format(i,"b")
        count = 0
        for j in range(len(binary)):
            count += int(binary[j])
        ans = max(ans,count)
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

n = int(sys.stdin.readline().rstrip())
xy = [[] for _ in range(n)]
for i in range(n):
    a = int(sys.stdin.readline().rstrip())
    for _ in range(a):
        x, y = map(int, sys.stdin.readline().split())
        xy[i].append((x - 1, y))

def main():
    comb = (np.arange(2 ** n).reshape(-1, 1) >> np.arange(n) & 1).astype(np.bool)
    for i in range(n):
        for x, y in xy[i]:
            bl = ~comb[:, i] | (comb[:, x] == np.bool(y))
            comb = comb[bl]
    
    ans = np.amax(np.sum(comb, axis=1))
    return ans

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

Submission status: Accepted

Solution code:
n = int(input())
l = [] 
for i in range(n):
	list = [" "] * n
	a = int(input())
	for j in range(a):
		data = input().split(" ")
		x = int(data[0])
		y = data[1]
		list[x-1] = y
	l.append(list)
m = 0
for i in range(2**n):
	s = bin(i)
	s = s[2:]
	s = s.zfill(n)
	ll = []
	th = [" "] * n
	for j in range(n):
		if int(s[j]) == 1:
			ll.append(l[j])
			th[j] = "1"
		elif int(s[j]) == 0:
			th[j] = "0" 
	te = 0
	for j in range(n):
		for k in range(len(ll)):
			if ll[k][j] == "1" or ll[k][j] == "0":
				if ll[k][j] != th[j]:
					te = 1
	if te == 0:
		f = len(ll)
		if f > m:
			m = f
print(m)

Submission status: Accepted

Solution code:
N = int(input())
xy = [[-1]*N for i in range(N)]

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

honest = 0
for i in range(2 ** N): #bit全探索
    count = 0
    flag = True
    for j in range(N): #人数分シフトする必要がある
        if((i >> j) & 1): #ビットシフト部(bit全探索に必ず必要)
            count += 1
            for k in range(N): #最大N人いるので．
                if xy[j][k] == -1:
                    continue
                elif ((i >> k) & 1) != xy[j][k]: #bit全探索でj人目を正直とした人が，証言で正しいことを言っているか
                    flag = False
    if flag:
        honest = max(honest, count)

print(honest)

Submission status: Accepted

Solution code:
from itertools import combinations, count

n = int(input())
r = range(n)
a = [(set(), set()) for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y].add(x - 1)
ans = next(i for i in count(n, - 1) for x in map(set, combinations(r, i))
           if all(a[j][0].isdisjoint(x) and a[j][1] < x for j in x))
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations, count

n = int(input())
r = range(n)
a = [(set(), set()) for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y].add(x - 1)
ans = next(i for i in count(n, - 1) for x in combinations(r, i)
           if all(a[j][0].isdisjoint(x) and a[j][1].issubset(x) for j in x))
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
data = [[] for i in range(N+1)]

for i in range(N):
  a = I()
  for j in range(a):
    data[i].append(IL())

ans = 0
for i in range(1 << N):
  TF = [-1]*N
  cnt = 0
  for j in range(N):
    if ((i >> j) & 1) == 1: #j人目が正しい
      TF[j] = True
      cnt += 1
    else:
      TF[j] = False
  
  for k in range(N):
    if TF[k] == True:
      for x,y in data[k]:
        if TF[x-1] == y:
          continue
        else:
          break
      else:
        continue
      break
  else:
    ans = max(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
I=int
i=input
n=I(i())
a=eval('[i().split()for _ in"_"*I(i())],'*n)
print(max(all(I(y)==i>>I(x)-1&1for j,t in enumerate(a)if i>>j&1for x,y in t)*bin(i).count('1')for i in range(1<<n)))

Submission status: Accepted

Solution code:
from itertools import combinations, count

n = int(input())
r = range(n)
a = [(set(), set()) for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y].add(x - 1)
r = next(i for i in count(n, - 1) for x in map(set, combinations(r, i))
         if all(a[j][0].isdisjoint(x) and a[j][1] < x for j in x))
print(r)

Submission status: Accepted

Solution code:
import sys

n = int(sys.stdin.readline().rstrip())
xy = [[] for _ in range(n)]
for i in range(n):
    a = int(sys.stdin.readline().rstrip())
    for j in range(a):
        x, y = map(int, sys.stdin.readline().split())
        xy[i].append((x-1, y))

def main():
    ans = 0
    for comb in range(2 ** n):
        cnt = 0
        for i in range(n):
            if comb >> i & 1 ^ 1:
                continue
            for x, y in xy[i]:
                if comb >> x & 1 ^ y:
                    break
            else:
                cnt += 1
                continue
            break
        else:
            ans = max(ans, cnt)
    return ans
                
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
i=input
n=int(i())
a=eval('[i().split()for _ in"_"*int(i())],'*n)
print(max(all(int(y)==i>>int(x)-1&1for j,t in enumerate(a)if i>>j&1for x,y in t)*bin(i).count('1')for i in range(2**n)))

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())
    for j in range(A[i]):
        a,b = list(map(int,input().split()))
        a -= 1
        xy[i].append([a,b])

ans = 0
for i in range(1<<N):
    state = [False] * N
    tmp = i
    for j in range(N):
        state[j] = (tmp%2==1)
        tmp = tmp//2
    
    flag = True
    for j in range(N):
        if state[j]:
            for k in range(A[j]):
                if state[xy[j][k][0]] != xy[j][k][1]:
                    flag = False
                    break
                
            if not flag:
                break
    if flag:
        ans = max(ans,sum(state))
        
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    a=sorted([random.randint(0,5) for _ in range(n)])[::-1]
    return n,a

show_flg=False
show_flg=True

n=I()
ans=0
c=[[] for i in range(n)]
for i in range(n):
    a=I()
    for j in range(a):
        x,y=LI()
        x-=1
        c[i].append((x,y))

for bit in range(2**n):
    t=[1 if (bit>>i)&1 else 0 for i in range(n)]
    flg=True    
    for i in range(n):
        if t[i]==1:
            for x,y in c[i]:
                if t[x]!=y:
                    flg=False
    if flg:
        ans=max(ans,sum(t))
    
print(ans)

Submission status: Accepted

Solution code:
import copy

def main():
    n = int(input())

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

    ans = 0
    for bit in range(0, 2**n):
        temp_ans = 0
        flag = True

        temp_table = []
        b = 1
        for i in range(n):
            if b & bit:
                temp_table.append(table[i][:])
                temp_table[-1][i] = 1
                temp_ans += 1
                for j in range(n):
                    temp_j_bit = bit >> j & 1
                    table_i_j = table[i][j]
                    if table_i_j == -1:
                        continue
                    elif temp_j_bit != table_i_j:
                        flag = False
            b <<= 1
        if temp_table and flag:
            temp_table_t = list(zip(*temp_table))
            for j, t in enumerate(temp_table_t):
                if 1 in t and 0 in t:
                    flag = False
        if flag:
            ans = max(ans, temp_ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
i=input
n=int(i())
a=eval('[list(map(int,i().split()))for _ in"_"*int(i())],'*n)
print(max(all(y==i>>x-1&1for j,t in enumerate(a)if i>>j&1for x,y in t)*bin(i).count('1')for i in range(2**n)))

Submission status: Accepted

Solution code:
n = int(input())
a =[0]*n
x = [[0] *n for i in range(n)]
y = [[0] *n for i in range(n)]
ans = []
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
        
ishonest= [-1]*n + [0]
def check(ishonest):
    for i in range(n):
        if not ishonest[i]:continue
        for j in range(a[i]):
            if y[i][j] == 1 and ishonest[x[i][j]] == 0:
                return False
            if y[i][j] == 0 and ishonest[x[i][j]] == 1:
                return False
    return True

def dfs(now,h_or_not= -1):
    ishonest[now] = h_or_not
    if now == n-1:
        if check(ishonest):
      
            return sum(ishonest)+1
        else:
            return 0
  
    return max(dfs(now+1,0),dfs(now+1,1))

print(dfs(-1))

Submission status: Accepted

Solution code:
def c():
  from math import log2

  def get_ones(n):
    while n:
      k = n & -n
      yield int(log2(k))
      n ^= k

  N = int(input())
  guys = []
  for i in range(N):
    guys.append([])
    A = int(input())
    for j in range(A):
      guys[-1].append(tuple(map(int,input().split())))
  guys = guys[::-1]
  
  ans = 0
  for i in range(2**N):
    cnt = 0
    for j in get_ones(i):
      cnt += 1
      for k in range(len(guys[j])):
        if (int(i & (1 << (N - guys[j][k][0]))) != 0) != guys[j][k][1]:
          break
      else:
        continue
      break
    else:
      ans = max(cnt,ans)
  print(ans)
c()

Submission status: Accepted

Solution code:
n = int(input())
len_a = [0]*n
x = [0]*n
y = [0]*n
for i in range(n):
    len_a[i]=int(input())
    x[i]=[0]*len_a[i]
    y[i]=[0]*len_a[i]
    for j in range(len_a[i]):
        x[i][j], y[i][j] = map(int,input().split())
ans = 0
for i in range(2**n):
    honest_list = bin(i)[2:].zfill(n)
    honest_all = True
    for j in range(n):
        if honest_list[j]=='1':
            for k in range(len(x[j])):
                if str(y[j][k]) != honest_list[x[j][k]-1]:
                    honest_all = False
                    break
        if honest_all==False:
            break
    if honest_all:
        if ans < str(honest_list).count('1'):
            ans = str(honest_list).count('1')
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

n = int(sys.stdin.readline().rstrip())
x = []
y = []
for i in range(n):
    a = int(sys.stdin.readline().rstrip())
    xy = [sys.stdin.readline().split() for _ in range(a)]
    if not xy:
        x.append(None)
        y.append(None)
        continue
    xi, yi = np.array(xy, np.int64).T
    x.append(xi-1)
    y.append(yi)

def main():

    ans = 0
    for comb in range(2 ** n):
        cnt = 0
        for i in range(n):
            if not comb >> i & 1:
                continue
            if x[i] is None:
                cnt += 1
                continue
            if np.count_nonzero(comb >> x[i] & 1 ^ y[i]):
                break
            cnt += 1
        else:
            ans = max(ans, cnt)
    return ans
                
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

n = int(sys.stdin.readline().rstrip())
A = []
x = []
y = []
for i in range(n):
    a = int(sys.stdin.readline().rstrip())
    A.append(a)
    if a == 0:
        x.append(None)
        y.append(None)
        continue
    xi, yi = np.array([sys.stdin.readline().split() for _ in range(a)], dtype=np.int64).T
    x.append(xi-1)
    y.append(yi)

def main():
    ans = 0
    for comb in range(2 ** n):
        cnt = 0
        for i in range(n):
            if not comb >> i & 1:
                continue
            if not A[i]:
                cnt += 1
                continue
            if np.count_nonzero(comb >> x[i] & 1 ^ y[i]):
                break
            cnt += 1
        else:
            ans = max(ans, cnt)
    return ans
                
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
A = [0 for _ in range(20)]
x = [[0 for _ in range(20)] for _ in range(20)]
y = [[0 for _ in range(20)] for _ in range(20)]
N = int(input())
for i in range(N):
    A[i] = int(input())
    for j in range(A[i]):
        temp_x, temp_y = map(int, input().split(' '))
        x[i][j] = temp_x
        y[i][j] = temp_y
res = 0
for i in range(2 ** N):
    flg = True
    for j in range(N):        
        if(not ((i >> j) & 1)): continue
        for a in range(A[j]):
            if(((i >> (x[j][a] - 1)) & 1) ^ y[j][a]):
                flg = False        
    if(flg):
        res = max(res, str(bin(i)).count('1'))
            
print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, = map(int, input().split())
rs = []
for _ in range(N):
    A, = map(int, input().split())
    ts, fs = set(), set()
    for _ in range(A):
        x, y = map(int, input().split())
        if y:
            ts.add(x-1)
        else:
            fs.add(x-1)
    rs.append((ts, fs))
r = 0
for i in range(2**N):
    ok = True
    c = 0
    for j in range(N):
        if (i>>j) % 2:
            for t in rs[j][0]:
                if not (i>>t) % 2:
                    ok = False
            for t in rs[j][1]:
                if (i>>t) % 2:
                    ok = False
            c += 1
    if ok:
        r = max(r, c)
print(r)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, = map(int, input().split())
rs = []
for _ in range(N):
    A, = map(int, input().split())
    ts, fs = set(), set()
    for _ in range(A):
        x, y = map(int, input().split())
        if y:
            ts.add(x-1)
        else:
            fs.add(x-1)
    rs.append((ts, fs))
r = 0
for i in range(2**N):
    i = i+2**N
    bi = bin(i)[3:]
    ok = True
    for j in range(N):
        if int(bi[j]):
            for t in rs[j][0]:
                if not int(bi[t]):
                    ok = False
            for t in rs[j][1]:
                if int(bi[t]):
                    ok = False
    if ok:
        r = max(r, bi.count("1"))
print(r)

Submission status: Accepted

Solution code:
import math


def inputIntList():
    return [int(s) for s in input().split()]


def inputInt():
    return int(input())


def main():
    N = inputInt()
    A = [[] for _ in range(N)]
    for i in range(N):
        for _ in range(inputInt()):
            A[i].append(inputIntList())
    ret = 0
    for i in range(2 ** N):
        bits = [i >> j & 1 for j in range(N)]
        for i, a in enumerate(A):
            if bits[i] == 0:
                continue
            for x, y in a:
                # print(bits, bits[x - 1], y)
                if bits[x - 1] == y:
                    continue
                break
            else:
                continue
            break
        else:
            ret = max(ret, sum(bits))
    return ret


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
import sys
# import numpy as np

n = int(sys.stdin.readline().rstrip())
xy = [[] for _ in range(n)]

for i in range(n):
    a = int(sys.stdin.readline().rstrip())
    for j in range(a):
        x, y = map(int, sys.stdin.readline().split())
        xy[i].append((x-1, y))

# xy = np.array(xy)
# x, y = xy[:, :].T
# x = x.T 
# y = y.T

def main():
    ans = 0
    for comb in range(2 ** n):
        cnt = 0
        ok = True
        for i in range(n):
            if not comb >> i & 1:
                continue
            for x, y in xy[i]:
                if comb >> x & 1 ^ y:
                    ok = False
                    break
            if ok:
                cnt += 1
            else:
                break
        else:
            ans = max(ans, cnt)
    return ans
                
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

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

import itertools
import numpy as np

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

A = np.array(list(itertools.product([0,1],repeat=N)),np.bool)

for i in range(N):
    for x,y in XY[i]:
        bl = (~A[:,i]) | ((A[:,x]) == bool(y))
        A = A[bl]

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

Submission status: Accepted

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

res = 0
for k in range(1 << N):
    bits = [(k >> i) & 1 for i in range(N)]
    flag = True
    for i, a in enumerate(A):
        if bits[i] == 0:
            continue
        for x, y in a:
            if bits[x - 1] == y:
                continue
            flag = False
    if flag:
        res = max(res, sum(bits))

print(res)

Submission status: Accepted

Solution code:
import re
n=int(input())
A=[]
for i in range(n):
    B=["."]*n
    for x,y in [list(map(int,input().split())) for k in range(int(input()))]:
        B[x-1]=str(y)
    A.append("".join(B))
ans=0
for i in range(2**n):
    num=format(i,"b").zfill(n)
    cnt,flag=0,1
    for k,j in enumerate(num):
        result=re.search(r"".join(A[k]),num)
        if result is not None and j=="1":
            cnt +=1
        elif (result is not None and j=="0") or (result is None and j=="1"):
            flag=0
            break
    if flag:
        ans=max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
import re
n=int(input())
A=[]
for i in range(n):
    B=["."]*n
    for x,y in [list(map(int,input().split())) for k in range(int(input()))]:
        B[x-1]=str(y)
    A.append("".join(B))
ans=0
for i in range(2**n):
    num=format(i,"b").zfill(n)
    cnt,flag=0,1
    for k,j in enumerate(num):
        result=re.search(r"".join(A[k]),num)
        if result is not None and j=="1":
            cnt +=1
        elif (result is not None and j == "0") or (result is None and j == "1"):
            flag=0
            break
    if flag:
        ans=max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
import re
n=int(input())
A=[]
for i in range(n):
    B=["."]*n
    for x,y in [list(map(int,input().split())) for k in range(int(input()))]:
        B[x-1]=str(y)
    A.append("".join(B))
ans=0
for i in range(2**n):
    num=format(i,"b").zfill(n)
    cnt,flag=0,1
    for k,j in enumerate(num):
        result=re.search(r"".join(A[k]),num)
        if result!=None and j=="1":
            cnt +=1
        elif (result!=None and j=="0") or (result==None and j=="1"):
            flag=0
            break
    if flag:
        ans=max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [[tuple(map(int, input().split())) for i in range(int(input()))]
     for j in range(n)]

# bit全探索
res = 0
for bit in range(2**n):
    for i in range(n):
        if bit & (1 << i):
            for x, y in a[i]:
                if (bit >> x-1) & 1 != y:
                    break
            else:
                continue
            break
    else:
        res = max(res, bin(bit).count('1'))

print(res)

Submission status: Accepted

Solution code:
from itertools import combinations

n = int(input())
l = (1 << n) - 1
r = range(n)
a = [[0, 0] for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y] |= 1 << x - 1

def fail(x):
  x = sum(1 << i for i in x)
  return not all(a[i][0] & x == a[i][1] & l - x == 0 for i in r if x >> i & 1)

while all(map(fail, combinations(r, n))):
  n -= 1
print(n)

Submission status: Accepted

Solution code:
from itertools import combinations
 
n = int(input())
r = range(n)
a = [(set(), set()) for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y].add(x - 1)
 
fail = lambda x: not all(a[i][0].isdisjoint(x) and a[i][1] < x for i in x)
 
while all(map(fail, map(set, combinations(r, n)))):
  n -= 1
print(n)

Submission status: Accepted

Solution code:
def popcount(x):
  r = 0
  while x:
    if x & 1:
      r += 1
    x >>= 1
  return r

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

m = 0
l = (1 << n) - 1
for x in range(1, l + 1):
  if all(a[i][0] & x == a[i][1] & l - x == 0 for i in r if x >> i & 1):
    m = max(m, popcount(x))
print(m)

Submission status: Accepted

Solution code:
n = int(input())
xy_l = [[] for i in range(n)]
cnt = 0
for i in range(n):
    a = int(input())
    for j in range(a):
        xy = list(map(int, input().split()))
        xy_l[i].append(xy)
# 　括りとして、x,yの組み合わせ、人ごとの証言の組み合わせでそれぞれ分ける

for k in range(1 << n):
    ev = [0]*n
    for l in range(n):
        if (k >> l) & 1:
            ev[l] = 1
    #         ここまでで仮定は完成
    f = True
    for p,q in enumerate(xy_l):  # 第一変数はindexで第二変数が要素
        if ev[p]:
            for r in q:  # xy_lの要素
                if r[1] != ev[r[0] - 1]:
                    f = False
    if f:
        cnt = max(cnt, ev.count(1))

print(cnt)

Submission status: Accepted

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

def mujunsearch(n,n15,wrd):
    cnt = 0
    s = {}
    for i in range(n):
        if(n15>>i&1) == 1:
            cnt += 1
            for j in wrd[i]:
                x = j[0]
                y = j[1]
                if s.get(x,y) != y:
                    return 0
                else:
                    s[x] = y
    for i in range(n):
        if(n15>>i&1) == 0:
            if s.get(i+1,0) == 1:
                return 0
        else:
            if s.get(i+1,1) == 0:
                return 0
    # print(s)
    # print(bin(n15))
    return cnt

st = 0
for i in range(1<<n):
    st = max(st,mujunsearch(n,i,wrd))
print(st)

Submission status: Accepted

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

ans = 0
for i in range(1 << N):
    chk = []
    for j in range(N):
        if ((i >> j) & 1):
            chk.append(1)
        else:
            chk.append(0)
    for a, x, y in lst:
        if ((i >> a) & chk[a]):
            if chk[x] ^ y:
                chk = [0] * N
                break
    ans = max(ans, sum(chk))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

messages = [[] for i in range(n)]

for i in range(n):
    num = int(input())

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

ans = 0
for i in range(2**n):
    check = i
    count = sum([(check >> t) & 1 for t in range(n)])
    if count <= ans:
        continue
    possible = True
    for k in range(n):
        if (check >> k) & 1:  # k is truth
            message = messages[k]

            for person, truth in message:
                if (check>>person)&1 == truth:
                    continue
                else:
                    possible = False
                    break
        else:  # k is not truth
            continue

        if not possible:
            break

    if possible:
        ans = max(ans, count)

print(ans)

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_ = tuple(map(int,input().split()))
        xy[i].append(xy_)

bN = 2**N
ans = 0
for b in range(bN):
    lis = [int(("00000000000000"+bin(b)[2:])[-1-i]) for i in range(N)]
    #lis は0,1で表される不親切、正直者
    for n,l in enumerate(lis):
        #nは今見ている人、lは1なら正直者
        if l:
            for x,y in xy[n]:
                if y != lis[x-1]:
                    break
            else:
                continue
            break
    else:
        ans = max(ans,lis.count(1))
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(1 << n):
    ok = True
    cnt = 0
    t = [-1] * n
    for j in range(n):
        if (i & (1 << j)) and ok:
            if t[j] == -1:
                t[j] = 1
            elif t[j] == 0:
                ok = False
                break
            cnt += 1
            for k in range(a[j]):
                if t[x[j][k]] == -1:
                    t[x[j][k]] = y[j][k]
                elif t[x[j][k]] != y[j][k]:
                    ok = False
                    break
        else:
            if t[j] == -1:
                t[j] = 0
            elif t[j] == 1:
                ok = False
                break
    if ok:
        ans = max(ans, cnt)
        #print(i)

print(ans)

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_ = tuple(map(int,input().split()))
        xy[i].append(xy_)

bN = 2**N
ans = 0
for b in range(bN):
    for n in range(N):
        if (b >> n) & 1:
            for x,y in xy[n]:
                if y != (b >> (x-1) & 1):
                    break
            else:
                continue
            break
    else:
        ans = max(ans,bin(b).count("1"))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
XY = []
ans = 0
for i in range(n):
  a = int(input())
  XY.append([])
  for j in range(a):
    XY[i].append(list(map(int,input().split())))
for i in range(2**n):
  i = format(i, 'b')
  i = i.zfill(n)
  temp = i.count("1")
  temp2 = 0
  for j in range(n):
    if i[j] == "1":
      for k in range(len(XY[j])):
        if str(XY[j][k][1]) != i[XY[j][k][0]-1]:
          temp2 = 1
          break
  if temp2 == 0:
    if ans < temp:
      ans = temp
print(ans)