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 itertools import product
N=int(input())
XYs = []
for i in range(N):
    A = int(input())
    XYs.append([tuple(map(int, input().split())) for _ in range(A)])

n=0
for ts in product(*[[1, 0] for _ in range(N)]):
    for i, t in enumerate(ts):
        if t:
            if not all(ts[x-1] == y for x, y in XYs[i]):
                break
    else:
        n=max(n,sum(ts))
print(n)

Submission status: Accepted

Solution code:
n = int(input())
a = []
says = []
maxcnt = 0

for i in range(n):
    ai = int(input())
    says.append([])
    for j in range(ai):
        says[i].append(list(map(int, input().split())))
for bit in range(2**n):
    case = list(map(int, format(bit, "0%sb" % n)))
    truthes = []
    liers = []
    match = True
    for i, truth in enumerate(case):
        if truth == 1:
            truthes.append(i+1)
        else:
            liers.append(i+1)
    for i, truth in enumerate(case):
        if truth == 1:
            for say in says[i]:
                if say[1] == 1:
                    if say[0] in liers:
                        match = False
                        break
                else:
                    if say[0] in truthes:
                        match = False
                        break
    # print(truthes, liers, match)
    if match:
        maxcnt = max(maxcnt, len(truthes))
print(maxcnt)

Submission status: Accepted

Solution code:
N = int(input())
xyss = []
for i in range(N):
    A = int(input())
    xys = []
    for j in range(A):
        x, y = map(int, input().split())
        xys.append((x-1, y))
    xyss.append(xys)
 
ans = 0
for S in range(2**N):
    numHonest = 0
    isOK = True
    for i in range(N):  # 人i
        if (S>>i)&1 == 0:
            continue
 
        numHonest += 1
        xys = xyss[i]
        A = len(xys)
        for x, y in xys:  # 証言j
            if (S>>x)&1 != y:
                isOK = False
                break
        if not isOK:
            break
 
    if isOK:
        ans = max(ans, numHonest)
 
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def check(s):
        for i in range(n):
            if s>>i & 1:
                for j, y in to[i]:
                    if s >> j & 1 != y:
                        return False
        return True

    to = defaultdict(list)
    n = int(input())
    for i in range(n):
        a = int(input())
        for _ in range(a):
            x, y = MI()
            to[i].append([x - 1, y])
    ans = 0
    for s in range(1 << n):
        if check(s):
            ans = max(ans, bin(s).count("1"))
    print(ans)

main()

Submission status: Accepted

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

    ans = 0
    for i in range(1 << N):
        ok = True
        for j in range(N):
            if (i >> j & 1) != 1:
                continue
            for x, y in A[j]:
                if (i >> x & 1) ^ y:
                    ok = False
                    break
            if not ok:
                break
        if ok:
            cnt = 0
            for j in range(N):
                if (i >> j & 1) == 1:
                    cnt += 1
            ans = max(ans, cnt)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
data=[[]]
for i in range(n):
    a=int(input())
    xy=[list(map(int,input().split())) for i in range(a)]
    data.append(xy)
ans=0
for i in range(2**n):
    lst=[0]
    for j in range(n):
        if (i>>j)&1==1:
            lst.append(1)
        else:
            lst.append(0)
    for j in range(1,n+1):
        if lst[j]==1:
            for k,l in data[j]:
                if lst[k]==l:
                    continue
                else:
                    break
            else:
                continue
            break
    else:
        ans=max(ans,sum(lst))
print(ans)

Submission status: Accepted

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

ans = 0
for S in range(2**N):
    numHonest = 0
    isOK = True
    for i in range(N):  # 人i
        if (S>>i)&1 == 0:
            continue

        numHonest += 1
        xys = xyss[i]
        A = len(xys)
        for x, y in xys:  # 証言j
            if (S>>x)&1 != y:
                isOK = False
                break
        if not isOK:
            break

    if isOK:
        ans = max(ans, numHonest)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
N=int(input())
l=[[] for i in range(N)]
for i in range(N):
  a=int(input())
  for j in range(a):
    x,y=map(int,input().split())
    l[i].append((x-1,y))
ans=0
for t in itertools.product(range(2),repeat=N):
  miss=False
  for i in range(N):
    if t[i]==0:continue
    for x,y in l[i]:
      if not t[x]==y:break
    else:continue
    break
  else:ans=max(ans,sum(t))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [[] for i in range(n)]
for i in range(n):
    ai = int(input())
    for j in range(ai):
        x = list(map(int, input().split()))
        a[i].append(x)
ans = 0
for i in range(2 ** n):
    i_str = format(i, '0' + str(n) + 'b')
    flag = False
    z = [-1 for _ in range(n)]
    h = []
    for j in range(n):
        if i_str[j] == '1':
            h.append(j)
    for j in h:
        for x, y in a[j]:
            if z[x - 1] >= 0 and z[x - 1] != y:
                flag = True
                break
            elif z[x - 1] < 0:
                z[x - 1] = y
        if flag:
            break
    else:
        for zj, sj in zip(z, i_str):
            if zj >= 0 and zj != int(sj):
                flag = True
                break
    if not flag:
        ans = max(ans, sum(map(int, i_str)))
print(ans)

Submission status: Accepted

Solution code:
import sys


def main():
    # input = sys.stdin.readline
    N = int(input())

    test = [dict() for _ in range(N)]

    count = 0

    for i in range(N):
        M = int(input())
        for _ in range(M):
            j, b = map(int, input().split())
            test[i][j-1] = bool(b)

    for i in range(2**N):
        bit = format(i, 'b')
        bit = '0' * 15 + bit
        bit = bit[-N:]

        honest = set()
        liar = set()
        for i, s in enumerate(bit):
            if s == '1':
                honest.add(i)
            else:
                liar.add(i)

        m = len(honest)
        for j in honest:
            for g, r in test[j].items():
                if r and g in liar:
                    m = 0
                elif not r and g in honest:
                    m = 0

        count = max(count, m)
    print(count)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
table = [[-1]*(N) for i in range(N)]
for i in range(N):
    A = int(input())
    for j in range(A):
        x,y = map(int,input().split())
        table[i][x-1] = y
# print(table)
# table[i][x] 人iが人xを正直者;1,真偽不明:0,未言及:-1

ans = 0
for i in range(2**N):

    hito = [0]*N
    for j in range(N):
        if i >> j & 1:
            hito[j] = 1

    flag = True
    cnt = 0
    for j in range(N):
        if i >> j & 1:
            cnt += 1
            for k in range(N):
                if table[j][k] != -1:
                    if table[j][k] != hito[k]:
                        flag = False
    if flag:
        if cnt > ans:
            ans = cnt
print(ans)
#print(3 >> 0) # 3????

Submission status: Accepted

Solution code:
N = int(input())
T = [[]for i in range(N)]
for i in range(N):
    A = int(input())
    for j in range(A):
        t = list(map(int,input().split()))
        T[i].append(t)
S = []
for i in range(2**N):
    f = 1
    for j in range(N):
        for k in range(len(T[j])):
            x = T[j][k][0]-1
            y = T[j][k][1]
            if (i>>j)&1:
                if ((i>>x)&1)^y:
                    f = 0
    if f == 1:
        S.append(i)
n = len(S)
m = 0
for i in range(n):
    s = S[i]
    a = 0
    for j in range(N):
        if (s>>j)&1:
            a += 1
    m = max(a,m)
print(m)

Submission status: Accepted

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

def power2(n):
    if n == 1:
        return [[1], [0]]
    res = []
    for l in power2(n-1):
        res.append([1] + l)
        res.append([0] + l)
    return res

ans = 0
patterns = power2(N)
for p in patterns:
    flag = True
    for i, remark in enumerate(remarks):
        if p[i] == 0: #不親切者の発言を無視
            pass
        else:
            for w in remark:
                if p[w[0]-1] != w[1]: #発言の矛盾を判定:
                    flag = False 
                    break
                # print(w)
    if flag: #すべての発言で矛盾がなかった場合
        ans = max(ans, p.count(1))

print(ans)

Submission status: Accepted

Solution code:
def bin_(n):
    return str(bin(n))[2: ]

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

start = 2**N-1
max_ = 0
for i in range(2**N):
    num = i
    uso = 0
    
    keta=bin(num)[2:]
    
    while(len(keta)<N):
        keta = "0"+keta
    for j in range(N):
        if(keta[j]=="1"):
            for p in range(len(syougen[j])):
                
                x,y = syougen[j][p]
                if(keta[x] != str(y)):
                    uso = 1
                    break
    
    suuji = str(bin(num))[2:]
    count  = 0
    for i in range(len(suuji)):
        if(suuji[i]=="1"):
            count += 1
            
    if(uso==0):
        max_ = max(max_,count)
        
print(max_)

Submission status: Accepted

Solution code:
n = int(input())
a = list()
xy = list()
for i in range(n):
  A = int(input())
  XY = [tuple(map(int, input().split())) for i in range(A)]
  a.append(A)
  xy.append(XY)
honest = [None] * n
ans = 0
for i in range(2 ** n-1,-1,-1):
  mini_ans = 0
  honest = []
  for j in range(n):
    honest.append(i % 2)
    i = i // 2
  for k,v in enumerate(honest):
    if v:
      mini_ans += 1
      for x,y in xy[k]:
        x -= 1
        if honest[x] != y:
          break
      else:
        continue
      break
  else:
    ans = max(ans,mini_ans)
    continue
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
claim = [[] for _ in range(n)]

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

max_kind = 0
for i in range(2**n):
    state = str(format(i, 'b').zfill(n))
    flag = True
    for j in range(n):
#        print(state, j)
        if (i >> j) & 1:
            for statement in claim[j]:
                person, type = statement
#                print(claim, statement, len(state)-1-person-1, state[len(state)-person], type)
                if int(state[len(state)-person]) != type:
                    flag = False
                    break
        if flag != True: break
    if flag:
        max_kind = max(max_kind, list(state).count('1'))
print(max_kind)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Dec  8 21:12:35 2019

@author: over-
"""

N=int(input())
A=dict()
x=dict()
y=dict()
for i in range(1,N+1):
    A[i]=int(input())
    x[i]=dict()
    y[i]=dict()
    for j in range(A[i]):
        a1,a2=map(int,input().split())
        x[i][j+1]=a1
        y[i][j+1]=a2

C=2**N
ans=0
for c in range(C):
    honest=[]
    unkind=[]
    B='{:0b}'.format(c)
    B='0'*(N-len(B))+B
    bool=True
    for i in range(N):
        if int(B[i])==0:
            honest.append(i+1)
        else:   
            unkind.append(i+1)
        
    for k in range(1,N+1):
        if k in honest:
            for j in range(A[k]):
                if y[k][j+1]==1:
                    if x[k][j+1] in unkind:
                        bool=False
                else:
                    if x[k][j+1] in honest:
                        bool=False
    if bool: 
        if len(honest) > ans:
            ans= len(honest)
                        
print(ans)

Submission status: Accepted

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

def power2(n):
    if n == 1:
        return [[1], [0]]
    res = []
    for l in power2(n-1):
        res.append([1] + l)
        res.append([0] + l)
    return res

ans = 0
patterns = power2(N)
for p in patterns:
    flag = True
    for i, remark in enumerate(remarks):
        if p[i] == 0: #不親切者の発言を無視
            continue
        else:
            for w in remark:
                if p[w[0]-1] != w[1]: #発言の矛盾を判定:
                    flag = False 
                    break
                # print(w)
    if flag: #すべての発言で矛盾がなかった場合
        ans = max(ans, p.count(1))

print(ans)

Submission status: Accepted

Solution code:
def c_honest_or_unkind_2():
    N = int(input())
    Answers = []
    for _ in range(N):
        a = int(input())
        Answers.append([[int(i) for i in input().split()] for j in range(a)])

    ret = -1
    for bits in range(1 << N):
        honests = set()
        for k in range(N):
            if (bits >> k) & 1 == 1:
                honests.add(k)

        is_contradict = False
        for k, answer in enumerate(Answers):
            if k not in honests:
                continue  # k 人目は不親切な人としたので証言を調べない

            for x, y in answer:
                x -= 1
                # 証言に矛盾が生じた
                if (y == 0 and x in honests) or (y == 1 and not x in honests):
                    is_contradict = True
                    break
            if is_contradict:
                break  # 1つでも矛盾があれば全証言に矛盾があるとする
        else:
            # 全証言に矛盾がなかったので正直者の人数を更新する
            ret = max(ret, len(honests))
    return ret

print(c_honest_or_unkind_2())

Submission status: Accepted

Solution code:
import itertools

N = int(input())

syougen_list = []
for i in range(N):
    a_i = int(input())
    a_i_list = []
    for j in range(a_i):
        a_i_list.append(list(map(int, input().split())))
    syougen_list.append(a_i_list)


output = 0
for i in itertools.product([1,0], repeat=N):
    legal = True
    for index, j in enumerate(i):
        if j == 1:
            syougen = syougen_list[index]
            for k in syougen:
                if i[k[0] - 1] != k[1]:
                    legal = False
                    break
            if not legal:
                break
    if legal:
        number = i.count(1)
        if number >= output:
            output = number

print(output)

Submission status: Accepted

Solution code:
import random as rng
import itertools as it
import collections as col
import heapq as hq
import sys
import copy as cp
import bisect
sys.setrecursionlimit(10**9)


def dump_impl(*objects):
    print(*objects, file=sys.stderr)


def dump_dummy(*objects):
    pass


dump = dump_impl if "DEBUG" in sys.argv else dump_dummy

N = int(input())
T = [None]*N
for i in range(N):
    Ai = int(input())
    T[i] = [-1]*N
    for j in range(Ai):
        xij, yij = map(int, input().split())
        dump(i, xij-1, yij)
        T[i][xij-1] = yij
dump(T)


def imply(p, q): return (not p) or q


ans = -1
for trusts in it.product([0, 1], repeat=N):
    dump(trusts)
    ok = True
    for i, trust in enumerate(trusts):
        if trust:
            for j, tij in enumerate(T[i]):
                ok = ok and imply(tij == 1, trusts[j]) and (
                    imply(tij == 0, not trusts[j]))
    if ok:
        ans = max([ans, len([i for i in trusts if i == 1])])
    dump(ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

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

ans = 0

for honests in range(2 ** N):
    bit = '{:015b}'.format(honests)[::-1]
    ok_flag = True
    for i in range(N):
        if bit[i] == '1':
            for j, k in enumerate(testinomy[i]):
                str_k = str(k)
                if bit[j] == '1' and str_k != '0':
                    pass
                elif bit[j] == '0' and str_k != '1':
                    pass
                else:
                    ok_flag = False
                    break
                # if str_k != '-1':
                #     if str_k == '1' and bit[j] == '1':
                #         pass
                #     elif str_k == '0' and bit[j] == '0':
                #         pass
                #     else:
                #         ok_flag = False
                #         break
        if ok_flag == False:
            break
    if ok_flag:
        ans = max(ans, sum(map(int, bit)))

print(ans)

Submission status: Accepted

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

#print(l)
ans = 0
for i in range(2 ** n):
  #ans_ = 0
  flag = 0
  for j in range(n):
    if ((i >> j) & 1):
      #ans_ += 1
      for k in range(n):
        if l[j][k] == 1 and ((i >> k) & 1)==1:
          continue
        elif l[j][k] == 0 and ((i >> k) & 1)==0:
          continue
        elif l[j][k] == -1:
          continue
        else:
          #print(l[j][k], (i >> k))
          flag = 1
  if flag == 0:
    ans_ = 0
    for p in range(n):
      if ((i >> p) & 1):
        ans_ += 1
    ans = max(ans, ans_)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = ['']

res = []

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

allp = 2**N - 1

for i in range(allp, -1, -1):
    pat = bin(i).replace('0b', '')
    pat = pat.zfill(N)
    h_list = []
    l_list = []
    for (i, p) in enumerate(pat):
        t = i + 1
        if p == '1':
            if t in l_list:
                break
            h_list.append(t)
            for s in S[t]:
                if s[1] == 1:
                    if s[0] in l_list:
                        break
                    h_list.append(s[0])
                else:
                    if s[0] in h_list:
                        break
                    l_list.append(s[0])
            else:
                continue
            break
        else:
            if t in h_list:
                break
            l_list.append(t)
    else:
        res.append(pat)

maxA = 0
for r in res:
    maxA = max(maxA, r.count('1'))
print(maxA)

Submission status: Accepted

Solution code:
n = int(input())
s_dict = {}
for i in range(n):
  add_dict = {}
  a = int(input())
  for j in range(a):
    b = list(map(int, input().split()))
    add_dict[b[0]-1] = b[1]
  s_dict[i] = add_dict
max_num = 0

def rec_get_list(i, tmp_num_list, tmp_honest, tmp_unkind):
  add_dict = s_dict[i]
  tmp_num_list.add(i)
  tmp_honest.add(i)
  for k, v in add_dict.items():
      if v:
        if k not in tmp_num_list:
        	tmp_num_list, tmp_honest, tmp_unkind = rec_get_list(k, tmp_num_list, tmp_honest, tmp_unkind)
        tmp_honest.add(k)
      else:
        tmp_unkind.add(k)
  return tmp_num_list, tmp_honest, tmp_unkind

def rec_check(i, tmp_num_list, tmp_honest, tmp_unkind):
  global max_num
  global n
  for j in range(i, n):
    if j in tmp_num_list:
      continue
    use_num_list = tmp_num_list.copy()
    use_honest = tmp_honest.copy()
    use_unkind = tmp_unkind.copy()
    use_num_list, use_honest, use_unkind = rec_get_list(j, use_num_list, use_honest, use_unkind)
    check_flg = len(use_honest & use_unkind)
    if check_flg:
      continue
    else:
      if len(use_num_list) > max_num:
        max_num = len(use_num_list)
    if j+1 < n:
      rec_check(j+1, use_num_list, use_honest, use_unkind)
  
rec_check(0, set(), set(), set()) 
    
print(max_num)

Submission status: Accepted

Solution code:
import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
 
n = I()
ans = 0
lst = [[] for _ in range(n)]
for i in range(n):
    a = I()
    for j in range(a):
        x,y = LI()
        lst[i].append((x-1,y))
for i in range(2**n):
    b = [0]*n
    for j in range(n):
        if (i >> j) & 1:
            b[j] = 1
    flg = True
    for j in range(n):
        if b[j] == 0:
            continue
        for k,l in lst[j]:
            if l == 0:
                if b[k] == 1:
                    flg = False
                    break
            else:
                if b[k] == 0:
                    flg = False
                    break
        if not flg:
            break
    else:
        ans = max(ans,sum(b))
print(ans)

Submission status: Accepted

Solution code:
#import sys
MOD = 10 ** 9 + 7
#input = sys.stdin.readline
import math
import itertools

#import bisect

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


def main():
#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

    n = int(input())
    xy = [[] for i in range(n)]
    for i in range(n):
        a=int(input())
        for j in range(a):
            xy[i].append(list(map(int,input().split())))
    b=[-1 for i in range(n)]
    count=0
    for c in itertools.product(range(2),repeat=n):
        k=0
        for i in range(n):
            if c[i]==1 and k==0:
                for j in xy[i]:
                    if c[j[0]-1]!=j[1]:
                        k=1
                        break
        if k==0:
            count=max(count,sum(c))




    print(count)




#  print(c)




            #    print(n,kingaku(a,b,x))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = 0
for i in range(2**n):
  results = [None] * n
  for j in range(n):
    candidate = ((i >> j) & 1) == 1
    if results[j] is None:
      results[j] = candidate
    elif results[j] != candidate:
      break
    if candidate == False:
      continue
    elif candidate == True:
      failed = False
      for comment in comments[j]:
        if results[comment[0]] is None:
          results[comment[0]] = comment[1]
        if results[comment[0]] != comment[1]:
          failed = True
          break
      if failed:
        break
  else:
    cnt = len([r for r in results if r is True])
    if cnt > ans:
      ans = cnt

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
lst = [[] for i in range(N)]
for i in range(N):
  for j in range(int(input())):
    lst[i].append(list(map(int,input().split())))
ans = 0
for i in range(2**N):
  flag = True
  bin_lst = list(bin(i)[2:].zfill(N))
  for idx,j in enumerate(bin_lst):
    if (j == '1'):
      for v, w in lst[idx]:
        if (bin_lst[v-1] != str(w)):
          flag = False
  if (flag):
    ans = max(ans,bin_lst.count('1'))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s_dict = {}
for i in range(n):
  add_dict = {}
  a = int(input())
  for j in range(a):
    b = list(map(int, input().split()))
    add_dict[b[0]-1] = b[1]
  s_dict[i] = add_dict
max_num = 0

def rec_get_list(i, tmp_num_list, tmp_honest, tmp_unkind):
  add_dict = s_dict[i]
  tmp_num_list.add(i)
  tmp_honest.add(i)
  for k, v in add_dict.items():
      if v:
        if k not in tmp_num_list:
        	tmp_num_list, tmp_honest, tmp_unkind = rec_get_list(k, tmp_num_list, tmp_honest, tmp_unkind)
        tmp_honest.add(k)
      else:
        tmp_unkind.add(k)
  return tmp_num_list, tmp_honest, tmp_unkind

def rec_check(i, tmp_num_list, tmp_honest, tmp_unkind):
  global max_num
  global n
  for j in range(i, n):
    if j in tmp_num_list:
      continue
    use_num_list = tmp_num_list.copy()
    use_honest = tmp_honest.copy()
    use_unkind = tmp_unkind.copy()
    use_num_list, use_honest, use_unkind = rec_get_list(j, use_num_list, use_honest, use_unkind)
    check_flg = len(use_honest & use_unkind)
    if check_flg:
      continue
    else:
      if len(use_num_list) > max_num:
        max_num = len(use_num_list)
    if j+1 < n:
      rec_check(j+1, use_num_list, use_honest, use_unkind)
  
rec_check(0, set(), set(), set()) 
    
print(max_num)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC147 C

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
ans = 0
lst = [[] for _ in range(n)]
for i in range(n):
    a = I()
    for j in range(a):
        x,y = LI()
        lst[i].append((x-1,y))
for i in range(2**n):
    b = [0]*n
    for j in range(n):
        if (i >> j) & 1:
            b[j] = 1
    flg = True
    for j in range(n):
        if b[j] == 0:
            continue
        for k,l in lst[j]:
            if l == 0:
                if b[k] == 1:
                    flg = False
                    break
            else:
                if b[k] == 0:
                    flg = False
                    break
        if not flg:
            break
    else:
        ans = max(ans,sum(b))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
Adj = [[-1]*n for _ in range(n)]

for i in range(n):
    ai = int(input())
    for j in range(ai):
        xij,yij = map(int, input().split( ))
        xij -= 1
        Adj[i][xij] = yij###==ってなんぞ
#print(Adj)
ans = 0

bt = 1<<n

for b in range(bt):#全探索
    flag = True
    tmp = 0
    for i in range(n):
        for j in range(n):
            if Adj[i][j]>=0:
                if ((b>>i) &1) and not ((Adj[i][j]==0) ^ ((b>>j) &1)):#正直者の答えが矛盾,醜いがあとでビット演算子確認
                    flag = False
                    break
        if not flag:
            break
    if flag:
        for t in range(n):
            tmp += (b>>t)&1
            #print("test",b,tmp,flag)
    ans = max(tmp, ans)
    #print(b,ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = ['']

res = []

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

allp = 2**N - 1

for i in range(allp, -1, -1):
    pat = bin(i).replace('0b', '')
    pat = pat.zfill(N)
    h_list = []
    l_list = []
    for (i, p) in enumerate(pat):
        t = i + 1
        if p == '1':
            if t in l_list:
                break
            h_list.append(t)
            for s in S[t]:
                if s[1] == 1:
                    if s[0] in l_list:
                        break
                    h_list.append(s[0])
                else:
                    if s[0] in h_list:
                        break
                    l_list.append(s[0])
            else:
                continue
            break
        else:
            if t in h_list:
                break
            l_list.append(t)
            # for s in S[t]:
            #     if s[1] == 1:
            #         if s[0] in h_list:
            #             break
            #         l_list.append(s[0])
            #     else:
            #         if s[0] in l_list:
            #             break
            #         h_list.append(s[0])
            # else:
            #     continue
            # break
    else:
        res.append(pat)

maxA = 0
for r in res:
    maxA = max(maxA, r.count('1'))
print(maxA)