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:
import sys
from collections import deque
readline = sys.stdin.readline
N = int(readline())

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

def check(honest_persons):
    """矛盾がないか検証する"""
    honest_checked = set()  # 宛先を確認済みの正直者の人
    honest_stack = deque(honest_persons)  # 宛先を確認する正直者の人の待ち行列
    honest, liers = honest_persons, []  # 正直者の人, 不親切な人

    # 正直者の人の証言も元に、正直者の人/不親切な人を追加していく
    while len(honest_stack) > 0:
        honest_person = honest_stack.popleft()
        honest_checked.add(honest_person)
        next_honest_persons = testimonies[honest_person][1]

        # 検証済み以外の人をstackする
        for person in next_honest_persons:
            if person not in honest_checked:
                honest_stack.append(person)

        honest += testimonies[honest_person][1]
        liers += testimonies[honest_person][0]

    # 矛盾がなければOK
    if len(set(honest) & set(liers)) == 0:
        return True
    else:
        return False

def main():
    # bit全探索する
    ans = 0
    for i in range(1, 2**N):
        comb = bin(i)[2:].zfill(N)
        honest_persons = []
        for p, c in enumerate(comb):
            if c == '1':
                honest_persons.append(p)
        if check(honest_persons):
            ans = max(ans, sum(list(map(int, list(comb)))))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
N = int(readline())

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

def check(honest_persons):
    """矛盾がないか検証する"""
    honest_checked = []  # 宛先を確認済みの正直者の人
    honest_stack = honest_persons[:]  # 宛先を確認する正直者の人の待ち行列
    honest, liers = honest_persons[:], []  # 正直者の人, 不親切な人

    # 正直者の人の証言も元に、正直者の人/不親切な人を追加していく
    while len(honest_stack) > 0:
        honest_person = honest_stack.pop(0)
        honest_checked.append(honest_person)
        next_honest_persons = testimonies[honest_person][1]

        # 検証済み以外の人をstackする
        for person in next_honest_persons:
            if person not in honest_checked:
                honest_stack.append(person)

        honest += testimonies[honest_person][1]
        liers += testimonies[honest_person][0]

    # 矛盾がなければOK
    if len(set(honest) & set(liers)) == 0:
        return True
    else:
        return False

def main():
    # bit全探索する
    ans = 0
    for i in range(1, 2**N):
        comb = bin(i)[2:].zfill(N)
        honest_persons = []
        for p, c in enumerate(comb):
            if c == '1':
                honest_persons.append(p)
        if check(honest_persons):
            ans = max(ans, sum(list(map(int, list(comb)))))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

def check(comb):
    """矛盾がないか検証する"""
    honest_checked = []  # 検証済みの正直者の人
    honest_stack = []  # 正直者の人
    for i, c in enumerate(comb):
        if c == '1':
            honest_stack.append(i)
    
    honest, liers = honest_stack[:], []  # 正直者の人, 不親切な人
    # 正直者の人の証言も元に、正直者の人/不親切な人を追加していく
    while len(honest_stack) > 0:
        honest_person = honest_stack.pop(0)
        honest_checked.append(honest_person)
        next_honest_persons = testimonies[honest_person][1]

        # 検証済み以外の人をstackする
        for person in next_honest_persons:
            if person not in honest_checked:
                honest_stack.append(person)

        honest += testimonies[honest_person][1]
        liers += testimonies[honest_person][0]

    # 矛盾がなければOK
    if len(set(honest) & set(liers)) == 0:
        return True
    else:
        return False

# bit全探索する
ans = 0
for i in range(1, 2**N):
    comb = bin(i)[2:].zfill(N)
    if check(comb):
        ans = max(ans, sum(list(map(int, list(comb)))))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

import numpy as np
n = int(input())
syougen = np.zeros([n, n])

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

score = 0
for binary in product([1, 0], repeat=n):
    s = syougen.copy()
    s[np.array(binary) == 0] *= 0
    
    flag = True
    ma = np.max(s, axis = 0)
    mi = np.min(s, axis = 0)
    if np.max(ma - mi) == 2:
        flag = False
    if np.min(np.array(binary) - ma) == -1:
        flag = False
    if np.max(np.array(binary) -mi) == 2:
        flag = False
        
    if flag:
#         print(binary)
        if sum(binary) > score:
            score = sum(binary)
            break
print(score)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
state=[]
for j in range(N):
    A=int(input())
    temp=[]
    for i in range(A):
        temp.append(tuple(map(int, input().split())))
    state.append(temp)


OK=[]
for i in range(2**N):
    conflict=0
    for person in range(N): #各人の発言を評価
        for one_state in state[person]:
            if ((i >> (one_state[0]-1)) & 1): #正直者に対して
                if (i >> person) & 1 and one_state[1] == 0:
                    conflict=1
            else: #不親切に対して
                if (i >> person) & 1 and one_state[1]==1:
                    conflict=1
    if conflict==0:
        OK.append(i)
#print(OK)

num=[]
for el in OK:
    count=0
    for j in range(N):
        if (el >> j) & 1:
            count+=1
    num.append(count)
#print(num)
print(max(num))

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

import numpy as np
n = int(input())
syougen = np.zeros([n, n])

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

score = 0
for binary in product([1, 0], repeat=n):
    s = syougen.copy()
    s[np.array(binary) == 0] *= 0
    
    flag = True
    if np.max(np.max(s, axis = 0) - np.min(s, axis = 0)) == 2:
        flag = False
    if np.min(np.array(binary) - np.max(s, axis = 0)) == -1:
        flag = False
    if np.max(np.array(binary) - np.min(s, axis = 0)) == 2:
        flag = False
        
    if flag:
#         print(binary)
        if sum(binary) > score:
            score = sum(binary)
            break
print(score)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

import numpy as np
n = int(input())
syougen = np.zeros([n, n])

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

score = 0
for binary in product([0,1], repeat=n):
    s = syougen.copy()
    s[np.array(binary) == 0] *= 0
    
    flag = True
    if np.max(np.max(s, axis = 0) - np.min(s, axis = 0)) == 2:
        flag = False
    if np.min(np.array(binary) - np.max(s, axis = 0)) == -1:
        flag = False
    if np.max(np.array(binary) - np.min(s, axis = 0)) == 2:
        flag = False
        
    if flag:
#         print(binary)
        if sum(binary) > score:
            score = sum(binary)
print(score)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[0]*N
shougen=[[] for i in range(0,N)]
for i in range(0,N):
    A[i]=int(input())
    for j in range(0,A[i]):
        a,b=map(int,input().split())
        shougen[i].append([a,b])
m=0
for i in range(0,2**N):
    flag=0
    check=[]
    for j in range(0,N):
        if i>>j & 1==1:
            check.extend(shougen[j])
    for j in range(0,N):
        if ([j+1,0] in check) or ([j+1,1] in check):
            if [j+1,0] in check:
                if j==0:
                    data=[0]
                else:
                    data.append(0)
            if [j+1,1] in check:
                if j==0:
                    data=[1]
                else:
                    data.append(1)

        else:
            if j==0:
                data=[2]
            else:
                data.append(2)
    for j in range(0,N):
        if data[j]!=2:
            if int(data[j])!=(i>>j)%2 :
                flag=1
    if len(data)!=N:
        flag=1
    if flag==0:
        test=sum(i>>j &1 for j in range(0,N))
        if test>m:
            m=test

print(m)

Submission status: Time Limit Exceeded

Solution code:
def check(bag, mtx):
    shojiki = set()
    not_shojiki = set()
    for i in range(len(bag)):
        if bag[i] == 1:
            shojiki.add(i)
    shojiki_list = list(shojiki)
 
    while True:
        if shojiki_list == []:
            break
        i = shojiki_list.pop()
        for j in range(len(mtx[i])):
            if mtx[i][j] == 0 and j in shojiki:
                return False
            if mtx[i][j] == 1:
                if j in not_shojiki:
                    return False
                if j not in shojiki:
                    shojiki_list.append(j)
                    shojiki.add(j)
            if mtx[i][j] == 0:
                not_shojiki.add(j)
    return True
 
 
n = int(input())
 
mtx = [[-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())
        mtx[i][x-1] = y
 
ret = 0
 
for i in range(2 ** n):
    bag = []
    for j in range(n):
        if ((i >> j) & 1):
            bag.append(1)
        else:
            bag.append(0)
    if check(bag, mtx):
        if ret < sum(bag):
            ret = sum(bag)
 
print(ret)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst = [[-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())
        lst[i][x-1] = y

item = [i for i in range(2**n)]
def bitka(n):
    honest = []
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            honest.append(item[j])  # フラグが立っていたら bag に果物を詰める
    return honest

def check(honest, lst):
    for i in honest:
        for j in range(n):
            if lst[i][j]==1:
                if j not in honest:
                    return False
            elif lst[i][j]==0:
                if j in honest:
                    return False
    return True

ans = 0
for i in range(2**n):
    if check(bitka(i),lst)==True:
        ans = max(ans, len(bitka(i)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst = [[-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())
        lst[i][x-1] = y

item = [i for i in range(2**n)]
def bitka(n):
    honest = []
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            honest.append(item[j])  # フラグが立っていたら bag に果物を詰める
    return honest

def check(honest, lst):
    for i in honest:
        for j in range(n):
            if lst[i][j]==1 and (j not in honest):
                return False
            elif lst[i][j]==0 and (j in honest):
                return False
    return True

ans = 0
for i in range(2**n):
    if check(bitka(i),lst)==True:
        ans = max(ans, len(bitka(i)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
data = np.empty((0,3), int)
for i in range(N):
    A = int(input())
    tmp = np.zeros((A,3))
    for j in range(A):
        tmp[j][0] = i+1
        tmp[j][1:] = list(map(int, input().split()))
    data = np.append(data, tmp, axis=0)
#print(data)
maxi = 0
for i in range(2**N):
    M = i
    HOU = np.empty(N)
    for j in range(N):
        HOU[j] = M % 2
        M = (M - HOU[j]) / 2
    #print(HOU)
    flag = False
    for j in range(len(data)):
        if HOU[int(data[j][0])-1] == 1:
            if HOU[int(data[j][1])-1] != int(data[j][2]):
                break
    else:
        if sum(HOU) > maxi:
            maxi = sum(HOU)
print(int(maxi))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

messages = []
for i in range(N):
    a = int(input())
    message = []
    for j in range(a):
        pair = list(map(int, input().split()))
        message.append(pair)
    messages.append([a, message])


result = 0
for pattern in range(2 ** N):

    confidence = True
    for i in range(N):

        if not ((pattern >> i) & 1):
            continue

        a = messages[i][0]
        message = messages[i][1]
        for j in range(a):
            x, y = message[j][0], message[j][1]

            condition = (pattern >> (x - 1)) & 1
            if condition and y == 0:
                confidence = False

            condition = not ((pattern >> (x - 1)) & 1)
            if condition and y == 1:
                confidence = False

    if confidence:
        count = 0
        for n in range(N):
            if (pattern >> n) & 1:
                count += 1

        result = max(result, count)

print(result)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N=int(input())
    A=[0]*N
    shougen=[[] for i in range(0,N)]
    for i in range(0,N):
        A[i]=int(input())
        for j in range(0,A[i]):
            a,b=map(int,input().split())
            shougen[i].append([a,b])
    m=0
    for i in range(0,2**N):
        flag=0
        check=[]
        for j in range(0,N):
            if i>>j & 1==1:
                check.extend(shougen[j])#証言の収集
        for j in range(0,N):
            if ([j+1,0] in check) or ([j+1,1] in check):
                if [j+1,0] in check:
                    if j==0:
                        data=[0]
                    else:
                        data.append(0)
                if [j+1,1] in check:
                    if j==0:
                        data=[1]
                    else:
                        data.append(1)

            else:
                if j==0:
                    data=[2]
                else:
                    data.append(2)#証言から得られる正直者リスト
        for j in range(0,N):
            if data[j]!=2:
                if int(data[j])!=(i>>j)%2 :
                    flag=1
        if len(data)!=N:
            flag=1
        if flag==0:
            test=sum(i>>j &1 for j in range(0,N))
            if test>m:
                m=test

    print(m)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def digit(N,n):#nは正の整数、N進法での桁数、許容は１０＾１０００
    if n<N:
        return 1
    else:
        return 1+digit(N,n//N)

def Nbasenumber(N,m):#N>1,mは正の整数、N進法表記、出力は数、許容はN＾１０００
    if  m<N:
        return m
    else:
        k=digit(N,m)#digitとの併用を忘れないこと
        i=m//(N**(k-1))
        return i*(10**(k-1))+Nbasenumber(N,m%(N**(k-1)))

def digitsum(n):#nは正の整数、各位の和、許容は１０＾１０００
    if n<10:
        return n
    else:
        m=n//10
        return n%10+digitsum(m)

def main():
    N=int(input())
    A=[0]*N
    shougen=[[] for i in range(0,N)]
    for i in range(0,N):
        A[i]=int(input())
        for j in range(0,A[i]):
            a,b=map(int,input().split())
            shougen[i].append([a,b])
    m=0
    for i in range(0,2**N):
        flag=0
        check=[]
        for j in range(0,N):
            if i>>j & 1==1:
                check.extend(shougen[j])#証言の収集
        for j in range(0,N):
            if ([j+1,0] in check) or ([j+1,1] in check):
                if [j+1,0] in check:
                    if j==0:
                        data=[0]
                    else:
                        data.append(0)
                if [j+1,1] in check:
                    if j==0:
                        data=[1]
                    else:
                        data.append(1)

            else:
                if j==0:
                    data=[2]
                else:
                    data.append(2)#証言から得られる正直者リスト
        for j in range(0,N):
            if data[j]!=2:
                if int(data[j])!=(i>>j)%2 :
                    flag=1
        if len(data)!=N:
            flag=1
        if flag==0:
            test=digitsum(Nbasenumber(2,i))
            if test>m:
                m=test

    print(m)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def digit(N,n):#nは正の整数、N進法での桁数、許容は１０＾１０００
    if n<N:
        return 1
    else:
        return 1+digit(N,n//N)

def Nbasenumber(N,m):#N>1,mは正の整数、N進法表記、出力は数、許容はN＾１０００
    if  m<N:
        return m
    else:
        k=digit(N,m)#digitとの併用を忘れないこと
        i=m//(N**(k-1))
        return i*(10**(k-1))+Nbasenumber(N,m%(N**(k-1)))

def digitsum(n):#nは正の整数、各位の和、許容は１０＾１０００
    if n<10:
        return n
    else:
        m=n//10
        return n%10+digitsum(m)

def main():
    N=int(input())
    A=[0]*N
    shougen=[[] for i in range(0,N)]
    for i in range(0,N):
        A[i]=int(input())
        for j in range(0,A[i]):
            a,b=map(int,input().split())
            shougen[i].append([a,b])
    m=0
    for i in range(0,2**N):
        flag=0
        check=[]
        for j in range(0,N):
            if i>>j & 1==1:
                check.extend(shougen[j])#証言の収集
        for j in range(0,N):
            if ([j+1,0] in check) or ([j+1,1] in check):
                if [j+1,0] in check:
                    if j==0:
                        data=['0']
                    else:
                        data.append('0')
                if [j+1,1] in check:
                    if j==0:
                        data=['1']
                    else:
                        data.append('1')

            else:
                if j==0:
                    data=['A']
                else:
                    data.append('A')#証言から得られる正直者リスト
        for j in range(0,N):
            if data[j]!='A':
                if int(data[j])!=(i>>j)%2 :
                    flag=1
        if len(data)!=N:
            flag=1
        if flag==0:
            test=digitsum(Nbasenumber(2,i))
            if test>m:
                m=test

    print(m)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[[tuple(map(int,input().split(' ')))for j in range(int(input()))] for i in range(N)]
say_map=[[-1 for i in range(N)] for j in range(N)]
ans = 0
for n,i in enumerate(A):
    for j,k in i:
        say_map[n][j-1]=k
for i in range(2**N):
    i_bin=format(i,'0{}b'.format(N))
    flg = True
    tmp = 0
    for n,j in enumerate(i_bin):
        j = int(j)
        if j == 1:
            tmp += 1
            for k,l in zip(i_bin,say_map[n]):
                if (int(k)==0 and l==1) or (int(k)==1 and l ==0):
                    flg=False
                    break
            if not flg:
                tmp = 0
                break
    ans = max(ans,tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
dic={i:{j:2 for j in range(1,n+1)}for i in range(1,n+1)}
proof={k:0 for k in range(n+1)}
       
for i in range(1,n+1):
    a=int(input())
    for _ in range(a):
        x,y=map(int,input().split())
        dic[i][x]=y
                    
#dicに誰々が正直者か嘘つきであるかということをまとめるdic[x][y]=? xからｙは正直者あるいは真偽不明の者である

maxi=0

for _ in range(1,2**n): 
    #計算量 3* (10)**4
    choice=format(_,"0%ib"%n)
    #1が正直者,0がよくわからない人
    #正直者の発言が全て一致していなくてはいけない　それであれば、矛盾は生じない
    flag=True
    honest=[0 for _ in range(n+1)]
    for i in range(n):
        if choice[i]=="1":
            honest[i+1]=1
    for i in range(1,n+1):
      for j in range(1,n+1):
        if (i!=j and dic[i][j]==0 and honest[i] and honest[j]) or(i!=j and dic[i][j]==1 and honest[i] and (not honest[j])):
          flag=False
          break
         
    if flag:
      maxi=max(maxi,sum(honest))
      
      	

print(maxi)

Submission status: Time Limit Exceeded

Solution code:
def digit(N,n):#nは正の整数、N進法での桁数、許容は１０＾１０００
    if n<N:
        return 1
    else:
        return 1+digit(N,n//N)

def Nbasenumber(N,m):#N>1,mは正の整数、N進法表記、出力は数、許容はN＾１０００
    if  m<N:
        return m
    else:
        k=digit(N,m)#digitとの併用を忘れないこと
        i=m//(N**(k-1))
        return i*(10**(k-1))+Nbasenumber(N,m%(N**(k-1)))

def digitsum(n):#nは正の整数、各位の和、許容は１０＾１０００
    if n<10:
        return n
    else:
        m=n//10
        return n%10+digitsum(m)

def main():
    N=int(input())
    A=[0]*N
    shougen=[[] for i in range(0,N)]
    for i in range(0,N):
        A[i]=int(input())
        for j in range(0,A[i]):
            a,b=map(int,input().split())
            shougen[i].append([a,b])
    m=0
    for i in range(0,2**N):
        flag=0
        check=[]
        x=str(Nbasenumber(2,i))
        for j in range(0,N-len(x)):
            x='0'+x#正直者の仮定
        for j in range(0,N):
            if x[j]=='1':
                check.extend(shougen[j])#証言の収集
        for j in range(0,N):
            if ([j+1,0] in check) or ([j+1,1] in check):
                if [j+1,0] in check:
                    if j==0:
                        data='0'
                    else:
                        data=data+'0'
                if [j+1,1] in check:
                    if j==0:
                        data='1'
                    else:
                        data=data+'1'

            else:
                if j==0:
                    data='A'
                else:
                    data=data+'A'#証言から得られる正直者リスト
        for j in range(0,N):
            if data[j]!='A':
                if data[j]!=x[j]:
                    flag=1
        if len(data)!=N:
            flag=1
        if flag==0:
            test=digitsum(int(x))
            if test>m:
                m=test

    print(m)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
psn = []
alis = []
for i in range(n):
    lis = []
    a = int(input())
    for j in range(a):
        lis.append(list(map(int, input().split())))
    alis.append(a)
    psn.append(lis)
#print(psn)
#print(a)


ans = []
for i in range(2 ** n):
    flag = [False] * n
    for j in range(n):
        if (i >> j) & 1:
            flag[j] = True
    #print(flag)
    hata = True
    for j in range(n):
        for k in range(len(psn[j])):
            if flag[j] == True:
                if flag[psn[j][k][0]-1] == True and psn[j][k][1] == 0:
                    hata = False
                if flag[psn[j][k][0]-1] == False and psn[j][k][1] == 1:
                    hata = False
            #print(flag[psn[j][k][0]-1])
    if hata == True:
        ans.append(flag.count(True))
    #print(hata)

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
import numpy as np
input = sys.stdin.readline

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

ans = 0
for i in itertools.product((True,False), repeat=N):
	ch = True
	i = np.array(i)
	for ee in e[i]:
		for j in range(N):
			if(ee[j]!=-1):
				if(ee[j] != i[j]):
					ch = False
					continue
	if(ch):
		ans = np.count_nonzero(i == True)
		break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
import numpy as np
input = sys.stdin.readline

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

ans = 0
for i in itertools.product((True,False), repeat=N):
	i = np.array(i)
	ch = True
	for ee in e[i==1]:
		for j in range(N):
			if(ee[j]!=-1):
				if(ee[j] != i[j]):
					ch = False
					continue
	for ee in e[i == 0]:
		for j in range(N):
			if(ee[j]!=-1):
				if(ee[j] == i[j]):
					ch = False
					continue
	if(ch):
		ans = np.count_nonzero(i == True)
		break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
table = np.array([[-1]*n for _ in range(n)]) # 証言がないやつはとりあえず-1入れとくか

for i_speaker in range(n):
    ai = int(input())
    for _ in range(ai):
        xij, yij= map(int, input().split())
        table[i_speaker][xij-1] = yij

ans = 0
for i in range(2**n):
    isConflict = False

    for j_speaker in range(n): # それぞれの桁について0か1かを判断したいので
        if (i >> j_speaker) & 1 == 0: # j桁目が1かどうかをジャッジ
            continue

        for k_target in range(n):
            if table[j_speaker][k_target] != -1 and table[j_speaker][k_target] != ((i >> k_target) & 1) :
                isConflict = True
                break

        if isConflict:
            break
    if isConflict == False:
        ans = max(ans, bin(i).count("1"))


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial, ceil, floor
from collections import defaultdict
import itertools
sys.setrecursionlimit(200000)
input = sys.stdin.readline

# N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

N, = map(int, input().split())
L = []
for i in range(N):
    c = int(input())
    a = [[int(v) for v in input().split()] for _ in range(c)]
    L.append(a)

def dfs(index, al):
    for v in L[index]:
        c = v[0] - 1
        if c not in al:
            if v[1]:
                al = dfs(c, al + [c])

    return al

t = [None] * N
for i in range(N):
    t[i] = dfs(i, [i])

ans = 0
for i in range(1 << N):
    a = set()
    for j in range(N):
        if (i >> j) & 1:
            a.add(j)

    for p in list(a):
        for v in t[p]:
            a.add(v)

    s = [-1] * N
    f = True

    for v in a:
        s[v] = 1

    for v in a:
        for x, y in L[v]:
            if s[x-1] == -1:
                s[x-1] = y
            elif s[x-1] != y:
                f = False
    if f:
        ans = max(ans, len(a))

print(ans)

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
 
        del tlist[:]
 
    print(ans)
 
main()

Submission status: Time Limit Exceeded

Solution code:
'''input
3
1
2 1
1
1 1
1
2 0
'''
# A coding delight
from sys import stdin, stdout
import gc
from copy import deepcopy
# gc.disable()
input = stdin.readline



def consistent(choose):
	T = set()
	F = set()
	for i in choose:
		T.add(i + 1)

	for i in choose:
		aux = data[i]
		for j in range(len(aux)):
			p, v = aux[j]
			if v == 0:
				if p in T:
					return False 
				else:
					F.add(p)
			else:
				if p in F:
					return False
				else:
					T.add(p)
	pT = set()
	pF = set()
	while len(T) + len(F) != len(pT) + len(pF):
		# print(T, F)
		pT = deepcopy(T)
		pF = deepcopy(F)
		for i in range(n):
			aux = data[i]
			if i + 1 in T:
				for j in range(len(aux)):
					p, v = aux[j]
					if v == 0:
						if p in T:
							return False 
						else:
							F.add(p)
					else:
						if p in F:
							return False
						else:
							T.add(p)
	# print(T, F)		
	return True

	
# main starts
n = int(input().strip())
data = []
for _ in range(n):
	k = int(input().strip())
	temp =[]
	for i in range(k):
		x, y = list(map(int, input().split()))
		temp.append([x, y])
	data.append(temp)
ans = 0

# generating subset
for i in range(1, 2**n):
	choose = []
	for k in range(n):
		if (1 << k) & i:
			choose.append(k)

	if consistent(choose):
		ans = max(ans, len(choose))
		# print(choose)

print(ans)

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):
    ret = 0
    while x>0:
        ret += x & 1
        x <<= 1
    return ret

ans = 0
for i in range(1<<n):
    ok = True
    for j in range(n):
        # 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())
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):
    ret = 0
    while x>0:
        ret += x & 1
        x <<= 1
    return ret

ans = 0
for i in range(1<<n):
    ok = True
    for j in range(n):
        # 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)