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: Time Limit Exceeded

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

def digitsum(x, base=2):
    ret = 0
    while x>0:
        ret += x % base
        x = x // base
    return(ret)

ans = 0
for i in range(1<<n):
    ok = True
    for j in range(i):
        # if jth person may be honest, verify testimony of him.
        if (i>>j) & 1 == 1:
            for xy in xys[j]:
                x, y = xy
                if (i>>x) & 1 != y:
                    ok = False
                    break
        if not ok:
            break
    if ok:
        ans = max(ans, digitsum(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xy = [[]] * n
cnt = 0

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

bit = '0' + str(n) + 'b'
for k in range(2**n):
  cnt_current = 0
  flg = True
  katei = format(k, bit)
  
  for l in range(len(xy)):
    if katei[l] == '0':
      continue
    else:
      for m in range(len(xy[l])):
        if int(xy[l][m][1]) != int(katei[xy[l][m][0]-1]):
          flg = False
  if flg == True:
    cnt_current = katei.count('1')
  if cnt_current > cnt:
    cnt = cnt_current
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys


def kensho(x,tlist):
    for lis in tlist:
        if((x>>(lis[1]-1)) & 1 == lis[2]):
            pass
        else:
            return -1

    return bin(x).count('1')


def main():
    N = int(input())
    xy=[]
    ans=0

    for i in range(1,N+1):
        An= int(input())
        for j in range(0,An):
            x, y = map(int, input().split())
            xy.append([i,x,y])

    cnt = N

    tlist=[]
    for x in range (2 ** cnt):
        for y in range(cnt):
            if((x>>y) & 1):
                for z in xy:
                    if(z[0]==y+1):
                        tlist.append(z)

        anstack = kensho(x,tlist)
        if(ans<anstack):
            ans=anstack

        tlist.clear()

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

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

answers = []
for i in assumptions:
    assumptions2 = []
    for j in range(N):
        assumptions2.append((j + 1, i[j]))
        if i[j] == 1:
            for k in testimonies_all[j]:
                assumptions2.append(k)
    assumptions2.sort()
    count = 0
    for j in range(len(assumptions2) - 1):
        if assumptions2[j][0] == assumptions2[j + 1][0] and assumptions2[j][1] != assumptions2[j + 1][1]:
            count += 1
    if count == 0:
        answers.append(sum(i))

print(max(answers))

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
# import scipy as sp

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

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

    flag = True
    # print(bit)
    for idx, j in enumerate(bit):
        if j == 1:
            for k in [x for x in info if x[0] == idx]:
                # print(' ', k)
                if bit[k[1]] != k[2]:
                    flag = False
    if flag:
        ans = max(ans, sum(bit))
    # print(ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
all = []
for i in range(N):
    A_N = int(input())
    grid = []
    for j in range(A_N):
        a = list(map(int, input().split()))
        grid.append(a)
    all.append(grid)
evi = 0
for i in range(N):
    evi += len(all[i])
ok = []
ans = []
for i in range(2**N):
    b = format(i,'b').zfill(N)
    c = [int(k) for k in list(b)] #2進数りすと
    add = 0
    ok = []
    for j in range(N): 
        for k in range(len(all[j])):
            if c[j] == 0:
                add += 1
                continue
            elif c[all[j][k][0]-1] == all[j][k][1]:
                add += 1
        
        if add == evi:
            ok.append(sum(c))
    if len(ok)>0:
        ans.append(ok)
print(max(list(itertools.chain.from_iterable(ans))))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
data = []
for _ in range(N):
	A = int(input())
	items = []
	for __ in range(A):
		x, y = map(int, input().split())
		items.append((x - 1, y))
	data.append(items)
 
best = 0
 
def check(i):
    for j in range(N):
        if ((i >> j) & 1) == 1:           
            for x, y in data[j]:
                if y !=((i >> x) & 1):return False						
    return True
 
for i in range(1 << 2**N):
    count=0
    for j in range(N):count += ((i >> j) & 1)
    if count>best:
        if check(i):best = count
	
print(best)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
data = []
for _ in range(N):
	A = int(input())
	items = []
	for __ in range(A):
		x, y = map(int, input().split())
		items.append((x - 1, y))
	data.append(items)
 
best = 0
 
def check(i):
    for j in range(N):
        if ((i >> j) & 1) == 1:           
            for x, y in data[j]:
                if y !=((i >> x) & 1):return False						
    return True
 
for i in range(1 << 2**N):
    if check(i):
        count=0
        for j in range(N):
            count += ((i >> j) & 1)
        if count > best:best = count
	
print(best)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
data = []
for _ in range(N):
	A = int(input())
	items = []
	for __ in range(A):
		x, y = map(int, input().split())
		items.append((x - 1, y))
	data.append(items)
 
best = 0
 
def check(i):
    for j in range(N):
        if ((i >> j) & 1) == 1:           
            for x, y in data[j]:
                if y !=((i >> x) & 1):return False						
    return True
 
for i in range(1 << 2**N):
    if check(i):
        count=0
        for j in range(N):
            count += ((i >> j) & 1)
            if count > best:best = count
	
print(best)

Submission status: Time Limit Exceeded

Solution code:
syogens = []
n = int(input())
for i in range(n):
    syogens.append([])
    a = int(input())
    for j in range(a):
        m,s=map(int,input().split())
        syogens[i].append([m,s])
ok = 0
for i in range(2**n):
    ng = False
    i2 = format(i,"b").zfill(16)
    i2 = i2[::-1]
    for k,j in enumerate(syogens):
        for l,j2 in enumerate(j):
            if i2[k] == "1":#i2[k]
                if str(j2[1]) != i2[j2[0]-1]:#証言が正しいかチェック
                    ng = True#証言が矛盾していればNG
    if ng:
        ng = False
    else:
        if i2.count("1") > ok: ok = i2.count("1") 
print(ok)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
N = int(input())
R = np.full((N, N), 2, dtype=np.uint8)
S = np.full((N, N), 2, dtype=np.uint8)
A = []
for i in range(N):
  A.append(int(input()))
  for j in range(A[i]):
    x, y = map(int, input().split())
    R[i, x-1] = y

def contra(M, N, st):
  ss = '0'*(N-len(st)) + st
  flag = 1
  for i in range(N):
    if(ss[i] == '1' and sum(M[:,i] == 0) != 0):
      return False;
    elif(ss[i] == '0' and sum(M[:,i] == 1) != 0):
      return False;
  return True

C = []
for i in range(2**N):
  S = np.full((N, N), 2, dtype=np.uint8)
  st = bin(i)[2:]
  for k in range(1, len(st)+1):
    if(st[-k] == '1'):
      S[N-k, :] = R[N-k,:]
  if(contra(S, N, st)):
    C.append(st.count('1'))

if(len(C) == 0):
  print(0)
else:
  print(max(C))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

state = [[-1] * N for i in range(N)]
for index in range(N):
    Ai = int(input())
    for naka in range(Ai):
        x, y = map(int, input().split()) 
        state[index][x - 1] = y
        # state[index][naka] = [x, y]


# print(state)


maxx = 0
for index in range(2 ** N):
    # print(index)
    person = index
    tempM = 0
    Ai = 0
    ok = 1
    while person > 0:
        if person % 2 == 1:
            tempM += 1
            for i in range(N):
                if state[Ai][i] != -1:
                    # print(str(Ai) + " " + str(i))
                    # print(str(state[Ai][i]) + " " + str((index // (2 ** i)) % 2))
                    # print()
                    if state[Ai][i] != (index // (2 ** i)) % 2:
                        ok = 0
                
        
        person //= 2
        Ai += 1
    
    if ok == 1:
        maxx = max(maxx, tempM)

print(maxx)

Submission status: Time Limit Exceeded

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

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[]
for i in range(n):
  m=int(input())
  a.append([])
  for i in range(m):
    a[-1].append(list(map(int,input().split())))
ans=0
for i in range(2**n):
  s=bin(i)[2:].zfill(n)
  f=True
  for j,k in enumerate(a):
    for x,y in k:
      if s[x-1]!=str(y) and s[j]=="1":f=False
  if f:ans=max(ans,s.count("1"))
print(ans)

Submission status: Time Limit Exceeded

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

for case in range(2**N):
    flag = True
    honest = 0
    for i in range(N):
        for j in range(A[i]):
            if (case >> i)&1 and (case >> x[i][j])&1 != y[i][j]:
                flag = False
        honest += (case >> i)&1

    if flag:
        ans = max(ans, honest)

print(ans)

Submission status: Time Limit Exceeded

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 = 0
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
def honest(i,j):
    return (i>>j)%2 ==1
def check(m):
    for i in range(n):
        if not honest(m,i) :continue
        for j in range(a[i]):
            if y[i][j] == 1 and honest(m,x[i][j]) == 0:
                return False
            if y[i][j] == 0 and honest(m,x[i][j]) == 1:
                return False
    return True
def count(c):
    cnt = 0
    for i in range(c//2+5):
        cnt+= (c >> i)%2
    return cnt
for i in range(2**n):
    if check(i):
        ans = max(ans,count(i))
    
        
        
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = [0]*N
X = np.zeros([N,N],dtype=int)
Y = np.zeros([N,N],dtype=int)

for n in range(N):
    A[n] = int(input())
    for a in range(A[n]):
        X[n][a], Y[n][a] = list(map(int,input().split()))

ans = 0

for bits in range( 1, 1<<N ):
    ok = True
    for i in range( 0, N ):
        if not ( bits & (1 << i) ):
            continue
        for j in range( 0, A[i] ):
            if (( bits >> (X[i][j]-1) ) & 1) ^ Y[i][j]:
                ok = False
    if ok:
        ans = max( ans, (str(bin(bits))[2:]).count('1'))
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = [0]*N
X = np.zeros([N,N],dtype=int)
Y = np.zeros([N,N],dtype=int)

for n in range(N):
    A[n] = int(input())
    for a in range(A[n]):
        X[n][a], Y[n][a] = list(map(int,input().split()))

def counter( x ):
    if x == 0:
        return 0
    return counter( x >> 1 ) + (x & 1)

ans = 0
       
for bits in range( 1, 1<<N ):
    ok = True
    for i in range( 0, N ):
        if not ( bits & (1 << i) ):
            continue
        for j in range( 0, A[i] ):
            if (( bits >> (X[i][j]-1) ) & 1) ^ Y[i][j]:
                ok = False
    if ok:
        ans = max( ans, counter(bits) )
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n = int(input())
xy = []
xyz =[]
a_list = []
ans = ['None']*n
count_list = []
count = 0
for _ in range(n):
    a = int(input())
    a_list.append(a)
    for i in range(a):
        x,y = map(lambda x: int(x),input().split())
        xy.append([x,y])
    xyz.append(xy)
    xy = []
xyz_all = list(itertools.permutations(xyz))

for i in range(len(list(itertools.permutations(xyz)))):
    for j in range(n):
        for k in range(a_list[j]) :
            hoge = xyz_all[i][j][k][:]
            if ans[hoge[0]-1] == 'None':
                ans[hoge[0]-1] = hoge[1]
            elif ans[hoge[0]-1] != hoge[1]:
                count+= 1
    count_list.append(count)



if ans == [0]*n :
    print(1)
else:
    print(n - min(count_list))

Submission status: Time Limit Exceeded

Solution code:
def counter(x):
        if x == 0:
                return 0
        return counter(x >> 1) + int(bin(x & 1), 2)

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

ans = 0 
for bits in range(1, 1 << N): 
        flag = 1 
        for i in range(N):
                if not int(bin(bits & (1 << i)), 2): 
                        continue
                for j in range(A[i]):
                        if int(bin((bits >> (x[i][j][0] - 1) & 1) ^ x[i][j][1]), 2): 
                                flag = 0 
        if flag:
                ans = max(ans, counter(bits))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def counter(x):
        if x == 0:
                return 0
        return counter(int(bin(x >> 1), 2)) + int(bin(x & 1), 2)

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

ans = 0 
for bits in range(1, int(bin(1 << N), 2)):
        flag = 1 
        for i in range(N):
                if not int(bin(bits & int(bin(1 << i), 2)), 2): 
                        continue
                for j in range(A[i]):
                        if int(bin(int(bin(bits >> (x[i][j][0] - 1)), 2) & 1), 2) ^ x[i][j][1]:
                                flag = 0 
        if flag:
                ans = max(ans, counter(bits))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst = [(bin(i)[2:]).zfill(n) for i in range(2**n)]
num_list = []
A_list = []
xy_list = []
for i in range(n):
    a = int(input())
    A_list.append(a)
    for j in range(a):
        x,y = map(int,input().split())
        xy_list.append([x,y])
for i in range(len(lst)):
    choose = lst[i]
    one_count = choose.count("1")
    a_count = 0
    flag = True
    for num, j in enumerate(A_list):
        a_count += j
        for k in range(a_count-j, a_count):
            x,y = xy_list[k][0],xy_list[k][1]
            if choose[num] == "1" and choose[x-1] != str(y):
                flag = False
    if flag:
        num_list.append(one_count)
    else:
        num_list.append(0)
print(max(num_list))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
Nloop = N + 1
A = np.zeros((Nloop, Nloop), dtype="int")
Acount = np.zeros(Nloop, dtype="int")

for i in range(1, Nloop):
    Acount[i] = int(input())
    for _ in range(Acount[i]):
        x, y = map(int, input().split())
        A[i, x] = 1 if y == 1 else -1

honest_loop = 2 ** N
honest_num = np.zeros(Nloop, dtype="int")

ans = 0

for i in range(1, honest_loop):
    for l in range(1, Nloop):
        honest_num[l] = 1 if i >> (l - 1) & 1 == 1 else -1

    check = np.dot(A, honest_num)

    honest_check = True
    for l in range(1, Nloop):
        # lの人が正直者のとき
        if honest_num[l] == 1 and Acount[l] != check[l]:
            honest_check = False

    if honest_check:
        ans = max(sum(honest_num == 1), ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

n = int(input())
mat = np.ones((n, n))
for i in range(n):
    tmp_a = int(input())
    for j in range(tmp_a):
        tmp_x, tmp_y = map(int, input().split())
        if tmp_y == 0:
            mat[i][tmp_x-1] = 0
          
#bit全探索

ans = 0
for k in range(2**n):
    bit_list = [0] * n
    for l in range(n):
         if ((k >> l) & 1):
            bit_list[n-1-l] = 1
    
    mat_check = mat
    for m in range(n)[::-1]:
        if bit_list[m] == 0:
            mat_check = np.delete(mat_check, obj=m, axis=0)
            mat_check = np.delete(mat_check, obj=m, axis=1)
    if np.sum(mat_check) == sum(bit_list)**2:
        if sum(bit_list)>=2:
            ans = sum(bit_list)
        elif sum(mat[m])==1:
            ans = sum(bit_list)
print(ans)

Submission status: Time Limit Exceeded

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):
		cu = "2"
		for k in range(len(ll)):
			if ll[k][j] == "1" and th[j] != "1":
				te = 1
			elif ll[k][j] == "0" and th[j] != "0":
				te = 1
			if ll[k][j] == "1" and cu == "2":
				cu = "1"
			elif ll[k][j] == "0" and cu == "2":
				cu = "0"
			elif ll[k][j] == "0" and cu == "1":
				te = 1
			elif ll[k][j] == "1" and cu == "0":
				te = 1
	if te == 0:
		f = len(ll)
		if f > m:
			m = f
print(m)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())

matrix = np.zeros((n, n)) + 2
for i in range(n):
    a = int(input())
    for _ in range(a):
        j, val = list(map(int, input().split(' ')))
        matrix[i, j-1] = val

max_count = 0
for i in range(2**n):
    bin_str = bin(i)[2:].zfill(n)
    bin_array = np.array([int(s) == 0 for s in bin_str])
    tmp_matrix = matrix[bin_array]
    said_false = np.any(tmp_matrix == 0, axis=0)
    if np.any(said_false & bin_array):
        continue
    said_true = np.any(tmp_matrix == 1, axis=0)
    if not np.any(said_true & ~bin_array):
        count = np.sum(bin_array)
        if count > max_count:
            max_count = count

print(max_count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())

matrix = np.zeros((n, n)) + 99
for i in range(n):
    a = int(input())
    for _ in range(a):
        j, val = list(map(int, input().split(' ')))
        matrix[i, j-1] = val

max_count = 0
for i in range(2**n):
    bin_str = bin(i)[2:].zfill(n)
    bin_array = np.array([int(s) == 0 for s in bin_str])
    tmp_matrix = matrix[bin_array]
    said_true = np.any(tmp_matrix == 1, axis=0)
    if np.any(said_true & ~bin_array):
        continue
    said_false = np.any(tmp_matrix == 0, axis=0)
    if not np.any(said_false & bin_array):
        count = np.sum(bin_array)
        if count > max_count:
            max_count = count

print(max_count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())

matrix = np.zeros((n, n)) + 99
for i in range(n):
    a = int(input())
    for _ in range(a):
        j, val = list(map(int, input().split(' ')))
        matrix[i, j-1] = val

max_count = 0
for i in range(2**n):
    bin_str = bin(i)[2:].zfill(n)
    bin_array = np.array([int(s) == 0 for s in bin_str])
    tmp_matrix = matrix[bin_array]
    said_true = np.any(tmp_matrix == 1, axis=0)
    said_false = np.any(tmp_matrix == 0, axis=0)
    if np.any(said_true & ~bin_array):
        continue
    if not np.any(said_false & bin_array):
        count = np.sum(bin_array)
        if count > max_count:
            max_count = count

print(max_count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

NGlist = [0] * N
grouplist = [0]*N
ans = 0
for i in range(N):
    NGlist[i] = [0] * N
    grouplist[i] = [0] * N


for k in range(N):
    n = int(input())
    for j in range(n):
        x, y = map(int, input().split())
        if y == 0:
            NGlist[k][x-1] = 1
            NGlist[x - 1][k] = 1
        if y == 1:
            grouplist[k][x-1] = 1

for num in range(2 ** N):
    # print("num=")
    # print(num)
    group = set()
    newmember = set()
    for h in range(N):
        if h not in group and num % 2 == 1:
            group.add(h)
            newmember.add(h)
        num //= 2

    while (len(newmember) != 0):
        for s in list(newmember):
            for p in range(N):
                if grouplist[s][p] == 1 and p not in group:
                    group.add(p)
                    newmember.add(p)
                newmember.discard(s)

    len_group = len(group)
        # print(group)
    flag = 0
    if ans >= len_group:
       flag = 1
    
    # print(group)
    for m in group:
        for t in group:
            if NGlist[m][t] == 1:
                flag = 1
                break
        if flag == 1:
            break
    if flag == 0 and ans < len_group:
        ans = len_group

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys

N= int(input())
s = []
A = []
for i in range(N):
  a = int(input())
  A.append(a)
  temp = []
  for j in range(a):
    temp.append(list(map(int,input().split())))
  s.append(temp)
  
l = list(range(N))
for num in range(N):
  for lie in itertools.permutations(l, num):
    ok = 1
    for i in range(N):
      if i in lie:
        continue
      for shogen in s[i]:
        if shogen[0]-1 in lie and shogen[1] == 1:
          ok = 0
          break
        elif not(shogen[0]-1 in lie) and shogen[1] == 0:
          ok = 0
          break
    
    if ok == 1:
      print(N-num)
      sys.exit()
print(0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())

matrix = np.zeros((n, n)) + 99
for i in range(n):
    a = int(input())
    for _ in range(a):
        j, val = list(map(int, input().split(' ')))
        matrix[i, j-1] = val

max_count = 0
for i in range(2**n):
    bin_str = bin(i)[2:].zfill(n)
    bin_array = np.array([int(s) == 0 for s in bin_str])
    # print(matrix)
    # print(bin_array)
    said_true = np.any(matrix[bin_array] == 1, axis=0)
    # print(said_true)
    if np.any((said_true == True) & (bin_array == False)):
        continue
    # judge if there is no lier
    if np.all(matrix[:, bin_array][bin_array] != 0):
        # print('K')
        count = np.sum(bin_array)
        if count > max_count:
            max_count = count
    # print()

print(max_count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [0]*N
syogen = [0]*N

for i in range(N):
    A[i] = int(input())
    xy = [0]*A[i]
    for j in range(A[i]):
        xy[j] = [int(i) for i in input().split()]
    syogen[i] = xy

syojiki = [0]*N

truth = [7]*N

flag = True
flag2 = True

for i in range(N):
    truth[i] = 1
    for j in range(len(syogen[i])):
        truth[syogen[i][j][0]-1] = syogen[i][j][1]
    
    for j in range(N):
        if truth[j] == 1:
            for k in range(len(syogen[j])):
                if truth[syogen[j][k][0]-1] == 7:
                    truth[syogen[j][k][0]-1] = syogen[j][k][1]
                else:
                    if truth[syogen[j][k][0]-1] != syogen[j][k][1]:
                        flag = False
                        break

    if flag:
        tmp = 0
        for j in range(N):
            if truth[j] == 1:
                tmp += 1
        syojiki[i] = tmp

        while 7 in truth:
            for j in range(N):
                if truth[j] == 7:
                    truth[j] = 1
                    for k in range(len(syogen[j])):
                        if truth[syogen[j][k][0]-1] == 7:
                            truth[syogen[j][k][0]-1] = syogen[j][k][1]
                        else:
                            if truth[syogen[j][k][0]-1] != syogen[j][k][1]:
                                flag2 = False
                                break
                if not flag2:
                    break
        if flag2:
            tmp = 0
            for j in range(N):
                if truth[j] == 1:
                    tmp += 1
            syojiki[i] = tmp
        
    truth = [7]*N
    flag = True
    flag2 = True

print(max(syojiki))

Submission status: Time Limit Exceeded

Solution code:
import itertools
n = int(input())
t = []
l = []
for nn in range(1, n + 1):
    for _ in range(int(input())):
        x, y = [int(n) for n in input().split()]
        if y ==  1:
            t.append([nn, x])
        else:
            l.append([nn, x])
if len(l) == 0:
    print(n)
    exit()
bl = set([x[0] for x in l])
cl = set([x[1] for x in l])
bt = set([x[0] for x in t])
ct = set([x[1] for x in t])
if len(bl) > len(cl):
    ds = cl
    dn = len(cl)
else:
    ds = bl
    dn = len(bl)
for nn in range(dn - 1, n + 1):
    for it in itertools.product(range(1, n + 1), repeat=nn):
        tt = [x[1] for x in t if not x[0] in it]
        if len(set(it) & set(tt)) != 0:
            continue
        ll = [x[1] for x in l if not x[0] in it]
        if len(set([x for x in range(1, n + 1) if not x in it]) & set(ll)) == 0:
            print(n - nn)
            exit()
print(0)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
import numpy as np
matrix = np.zeros((N,N),dtype="int8")
for n in range(N):
    A = int(input())
    for a in range(A):
        array = [int(i) for i in input().split()]
        matrix[n,array[0]-1] = 1 if array[1] == 1 else -1
l = [True,False]
from itertools import product
for pattern in product(l,repeat=N):
    able = True
    for i,p in enumerate(pattern):
        if p:
            for a,b in zip(matrix[i],pattern):
                if (b==True and a==-1) or (b==False and a == 1):
                    able = False
                    break
            if able == False:
                break
        else:
            pass
    if able == True:
        break
print(sum(pattern))

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools

input = sys.stdin.readline

n = int(input())
a_s = [0] * n
xss = []
yss = []
for i in range(n):
	a_s[i] = int(input())
	xss.append([])
	yss.append([])
	for _ in range(a_s[i]):
		x, y = map(int, input().split())
		xss[i].append(x)
		yss[i].append(y)

# print(xss)
# print(yss)

tmp_shojiki = [True] * n
for i in range(n):
	for shojiki in set(itertools.permutations(tmp_shojiki)):
		# print(i, shojiki)
		all_shojiki = True
		for j in range(n):
			if not shojiki[j]:
				continue
			for k in range(a_s[i]):
				x, y = xss[j][k] - 1, yss[j][k]
				if y == 1:
					if shojiki[x] == False:
						all_shojiki = False
						break
				else:
					if shojiki[x] == True:
						all_shojiki = False
						break
		if all_shojiki:
			print(n - i)
			sys.exit()

	tmp_shojiki[i] = False

print(0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = np.zeros((N,2,N), dtype=bool) # A = {([false],[true]),,}

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

upper = 0

for i in range(2**N):
  mask = (1 & i >> np.arange(N)).astype(bool)
  s = np.sum(mask)
  if s <= upper: continue
  m2 = np.repeat([mask], s, axis=0).reshape(-1)
  aa = A[mask]
  a0 = aa[:,0].reshape(-1)
  if np.any(m2[a0]!=0): continue
  a1 = aa[:,1].reshape(-1)
  if np.any(m2[a1]!=1): continue
  upper = s

print(upper)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = np.zeros((N,2,N), dtype=bool) # A = {([false],[true]),,}

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

upper = 0

seed = 1 << np.arange(N)

for i in range(2**N):
  mask = (seed & i).astype(bool)
  s = np.sum(mask)
  if s <= upper: continue
  m2 = np.repeat([mask], s, axis=0).reshape(-1)
  aa = A[mask]
  a0 = aa[:,0].reshape(-1)
  if np.any(m2[a0]!=0): continue
  a1 = aa[:,1].reshape(-1)
  if np.any(m2[a1]!=1): continue
  upper = s

print(upper)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())

matrix = np.zeros((n, n)) + 99
for i in range(n):
    a = int(input())
    for _ in range(a):
        j, val = list(map(int, input().split(' ')))
        matrix[i, j-1] = val

max_count = 0
for i in range(2**n):
    bin_str = bin(i)[2:].zfill(n)
    bin_array = np.array([int(s) == 0 for s in bin_str])
    # pick back person who is judged true
    bin_array[np.any(matrix[bin_array] == 1, axis=0)] = True
    # judge if there is no lier
    if np.all(matrix[:, bin_array][bin_array] != 0):
        count = np.sum(bin_array)
        if count > max_count:
            max_count = count

print(max_count)