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:
from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
from fractions import gcd
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

ans = 0
n = int(input())
def to_num(m):
    outp = 0
    for i in range(n):
        outp += (m>>i)&1
    return outp

ini = [[] for _ in range(n)]
for i in range(n):
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        ini[i].append([x,y])
#all possible true or false 
for bit in range(1<<n):
    is_good = 1
    for i in range(n):
        if is_good != 1:
            break
        #ith person is honest
        if (bit>>i)&1:
            for j in range(len(ini[i])):
                if is_good != 1:
                    break
                if ini[i][j][1] == 1:
                    is_good = is_good & ((bit >> (ini[i][j][0]-1))&1)
                elif ini[i][j][1] == 0:
                    is_good = is_good & ~((bit >> (ini[i][j][0]-1))&1)

    if is_good:
        ans = max(ans, to_num(bit))
    
print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

N = int(input())
A = []
xy = []
ans = []
sm = 0

for _ in range(N):
    temp = int(input())
    A.append([temp, sm])
    sm += temp
    for _ in range(A[-1][0]):
        xy.append(list(map(int, input().split())))
for i in range(2**N):
    flag = True
    binary = bin(i)[2:]
    if len(binary) < N:
        binary = '0' * (N - len(binary)) + binary
    check = [0]*N
    for j, digit in enumerate(binary):
        if digit == '1':
            check[j] = 1
    for j, value in enumerate(check):
        if value == 1:
            for k in range(A[j][0]):
                x = xy[A[j][1]+k][0] - 1
                y = xy[A[j][1]+k][1]
                if check[x] != y:
                    flag = False
    if flag:
        ans.append(check.count(1))

print(max(ans))

Submission status: Accepted

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

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

    honest = [[None] * 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())
            honest[i][x-1] = True if y else False
    
    ans = 0
    for i in range(2**N):
        p = [False] * N
        tmp = 0
        for j in range(N):
            if i&1:
                p[j] = True
                tmp += 1
            i >>= 1
        
        # print(p)
        
        ok = True
        for j in range(N):
            if not ok:
                break
            if p[j]:# 正直者の証言の場合はhonestと一致するか調べる
                for k in range(N):
                    if (honest[j][k] == True and p[k] == False) or (honest[j][k] == False and p[k] == True):
                        ok = False
                        break
        
        if ok:
            ans = max(ans, tmp)
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
v = []
for i in range(n):
    ai = int(input())
    vi = []
    for j in range(ai):
        vi.append(list(map(int, input().split())))
    v.append(vi)

m = 0
for bit in range(2**n - 1, -1, -1):
    is_break = False
    for i in range(n):
        if not (bit & (1 << i)):
            continue
        for xij, yij in v[i]:
            if not (not (bit & (1 << xij - 1))) != yij:
                is_break = True
                break
        if is_break:
            break
    else:
        m = max(bin(bit).count('1'), m)

print(m)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
from itertools import combinations

def main():
    n = int(input().strip())
    G = [[-1] * n for _ in range(n)]
    # H = [[0] * n for _ in range(n)]
    for i in range(n):
        m = int(input().strip())
        for j in range(m):
            x, y = list(map(int, input().strip().split()))
            G[i][x-1] = y
    # print(G)
    for i in reversed(range(n+1)):# n~0
        for c in combinations(range(n), i):
            # 正直者と正直者が指す人，がある特定の人を正直，真偽不明で指していたら矛盾
            cont = False
            # print("c: ", c)
            for p in c:
                for j in range(n):
                    if G[p][j] == -1:
                        continue
                    if (G[p][j] == 1) != (j in c):
                        cont = True
                    # print("p, j, cont: ", p, j, cont)
                    # print(c, j in c)
                    # print(G[p][j] == 1)
                    # print((G[p][j] == 1) != True)
                    # if (j in c and G[p][j] == 0):
                    #     print("cont: ", c)
                    #     cont = True
            if cont == False:
                print(i)
                return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

humans = []

for i in range(n):
  human = []
  ai = int(input())
  for j in range(ai):
    x,y = map(int, input().split())
    human.append([x-1,y])
  humans.append(human)
num = 0
for i in range(pow(2, n)):
  k = i
  honest = []
  for j in range(n):
    x = pow(2,n-j-1)
    honest.append(1 - (k // x))
    k = k % x
  
  flg = True
  for j in range(n):
    if(honest[j]==0):
      continue
    for k in humans[j]:
      if(honest[k[0]] != k[1]):
        flg = False
        break
    if(not(flg)):
      break
        
  if(flg):
    num = sum(honest)
    break

print(num)

Submission status: Accepted

Solution code:
# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math
# mod = 10**9 + 7

n = int(input())
x = []
for i in range(n):
    ai = int(input())
    xi = []
    for j in range(ai):
        xi.append(list(map(int, input().split())))
    x.append(xi)

m = 0
for h in range(2**n - 1, -1, -1):
    is_break = False
    h = bin(h)[2:].zfill(n)
    for i, xi in enumerate(x):
        if h[i] == '0':
            continue
        for xij, yij in xi:
            if (int(h[xij - 1]) != yij):
                is_break = True
                break
        if is_break:
            break
    else:
        m = max(sum(map(int, list(h))), m)

print(m)

Submission status: Accepted

Solution code:
n = int(input())
x = []
for i in range(n):
    ai = int(input())
    xi = []
    for j in range(ai):
        xi.append(list(map(int, input().split())))
    x.append(xi)

m = 0
for h in range(2**n - 1, -1, -1):
    is_break = False
    h = bin(h)[2:].zfill(n)
    for i, xi in enumerate(x):
        if h[i] == '0':
            continue
        for xij, yij in xi:
            if (int(h[xij - 1]) != yij):
                is_break = True
                break
        if is_break:
            break
    else:
        m = max(sum(map(int, list(h))), m)

print(m)

Submission status: Accepted

Solution code:
N = int(input())

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

result = 0
for i in range(1, 2**N):
    consistent = True
    for j in range(N):
        if (i >> j) & 1 == 0:
            continue
        for x, y in evidences[j]:
            if (i >> x) & 1 != y:
                consistent = False
                break
        if not consistent:
            break
    if consistent:
        result = max(result, bin(i)[2:].count('1'))
print (result)

Submission status: Accepted

Solution code:
n = int(input())
xy = []
for _ in range(n):
    a = int(input())
    xy.append([])
    for _ in range(a):
        xy[-1].append([int(i) for i in input().split()])
        xy[-1][-1][0] -= 1

ans = 0
for i in range(2 ** n):
    ok = True
    l = 0
    for j in range(n):
        if i & (2 ** j) == 0:
            continue
        l += 1
        for k in xy[j]:
            if (1 if i & (2 ** k[0]) != 0 else 0) != k[1]:
                ok = False
    
    if ok:
        ans = max(ans, l)
print(ans)

Submission status: Accepted

Solution code:
# 入力
N = int(input())
witness = [[-1] * N for _ in range(N)]
for i in range(N):
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        witness[i][x - 1] = y

# 正直者の組を作り判定
ans = 0
for i in range(1, 2 ** N + 1):
    honest = [0] * N
    for j in range(N):
        if int(format(i, 'b').zfill(N)[j]) == 1:
            honest[j] = 1

    is_correct = True
    for j in range(N):
        if honest[j] == 1:
            for k in range(N):
                if witness[j][k] == -1:
                    pass
                elif witness[j][k] != honest[k]:
                    is_correct = False
    if is_correct:
        ans = max(ans, sum(honest))

print(ans)

Submission status: Accepted

Solution code:
# 入力
N = int(input())
witness = [[-1] * N for _ in range(N)]
for i in range(N):
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        witness[i][x - 1] = y

# 正直者の組を作り判定
ans = 0
for i in range(1, 2 ** N + 1):
    honest = [0] * N
    for j in range(N):
        if int(str(format(i, 'b')).zfill(N)[j]) == 1:
            honest[j] = 1

    is_correct = True
    for j in range(N):
        if honest[j] == 1:
            for k in range(N):
                if witness[j][k] == -1:
                    pass
                elif witness[j][k] != honest[k]:
                    is_correct = False
    if is_correct:
        ans = max(ans, sum(honest))

print(ans)

Submission status: Accepted

Solution code:
# 入力
N = int(input())
witness = [[-1] * N for _ in range(N)]
for i in range(N):
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        witness[i][x - 1] = y

# 正直者の組を作り判定
ans = 0
for i in range(1, 2 ** N + 1):
    honest = [0] * N
    for j in range(N):
        if str(format(i, 'b')).zfill(N)[j] == "1":
            honest[j] = 1

    is_correct = True
    for j in range(N):
        if honest[j] == 1:
            for k in range(N):
                if witness[j][k] == -1:
                    pass
                elif witness[j][k] != honest[k]:
                    is_correct = False
    if is_correct:
        ans = max(ans, sum(honest))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xy = []
for _ in range(n):
    xy.append([])
    a = int(input())
    for _ in range(a):
        xy[-1].append([int(i) for i in input().split()])
        xy[-1][-1][0]-=1

ma = 0

for i in range(2 ** n):
    ok = True
    a = 0
    for j in range(n):
        if (2 ** j) & i != 0:
            a += 1
            for k in xy[j]:
                if (1 if (2 ** k[0]) & i != 0 else 0) != k[1]:
                    ok = False
    if ok:
        ma = max(ma, a)
print(ma)

Submission status: Accepted

Solution code:

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

    n_list = []
    for i in range(n):
        a_list = []
        a = int(input())
        for j in range(a):
            x,y = map(int, input().split())
            x -= 1
            a_list.append([x,y])
        if a == 0:
            a_list.append([0])
        n_list.append(a_list)

    #print(n_list)
    ans = [0]
    for j in range(0,2**n):
        tmp = bin(j)
        tmp = str(int(tmp[2:])).zfill(n)
        #print('tmp')
        #print(tmp)
        
        
        break_on = 0
        for k in range(n):
            if tmp[k] == '1':
                #print(n_list[k])
                if n_list[k][0] != [0]:
                    for h in n_list[k]:
                        #print('########')
                        #print(k)
                        #print(h[1])
                        #print(tmp[h[0]])
                        if h[1] != int(tmp[h[0]]):
                            break_on = 1
                            break
                    if break_on == 1:
                        break
            if break_on == 1:
                break
            
            if tmp[k] == '0':
                continue
        
        if break_on == 0:
            #print('tmp.count()')
            #print(tmp.count('1'))
            ans.append(tmp.count('1'))
    
    #print(ans)
    print(max(ans))
    


            



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
dat = []
for i in range(n):
    t = []
    an = int(input())
    for i in range(an):
        x, y = map(int, input().split())
        x -= 1
        t.append([x,y])
    dat.append(t)

res = 0

bin_a = ["{:015b}".format(a) for a in range(0, 2**n)]
bin_a = list(map(lambda x: [int(y) for y in list(x)], bin_a))
#print(dat)

for x in bin_a:
    x.reverse()
    #print("pattttttttttttttttt", x)
    r = 0
    f = True
    tmp = [-1] * n
    for i in range(n):
        if x[i] == 1:
            #print("i", i)
            for y in dat[i]:
                #print("y", y)
                if y[1] == 0 and x[y[0]] == 0:
                    if tmp[y[0]] != 1:
                        tmp[y[0]] = 0
                        continue
                    f = False
                if y[1] == 1 and x[y[0]] == 1:
                    if tmp[y[0]] != 0:
                        tmp[y[0]] = 1
                        continue
                    f = False
                f = False
    if f:
        res = max(res, sum(x))
print(res)

Submission status: Accepted

Solution code:
n = int(input())
L = []
for i in range(n):
    L.append(2**i)
ans = 0
comment = [[] for i in range(n)]
num = []
for i in range(n):
    t = int(input())
    num.append(t)
    for j in range(t):
        a,b = map(int,input().split())
        comment[i].append([a-1,b])
for i in range(2**n):
    cur = i
    str = ''
    flag = True
    honest_num = 0
    for j in range(len(L)):
        temp = cur&L[j]
        if temp != 0:
            str = '1'+str
            honest_num += 1
        else:
            str = '0'+str
    for j in range(n):
        d = num[j]
        if str[j] == '1':
            for k in range(d):
                pick = comment[j][k]
                if (pick[1] == 0 and str[pick[0]] == '1') or (pick[1] == 1 and str[pick[0]] == '0'):
                    flag = False
                    break
        if not flag:
            break
    if flag:
        ans = max(ans,honest_num)
print(ans)

Submission status: Accepted

Solution code:
#147C
n=int(input())
a_li=[]
xy_li=[]
for i in range(n):
  a_li.append(int(input()))
  xy_li_i=[list(map(int,input().split())) for j in range(a_li[i])]
  xy_li.append(xy_li_i)
  
proof=[]  
for i in range(2**n):
  li=[0]*n
  for j in range(n):
    if (i>>j)&1==1:
      li[j]=1
  proof.append(li)

ans=0  
for i in proof:
  flag=True
  for j in range(n):
    if i[j]==1:
      for k in range(a_li[j]):
        x=xy_li[j][k][0]
        y=xy_li[j][k][1]
        if i[x-1]!=y:
          flag=False
          break
  if flag:
    count=(sum(i))
    if ans<=count:
      ans=count
    
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import sys
n = int(input())
q = []
def judge():
    state = True
    for i in range(n):
        if li[i] == 0:
            continue
        else:
            for j in range(len(q[i])):
                if li[q[i][j][0]] != q[i][j][1]:
                    return False
                else:
                    state = True
    if state == False:
        return False
    else:
        return True

for i in range(n):
    xy = []
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        xy.append([x-1,y])
    q.append(xy)
maxans = 0
for i in range(2**n):
    li = [0]*n
    ans = 0
    for j in range(n):
        if (i>>j)&1:
            li[n-j-1] = 1
    if judge() == True:
        ans = sum(li)
        maxans = max(maxans,ans)
    else:
        continue
print(maxans)

Submission status: Accepted

Solution code:
#147_C
n = int(input())
ans = 0

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

for i in range(2 ** n):
    flg = True
    res = 0
    for j in range(n):
        if (i >> j) & 1:
            res += 1
            for k in range(len(pr[j])):
                x, y = pr[j][k]
                if ((i >> x) & 1 and y == 0) or (not((i >> x) & 1) and y == 1):
                    flg = False
                    break
    if flg:
        ans = max(ans, res)
        
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Mar 13 13:52:16 2020

@author: Kanaru Sato
"""

n = int(input())
a = []
proof = []

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

honest = 0

for state in range(2**n):   #状態stateを用意
    flag = 0
    for j in range(n):
        if flag == 1:
            break
        if state&(0b1<<j):    #状態stateにおいてj人目が正直か判定
            for k in range(a[j]):
                proofee = proof[j][k][0]-1
                if bool(state&(0b1<<proofee)) != (proof[j][k][1]):   #j人目のK番目の証言について、stateと一致しなければ次のstateへ移る
                    flag = 1    #不成立フラグ
                    break
    if flag == 0:
        count = 0
        for i in range(n):
            count += (state>>i)&0b1
        if honest <= count:
            honest = count
print(honest)

Submission status: Accepted

Solution code:
def count_bit(target):
    result, tmp = 0, target
    while tmp > 0:
        result += tmp & 1
        tmp = tmp >> 1
    return result


N = int(input())
mask_list = []
a_list = []
for i in range(N):
    A = int(input())
    mask, a = 0, 0
    for j in range(A):
        x, y = map(lambda z: int(z), input().split())
        mask += (1 << (x - 1))
        a += (y << (x - 1))
    mask_list.append(mask)
    a_list.append(a)
count = 0
for i in range(1, 2 ** N):
    is_ok = True
    for j, (m, a) in enumerate(zip(mask_list, a_list)):
        if i & (1 << j) == 0:
            continue
        if (i & m) ^ a > 0:
            is_ok = False
            break
    if is_ok:
        bit_count = count_bit(i)
        if count < bit_count:
            count = bit_count
print(count)

Submission status: Accepted

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

# print(info)
ans = 0
for i in range(2**n):
    ok = True
    cnt = 0
    jdg = str(bin(i)[2:]).zfill(n)
    # print(str(bin(i)[2:]).zfill(n))
    for j in range(n):
        if (i >> j) & 1: # 左から見ている
            # print(i, j)
            for x, y in info[j]:
                if jdg[-x] != str(y):
                    ok = False
        if j == n-1:
            cnt = jdg.count('1')

    if ok and ans < cnt:
        ans = cnt

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(1<<n):   #全部分集合について
    flug = True
    honest_num = 0
    for j in range(n):  #すべての人について
        if i & (1<<j):      #正直者のみ証言を考える
            honest_num += 1
            for k in range(a[j]):   #全証言について
                x = xy[j][k][0]
                y = xy[j][k][1]
                # print((i>>(x-1)) & 1 != y, (i>>(x-1)) & 1, bin(1<<(x-1)), x, y)
                if (i>>(x-1)) & 1 != y: #証言とデータが不一致
                    flug = False
                    # break
    # print(bin(i), flug)
    if flug:
        if honest_num > ans:
            ans = honest_num
print(ans)

Submission status: Accepted

Solution code:
import math
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
mod = 10**9 + 7 
sys.setrecursionlimit(1000010)

s = []
N = int(input())
A=[]
Rules=[]

def check():
    for i in range(len(Rules)):
        if s[i] != True:
            continue
        r = Rules[i]
        for rr in r:
            (x,y) = rr
            if y == 1:
                if s[x -1 ] == False:
                    return False
            else:
                if s[x-1] == True:
                    return False
            # print(rr)
    return True

for _ in range(N):
    a = ni()
    A.append(a)
    r = []
    for _ in range(a):
        rr = nl()
        r.append(rr)
    Rules.append(r)

# print(A,Rules)

l = 2 **N 
maxgood = 0
for i in range(1,l ):
    s=[]
    ix = i 
    good = 0
    for _ in range(N):
        if ix %2 != 0:
            good += 1
        s.append(ix%2 !=0 )
        ix = ix //2
    # print(good,s)
    if good > maxgood:
        if check():
            maxgood = good
print(maxgood)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

def judge(bit):
    # i人目の証言を検証する
    for i in range(N):
        # i人目が正直でなければその証言は無視する
        if not (bit & (1<<i)):
            continue
        for v in V[i]:
            x = v[0]
            y = v[1] # y = 1: 正直 y = 0: 不親切
            # y = 1なのに不親切はダメ
            if y == 1 and not(bit & (1<<x)):
                return False
            # y = 0なのに正直者はダメ
            if y == 0 and (bit & (1<<x)):
                return False
    return True

N = int(input())
V = {}
for i in range(N):
    A = int(input())
    V[i] = []
    for j in range(A):
        x, y = input_nums()
        V[i].append((x-1, y)) # 0-index

res = 0
for bit in range(1 << N):
    if judge(bit):
        count = 0
        for i in range(N):
            if bit & (1 << i):
                count += 1
        res = max(res, count)

print(res)

Submission status: Accepted

Solution code:
import sys
import math

from collections import defaultdict
from collections import deque
def load(vtype=int):
    return vtype(input().strip())
def load_list(seplator=" ", vtype=int):
    return [vtype(v) for v in input().strip().split(seplator)]
def exit():
    import sys
    sys.exit(0)
def perm_sub(li, used):
    if len(li) == len(used):
        return [deque()]
    k = []
    for i in range(len(li)):
        if i in used:
            continue
        used.add(i)
        sub_list = perm_sub(li, used)
        for sub in sub_list:
            sub.appendleft(li[i])
        k.extend(sub_list)
        used.discard(i)
    return k
def perm_li(li):
    return perm_sub(li, set())
def perm_n(n):
    return perm_sub(list(range(n)), set())
def join_i(li, sep=""):
    return sep.join([str(e) for e in li])
def li2n(li):
    n, base = 0, 1
    for i in range(len(li)-1, -1, -1):
        n += li[i] * base
        base *= 10
    return n
def sli2ili(li):
    return [int(s) for s in li] 
def prime_list(n):
    li = [i for i in range(2, n+1)]
    for i in range(len(li)):
        if li[i] >= int(math.sqrt(n)):
            break
        if li[i] == -1:
            continue
        for j in range(i+1, len(li)):
            if li[j] % li[i] == 0:
                li[j] = -1
    return [n for n in li if n != -1]
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while True:
        r = a % b
        if r == 0: return b
        a, b = b, r
def lcm(a, b):
    return int(a * b / gcd(a,b))


n = load()
sm = []
for _ in range(n):
    speak = {}
    a = load()
    for _ in range(a):
        x, y = load_list()
        speak[x-1] = bool(y)
    sm.append(speak)

def bit_count(bit):
    c = 0
    while bit > 0:
        bit &= bit - 1
        bit = bit >> 1
        c += 1
    return c


mx = 0
for bit in range(0, 1<<n):
    bf = False
    for i in range(0, n):
        if bit & (1 << i):
            for other, honest in sm[i].items():
                if (((bit & (1 << other))) > 0) == honest:
                    pass
                else:
                    bf = True
                    break
        if bf:
            break
    if not bf:
        mx = max(mx, bit_count(bit))
        
print(mx)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

N = int(input())

m = [[] for _ in range(N)]
for i in range(N):
    a = int(input())
    for _ in range(a):
        m[i].append(list(map(int, input().rstrip().split())))
        
def dfs(i, state):
    if i == N:
        for j, s in enumerate(state):
            if s == 1:
                for x, y in m[j]:
                    if y == 1 and state[x-1] == 0:
                        return 0
                    elif y == 0 and state[x-1] == 1:
                        return 0
        return sum(state)
        
    max_honest = 0
    max_honest = max(max_honest, dfs(i+1, state + [0]))
    max_honest = max(max_honest, dfs(i+1, state + [1]))
    
    return max_honest
    
print(dfs(0, []))

Submission status: Accepted

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

N = int(input())
testimony = [[] for _ in range(N)]
for i in range(N):
    for j in range(int(input())):
        xy = tuple(map(int, input().split(' ')))
        testimony[i].append(xy)

def judge(is_honest):
    res = True
    for i in range(N):
        if is_honest[i]:
            for t in testimony[i]:
                x = t[0]-1
                y = t[1]
                if is_honest[x] == True and y == 0:
                    res = False
                if is_honest[x] == False and y == 1:
                    res = False
    return res

ans = 0
for bit in range(2**N):
    is_honest = [False] * N
    for i in range(N):
        if bit & 1<<i:
            is_honest[i] = True
    if judge(is_honest) == True:
        ans = max(ans, is_honest.count(True))

print(ans)

Submission status: Accepted

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

res = 0

for i in range(2**N):
    ok = True
    cnt = 0
    for j in range(N):
        if (i>>j)&1:
            for x, y in xy[j]:
                if (i>>(x-1))&1 != y:
                    ok = False
                    break
            if not ok:
                break
            cnt += 1
    if ok:
        res = max(cnt, res)

print(res)

Submission status: Accepted

Solution code:
N = int(input())
shou = []
for f in range(N):
    x = int(input())
    for i in range(x):
        a, b = map(int, input().split())
        shou.append([f, a - 1, b])
max_count = 0
for i in range(1, 2 ** N):
    flag = True
    for j in range(N):
        if (i >> j) & 1 == 0:
            continue
        for z, x, y in shou:
            if (i >> x) & 1 != y and z == j:
                flag = False
                break
        if not flag:
            break
    if flag == 1:
        max_count = max(bin(i)[2:].count('1'), max_count)
print(max_count)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
li = [[-1 for i in range(n)] for j in range(n)]
for i in range(n):
    a = ni()
    for j in range(a):
        x, y = na()
        li[i][x-1] = y

ans = 0
for i in range(2 ** n):
    t_li = [-1 for i in range(n)]
    flag = False
    ct = 0
    for j in range(n):
        if ((i >> j) & 1):
            t_li[j] = 1
            ct += 1
        else:
            t_li[j] = 0
    #print(t_li)
    for j in range(n):
        if ((i >> j) & 1):
            tmp = li[j]
            for k in range(n):
                if tmp[k] != -1:
                    if t_li[k] == tmp[k]:
                        continue
                    else:
                        flag = True
                        break
        if flag:
            break
    #print(bin(i), ct,  flag)
    if flag is False:
        #print('\t', ct, i)
        ans = max(ans, ct)
print(ans)

Submission status: Accepted

Solution code:
import itertools

n = int(input())
testimonials = []

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

ans = 0
for item in itertools.product([0, 1], repeat=n):
    flag = 1
    for i, testimonial in enumerate(testimonials):
        if item[i]:
            for (x, y) in testimonial:
                if item[x] != y:
                    flag = 0
                    break
    if flag:
        ans = max(ans, sum(item))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
message = [[] for _ in range(n)]
for i in range(n):
  a = int(input())
  for j in range(a):
    message[i].append([int(x) for x in input().split()])
ans = 0
for i in range(2**n):
  key = [0]*n
  sub = 0
  flag = True
  for j in range(n):
    if (i >> j) & 1:
      key[j] = 1
      sub += 1
  
  for j in range(n):
    if key[j] == 0:
      continue
    for k in range(len(message[j])):
      pq = message[j][k]
      p, q = pq[0], pq[1]
      if key[p-1] == q:
        continue
      else:
        flag = False
        break
    if not flag:
      break
  
  if flag and ans < sub:
    ans = sub

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    n = int(input())
    persons = [[input().split() for j in range(int(input()))] for i in range(n)]

    result = 0
    for i in range(1, 2 ** n):
        flg = True
        for j, answers in enumerate(persons):
            if (i >> j) & 1 == 1:
                for x, y in answers:
                    if not((i >> int(x) - 1) & 1 == int(y)):
                        flg = False
                        break

        if flg:
            result = max(result, bin(i)[2:].count("1"))

    print(result)


if __name__ == '__main__':
    main()