Problem:


Score : 300 points

Problem Statement

There are N people numbered 1 to N. Each of them is either an honest person whose testimonies are always correct or an unkind person whose testimonies may be correct or not.

Person i gives A_i testimonies. The j-th testimony by Person i is represented by two integers x_{ij} and y_{ij}. If y_{ij} = 1, the testimony says Person x_{ij} is honest; if y_{ij} = 0, it says Person x_{ij} is unkind.

How many honest persons can be among those N people at most?

Constraints

All values in input are integers.

1 \leq N \leq 15

0 \leq A_i \leq N - 1

1 \leq x_{ij} \leq N

x_{ij} \neq i

x_{ij_1} \neq x_{ij_2} (j_1 \neq j_2)

y_{ij} = 0, 1

Input

Input is given from Standard Input in the following format:

N
A_1
x_{11} y_{11}
x_{12} y_{12}
:
x_{1A_1} y_{1A_1}
A_2
x_{21} y_{21}
x_{22} y_{22}
:
x_{2A_2} y_{2A_2}
:
A_N
x_{N1} y_{N1}
x_{N2} y_{N2}
:
x_{NA_N} y_{NA_N}

Output

Print the maximum possible number of honest persons among the N people.

Sample Input 1

3
1
2 1
1
1 1
1
2 0

Sample Output 1

2

If Person 1 and Person 2 are honest and Person 3 is unkind, we have two honest persons without inconsistencies, which is the maximum possible number of honest persons.

Sample Input 2

3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0

Sample Output 2

0

Assuming that one or more of them are honest immediately leads to a contradiction.

Sample Input 3

2
1
2 0
1
1 0

Sample Output 3

1



Sample input:
3
1
2 1
1
1 1
1
2 0


Sample output:
2

Submission status: Accepted

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

maxi = 0
for m in range(2**n):
  num = 0
  flg = False
  for i in range(n):
    if ((m >> i) & 1):
      num += 1
      for x, y in con[i]:
        if (((m >> x) ^ y) & 1):
          flg = True
          break
      if flg:
        break
  if not flg:
    maxi = max(num, maxi)
print(maxi)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for i in range(n)]
    for i in range(n):
        a = I()
        for j in range(a):
            x,y = LI()
            x -= 1
            v[i].append((x,y))
    m = 1<<n
    ans = 0
    for b in range(m):
        f = [1 if b&(1<<i) else 0 for i in range(n)]
        for i in range(n):
            for x,y in v[i]:
                if f[i]:
                    if f[x] != y:
                        break
            else:
                continue
            break
        else:
            na = sum(f)
            if ans < na:
                ans = na
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import itertools

N = int(input())

speak_list = [] #証言を格納する配列
for i in range(N):
  speak_list.append([-1]*(N))

for i in range(N):
  A = int(input())
  for j in range(A):
   x,y = map(int,input().split())
   x,y = x-1,y
   speak_list[i][x] = y #i番目の人がx番目の人を「y」と証言 
    
    
#(方針)最大2^15通り 試して 「正直者(1)が不親切(0)」と言っている人が
#     親切(1)になる場合そのパターンは不可と考える
ori = [0,1]
Comb = list(itertools.product(ori, repeat=N))
ans = 0

for i in range(len(Comb)):
 tmp = list(Comb[i]) #ex: (N=3)0,0,1
 
 #正直者の言ったこと格納用
 X = []
 for i in range(N):
  X.append([-1]*(N))
 
 for i in range(N):
  if(tmp[i] == 1): #正直者なら
   for j in range(N): #言ったことを反映
    X[i][j] = speak_list[i][j]
  
 judge = 0 #矛盾なし 
 for i in range(N):
  for j in range(N):
    if(X[i][j] != -1): #正直者か不親切者か言われているなら
      if((X[i][j] == 1)and(tmp[j] == 0)): #矛盾が生じるなら
        judge = 1 
        break  
      if((X[i][j] == 0)and(tmp[j] == 1)): #矛盾が生じるなら
        judge = 1 
        break  
  
 #矛盾が生じないなら       
 if(judge == 0):
   ans = max(ans,sum(tmp))
   #sum(tmp) : 1の個数
    
print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
l = [None]*N
for i in range(N):
    k = int(input())
    tmp = [None]*k
    for j in range(k):
        tmp[j] = list(map(int,input().split(' ')))
    l[i] = tmp

M = 0
A = [2]*N
n = 2**N
for i in range(2**N):#1の人が正しいとする
    bin_num = bin(i)
    bin_str = str(bin_num)
    bin_str = bin_str[2:].zfill(N)
    k = list(bin_str)
    flag = False
    for j in range(N):
        s = k[j]
        if s=='1':
            correct = l[j]
            for num,opinion in correct:
                if k[num-1]!=str(opinion):
                    flag = True
                    break
            if flag:
                break
    if not flag:
        M = max(M,sum(list(map(int, bin_str))))
print(M)

Submission status: Accepted

Solution code:
N = int(input())
xy = []
for i in range(N):
    A = int(input())
    xy.append([[int(i) for i in input().split()] for _ in range(A)])
ans = 0
for n in range(2**N):
    b = bin(n)[2:].zfill(N)
    s = 0
    for i, bi in enumerate(b):
        if bi == '0':
            continue
        for x, y in xy[i]:
            if b[x-1] == str(y):
                pass
            else:
                break
        else:
            s += 1
            continue
        break
    else:
        ans = max(ans, s)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
xy = []
check = 0
for i in range(n):
    a = int(input())
    if a ==0:
        check+=1
    for j in range(a):
        x,y=map(int,input().split())
        xy.append([i+1,x,y])
        
ans = 0
for i in range(2**n):
    temp=check
    se=set()
    for idx,x,y in xy:
        if i>>(idx-1) & 1:
            if i>>(x-1) & 1:
                if y==1 and idx not in se:
                    temp+=1
                    se.add(idx)
                elif y==0:
                    break
            else:
                if y==0 and idx not in se:
                    temp+=1
                    se.add(idx)
                elif y==1:
                    break
    else:
        ans=max(ans,temp)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

talk = []
for i in range(N):
        talk_num = int(input())
        tmp_talk = [list(map(int, input().split())) for j in range(talk_num)]
        talk.append(tmp_talk) 


ans = 0
for i in range(2 ** N):
        tmp = []
        flag = False
        for j in range(N):
                if ((i >> j) & 1):
                        tmp.append(1)
                else:
                        tmp.append(0)
        for k in range(len(tmp)):
                if tmp[k] == 0:
                        continue
                else:
                        for x in talk[k]:
                                #矛盾していないかを確認
                                if x[1] != tmp[x[0] - 1]:
                                        flag = True
                                        break
                if flag:
                        break
        if flag == False:
                ans = max(ans, sum(tmp))             

print(ans)

Submission status: Accepted

Solution code:
#[int(i) for i in input().split()]
n = int(input())
dic = {}
for i in range(n):
    a = int(input())
    dic[i+1] = [a]
    for j in range(a):
        dic[i+1].append([int(k) for k in input().split()])
#print(dic)
#dic[i] = {[0,1]} i = 1 ~ n+1 ,   0は対象, 1は真偽
ls = []
#全員正直者から
#for i in range(1,n):
#    for j in range(i+1,n+1):
#        ls.append([i,j])
#print(ls)


ret = 2 ** n - 1

for i in range(ret,-1,-1):
    ls.append(format(i, '0'+str(len(format(ret,'b')))+'b'))
#print(ls)
ls_3 = []
ok = 1
ans = 0
for i in range(len(ls)):
    for j in range(len(format(ret,'b'))):
         if ls[i][j] == '1':
            ls_3.append(j+1)
    #print(dic)
    for j in ls_3:
        for k in range(1,dic[j][0]+1):
            if dic[j][k][1] == 1 and dic[j][k][0] not in ls_3:
                ok = 0
            if dic[j][k][1] == 0 and dic[j][k][0] in ls_3:
                ok = 0
    if ok == 1:
        ans = ls[i].count('1')
        break
    ls_3 = []
    ok = 1

print(ans)

Submission status: Accepted

Solution code:
import collections
def main():

    N = int(input())
    dh = collections.defaultdict(set)
    dl = collections.defaultdict(set)
    for i in range(1, N+1):
        A = int(input())
        for _ in range(A):
            x, y = map(int, input().split())
            if y == 1:
                dh[i].add(x)
            else:
                dl[i].add(x)

    case = [[0], [1]]
    for _ in range(N-1):
        temp = []
        for lv in case:
            temp.append(lv + [0])
            temp.append(lv + [1])
        case = temp

    ans = 0
    for lv in case:
        h = set()
        l = set()
        # print(h)
        # print(lv)
        for i in range(len(lv)):
            if lv[i] == 1:
                h.add(i+1)
                h |= dh[i+1]
                l |= dl[i+1]

        prevh = len(h)
        prevl = len(l)
        while  True:
            addh = set()
            addl = set()
            for i in h:
                addh |= dh[i]
                addl |= dl[i]
            h |= addh
            l |= addl
            if prevh == len(h) and prevl == len(l):
                break
            prevh = len(h)
            prevl = len(l)

        # print(h.intersection(l), h, l)
        if len(h.intersection(l)) == 0:
            ans = max(ans, len(h))
    return ans



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

Submission status: Accepted

Solution code:
import itertools


num_person = int(input())

testimony = []
for i in range(0, num_person):
    honest = set()
    dishonest = set()
    num_test = int(input())
    for _ in range(0, num_test):
        target, test = map(int, input().split())
        target -= 1
        if test:
            honest.add(target)
        else:
            dishonest.add(target)
    testimony.append((honest, dishonest))

ans = [0]
for t in itertools.product((1, 0), repeat=num_person):
    honest = {i for i in range(0, num_person) if t[i]}
    dishonest = {i for i in range(0, num_person) if not t[i]}
    for i in range(0, num_person):
        if t[i]:
            honest.add(i)
            honest = honest.union(testimony[i][0])
            dishonest = dishonest.union(testimony[i][1])
    if honest.intersection(dishonest):
        continue
    else:
        ans.append(sum(t))

print(max(ans))
exit(0)

Submission status: Accepted

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

def main():
    N = int(input())
    # S = input().rstrip()
    mS = [[] for _ in [0,]*(N+1)]
    for i in range(N):
        Ai = int(input())
        for j in range(Ai):
            x, y = map(int, input().split())
            mS[i+1].append((x,y))

    # T1, T2 = map(int,input().split())
    # A1, A2 = map(int,input().split())
    # B1, B2 = map(int,input().split())
    # vA = list(map(int, input().split()))

    res = 0
    # print(mS)
    M = 1<<N
    for m in range(M):
        vS = []
        vH = [-1]*(N+1)
        cnt = 0
        d = 0
        while m:
            if m&1:
                vS.extend(mS[d+1])
                vH[d+1] = 1
                cnt += 1
            d += 1
            m >>= 1
        
        ok_in_xy = True
        while vS:
            x,y = vS.pop()
            if vH[x] == -1:
                vH[x] = y
                if y:
                    vS.extend(mS[x])
            elif vH[x] != y:
                ok_in_xy = False
                break

        if ok_in_xy:
            res = max(res, cnt)

    print(res)


main()

Submission status: Accepted

Solution code:
# C
N = int(input())
enter = []
A = [0] * N
for a in range(N):
    ai = int(input())
    tmp_enter = [list(map(int, input().split())) for _ in range(ai)]
    A[a] = ai
    enter.append(tmp_enter)

ans_list = [0]
for i in range(2 ** N):
    # iは誰が正直者かを表す
    honest = []
    unkind = []
    flag = True
    for j in range(N):
        if (i >> j) & 1:
            honest.append(j)
        else:
            unkind.append(j)
    ##print(i, honest, unkind)
    for h in honest:
        for k in range(A[h]):
            if enter[h][k][1] == 1:
                if (enter[h][k][0]-1) in unkind:
                    flag = False
                    break
            if enter[h][k][1] == 0:
                if (enter[h][k][0]-1) in honest:
                    flag = False
                    break
    if flag:
        ans_list.append(len(honest))
print(max(ans_list))

Submission status: Accepted

Solution code:
N = int(input())
A = [[] for _ in range(N)]
for i in range(N):
  a = int(input())
  for j in range(a):
    A[i].append(tuple(map(int,input().split())))
#print(A)

ans = 0
for i in range(1<<N):
  B = [0 for _ in range(N)]
  for j in range(N):
    if (i>>j)&1 == 1:
      B[j] = 1
  #print(B)
  flag = True
  for j in range(N):
    if B[j] == 1:
      for x,y in A[j]:
        if (y == 1 and B[x-1] == 0) or (y == 0 and B[x-1] == 1):
          flag = False
          break
    if not flag:
      break
  if flag:
    ans = max(sum(B),ans)
print(ans)

Submission status: Accepted

Solution code:
import unittest


class TestC(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think([[[2, 1]], [[1, 1]], [[2, 0]]]), 2)

    def test_2(self):
        self.assertEqual(think([[[2, 1], [3, 0]], [[3, 1], [1, 0]], [[1, 1], [2, 0]]]), 0)

    def test_3(self):
        self.assertEqual(think([[[2, 0]], [[1, 0]]]), 1)

    def test_4(self):
        self.assertEqual(count_bits_one(1), 1)

    def test_5(self):
        self.assertEqual(count_bits_one(2), 1)

    def test_6(self):
        self.assertEqual(count_bits_one(3), 2)

    def test_7(self):
        self.assertEqual(count_bits_one(31), 5)


def solve():
    list_of_testimony = read()
    result = think(list_of_testimony)
    write(result)


def read():
    n = read_int(1)[0]
    list_of_testimony = []
    for _ in range(n):
        list_of_x_y = []
        a = read_int(1)[0]
        for __ in range(a):
            list_of_x_y.append(read_int(2))
        list_of_testimony.append(list_of_x_y)
    return list_of_testimony


def read_int(n):
    return read_type(int, n)


def read_float(n):
    return read_type(float, n)


def read_type(t, n):
    return list(map(lambda x: t(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(data):
    max_bits = 2 ** len(data)
    result = 0
    for bits in range(max_bits):
        # print(is_legal(bits, data), bits)
        if is_legal(bits, data):
            result = max(result, count_bits_one(bits))
    return result


def is_legal(bits, data):
    n = len(data)
    for i in range(n):
        if not is_honest(i, bits):
            continue
        for x, y in data[i]:
            if y == 1:
                if not is_honest(x - 1, bits):
                    return False
            else:
                if is_honest(x - 1, bits):
                    return False
    return True


def is_honest(i, bits):
    # print('is_honest', i, bits, (bits >> i) % 2 == 1)
    return (bits >> i) % 2 == 1


def count_bits_one(bits):
    count = 0
    while bits > 0:
        if bits % 2 == 1:
            count += 1
        bits //= 2
    return count


def write(result):
    print(result)


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Accepted

Solution code:
def get_switch(n):
    allswitch = []
    for i in range(0,2**n):
        bin_str = format(i,'0'+str(n)+'b')
        swt = list(map(int,list(bin_str)))
        allswitch.append(swt)
    return allswitch

def test(patarn,a,x,y,n):
    ans_sub=sum(patarn)
    for i in range(n):
        if patarn[i]==1:
            for j in range(a[i]):
                if y[i][j]==1:
                    if patarn[x[i][j]]==0:
                        return 0
                else:
                    if patarn[x[i][j]]==1:
                        return 0
        #else:
            #f.append(i)
            #if i in t:
                #return 0
    #print(patarn)
    return ans_sub
    
def main():
    n=int(input())
    a=[]
    x=[]
    y=[]
    for i in range(n):
        a_sub=int(input())
        a.append(a_sub)
        x_sub=[]
        y_sub=[]
        for j in range(a_sub):
            tmp=list(map(int,input().split()))
            x_sub.append(tmp[0]-1)
            y_sub.append(tmp[1])
        x.append(x_sub)
        y.append(y_sub)
    #print(x)
    #print(y)
    ans=0
    for patarn in get_switch(n):
        ans=max(ans,test(patarn,a,x,y,n))
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import math
import queue
import bisect
import heapq
import time
import itertools

mod = 1e9+7
global a,n,xy,ans

def swap(a,b):
    return (b,a)

def gcd(a,b): #最大公約数
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def divisors(a): # 約数列挙
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def is_prime(a): #素数判定
    if a<2:
        return False
    elif a==2:
        return True
    elif a%2==0:
        return False
    sqrt_num = int(a**0.5)
    for i in range(3,sqrt_num+1,2):
        if a%i==0:
            return False
    return True

def prime_num(a): #素数列挙
    pn = [2]
    for i in range(3,int(a**0.5),2):
        prime = True
        for j in pn:
            if i%j==0:
                prime = False
                break
        if prime:
            pn.append(i)
    return pn


def func():
    global a,n,xy,ans
    count = 0
    for i in range(n):
        for j in xy[i]:
            if a[i]:
                if a[j[0]]!=j[1]:
                    return
        if a[i]:
            count += 1
    ans = max(ans,count)

def dfs(pos):
    global n
    if pos==n:
        func()
        return
    a[pos] = 0
    dfs(pos+1)
    a[pos] = 1
    dfs(pos+1)

def main():
    global a,n,xy,ans
    n = int(input())
    xy = []
    for i in range(n):
        a = int(input())
        xy.append([])
        for j in range(a):
            x,y = map(int,input().split())
            xy[i].append([x-1,y])
    a = [0 for i in range(n)]
    ans = 0
    dfs(0)
    print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product
n = int(input())
li = list(product([1,0], repeat=n))
A = [[]] * n
for i in range(n):
  a = int(input())
  A[i] = [list(map(int, input().split())) for _ in range(a)]
  
cnt = 0
for i in li:
  flg = False
  for itr, val in enumerate(i):
    if val == 1:
      if not all([i[x[0]-1] == x[1] for x in A[itr]]):
        flg = True
        break
  if flg == False:
    cnt = max(cnt, sum(i))
print(cnt)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bit_count(i):

    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    i = (i + (i >> 4)) & 0x0f0f0f0f
    i = i + (i >> 8)
    i = i + (i >> 16)
    return i & 0x3f

N = INT()
A = []
for i in range(N):
    a = []
    for j in range(INT()):
        x, y = MAP()
        a.append((x-1, y))
    A.append(a)

def check(a):
    for x, y in a:
        if honest[x] == -1:
            honest[x] = y
            if y == 1:
                if not check(A[x]):
                    return False
        elif honest[x] != y:
            return False
    return True

ans = 0
for S in range(1<<N):
    honest = [-1] * N
    valid = True
    for i in range(N):
        if S & (1<<i):
            honest[i] = 1
    for i in range(N):
        if S & (1<<i):
            if not check(A[i]):
                valid = False
    if valid:
        ans = max(ans, bit_count(S))
print(ans)

Submission status: Accepted

Solution code:
def f(s):
    cnt=0
    for i in range(len(s)):
        if s[i]=="1":
            cnt+=1
    return cnt
n=int(input())
a=[0]*n
x=[0]*n
for i in range(n):
    a[i]=int(input())
    x[i]=[list(map(int,input().split())) for j in range(a[i])]
    for j in range(a[i]):
        x[i][j][0]-=1
#print(x)
b=2**n
s = [bin(i)[2:] for i in range(b)]
for i in range(b):
    s[i]='0'*(n-len(s[i]))+s[i]
    s[i]=s[i][::-1]
ans=0

for i in range(b):
    cnt=0
    z=False
    for j in range(n):
        if s[i][j]=="1":
            for k in range(a[j]):
                if int(s[i][x[j][k][0]])!=x[j][k][1]:
                    z=True
                    break
            if z:
                break
        if j==n-1:
            cnt=f(s[i])
    ans=max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
xy = [[]] * N
for i in range(N):
  A = int(input())
  xy[i] = [list(map(int, input().split())) for j in range(A)]
# print(xy)

def check(a):
  for i in range(N):
    if a[i] == 0:
      continue
    for x, y in xy[i]:
      if a[x-1] != y:
        return -1
  return a.count(1)

r = 0
for i in range(2**N):
  bstr = format(i, '0%db' % N)
  a = tuple(map(int, bstr))
  # print(a)
  t = check(a)
  if t > r:
    r = t 
print(r)

Submission status: Accepted

Solution code:
import sys

N = int(input())
evid_lst = []
for i in range(N):
    tmp_a = int(input())
    tmp_lst = []
    for j in range(tmp_a):
        tmp_lst.append(tuple(map(int, input().split())))
    evid_lst.append(tmp_lst)

honest_sets = []
for i in range(2 ** N - 1, 0, -1):
    honest_expect = set()
    for j in range(N):
        if ((i >> j) & 1):
            honest_expect.add(j + 1)
    honest_sets.append(honest_expect)

honest_sets.sort(key=lambda x: -len(x))
for h in honest_sets:
    flag = False
    for i in h:
        for evid in evid_lst[i - 1]:
            if evid[1] == 0:
                if evid[0] in h:
                    flag = True
                    break
            else:
                if not evid[0] in h:
                    flag = True
                    break
        if flag:
            break
    if not flag:
        print(len(h))
        sys.exit()
print(0)

Submission status: Accepted

Solution code:
n = int(input())

xy = []
a_list = []

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

num = 2**n
hito = []
flag = True

for i in reversed(range(num)):
    #print(i)
    hito = []
    tmp = i
    while tmp != 0:
        if tmp % 2 == 1:
            hito.append(1)
        else:
            hito.append(0)
        tmp //= 2
    """
    if len(hito) == 2:
        hito.append(0)
    elif len(hito) == 1:
        hito.append(0)
        hito.append(0)
    elif len(hito) == 0:
        hito.append(0)
        hito.append(0)
        hito.append(0)
    """
    if len(hito) != n:
        for j in range(n-len(hito)):
            hito.append(0)
    
    hito = hito[::-1]
    #print(hito)
    
    number = 0
    flag = True
    #print(hito)
    
    for j in range(n):
        #print(j)
        for k in range(a_list[j]):
            #正しいことを言う人
            if hito[j] == 1:
                #print(number,hito[xy[number][0]] , xy[number][1])
                if hito[xy[number][0]-1] != xy[number][1]:
                    flag = False
            number += 1
    if flag == True:
        print(sum(hito))
        exit()
        
print(0)
exit()

Submission status: Accepted

Solution code:
import itertools as it

N = int(input())
xy = []
for i in range(N):
    A_i = int(input())
    xy_i = []
    for j in range(A_i):
        tmp = [int(i) for i in input().split()]
        xy_i.append(tmp)
    xy.append(xy_i)
ans = 0
for conf in it.product(range(2), repeat=N):
    is_consist = True
    # honest 1, evil 0
    for i in range(N):
        if conf[i] == 0:
            continue
        # i is honest
        for jth_state in range(len(xy[i])):
            if xy[i][jth_state][1] != conf[xy[i][jth_state][0] - 1]:
                is_consist = False
                break
    if is_consist:
        ans = max(ans, sum(conf))
print(ans)

Submission status: Accepted

Solution code:
import sys
n = int(input())
a = [[-1 for _ in range(n)] for _ in range(n)]
for i in range(n):
    j = int(input())
    for s in range(j):
        x, y = map(int, input().split())
        a[i][x-1] = y
r = 0
for i in range(2**n):
    s = bin(i)
    t = s[2:]
    t = t.rjust(n, '0')
    c = 1
    for j in range(n):
        if t[j] == '0':
            continue
        else:
            for p in range(n):            
                    if int(t[p]) == a[j][p] or a[j][p] == -1:
                        continue
                    else:
                        c = 0
                        break
    if c:
        r = max(r, sum(map(int, list(t))))
print(r)

Submission status: Accepted

Solution code:
n = int(input())

p = [[] for _ in range(n)]

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

ans = 0

for i in range(2 ** n):
    a = [0]*n
    for j in range(n):
        if ((i>>j) & 1):
            a[j] = 1
    chk = 0
    for j in range(n):
        if a[j] != 1:
            continue
        else:
            if not all(a[s[0]] == s[1] for s in p[j]):
                chk = 1
    if chk != 1:
        ans = max(ans,sum(a))

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
root=[[] for i in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        root[i].append((x-1,y))
k=2**n
h=[0]*n
idx=0
for i in range(k):
    buf=i
    flag=True
    #print(h)
    for j in range(n):
        h[j]=buf%2
        buf=buf//2
    for j in range(n):
        if h[j]==1:
            for x,y in root[j]:
                if h[x]!=y:
                    flag=False
                    break
        if flag==False:
            break
    if flag==True:
        idx=max(idx,sum(h))

print(idx)

Submission status: Accepted

Solution code:
N=int(input())
#S=  [ [-1] * N for i in range(N)]
S=[ [] * N for i in range(N)]
#print(S)
for i in range(N):
  a=int(input())
  for j in range(a):
    x,y=map(int,input().split())
    #S[i][x-1]=y
    S[i].append([x-1,y])
#print(S)
ans=0
P=[0]*N
#print(P)
for i in range(2**N):
  tmp=0
  for j in range(N):
    if P[j]==0:
      P[j]=1
      break
    else:
      P[j]=0
  #print(P,sum(P))
  if sum(P)<=ans:
    continue
  flag=0
  for p in range(len(P)):
    if P[p]==1:
      for s in S[p]:
        if s[1]!=P[s[0]]:
          flag=1
  if flag==1:
    continue
  else:
    ans=sum(P)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
from inspect import currentframe
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def MI() : return map(int, input().split())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def chkprint(*args) : names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}; print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

N = I()
XY = []

for i in range(N):
    alen = I()
    tmp = [-1] * N

    for j in range(alen):
        x, y = LI()
        tmp[x - 1] = y

    XY.append(tmp)

ret = 0
for i in range(2 ** N):
    if i == 0:
        continue

    ans = [(i >> j) & 1 for j in range(N)]
    
    flag = True
    for e, a in enumerate(ans):
        if a != 1:
            continue

        for b, c in zip(XY[e], ans):
            if b == -1:
                continue
            if b!= c:
                flag = False
        
    if flag:
        ttt = 0
        for d in ans:
            if d == 1:
                ttt += 1
        ret = max(ret, ttt)

print(ret)

Submission status: Accepted

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

max_honesty = 0
for i in range(2 ** n):
    num = bin(i + 2 ** n)[3:]
    honest = 0
    flag = True
    for j in range(len(num)):
        if num[j] == "0":
            continue
        else:
            for k in range(len(xy[j])):
                if int(num[xy[j][k][0] - 1]) == xy[j][k][1]:
                    continue
                else:
                    flag = False
                    break
            if flag == True:
                honest += 1
    if flag == True:
        max_honesty = max(max_honesty, honest)
print(max_honesty)

Submission status: Accepted

Solution code:
n = int(input())
x = [None] * n
y = [None] * n
for i in range(n):
    a = int(input())
    x[i] = [0] * a
    y[i] = [0] * a
    for j in range(a):
        x[i][j], y[i][j] = map(int, input().split())
ans = 0
for i in range(2 ** n):
    a = [-1] * n
    cnt = 0
    for j in range(n):
        tmp = (i >> j) & 1
        cnt += tmp
        if tmp == 1:
            for p, q in zip(x[j], y[j]):
                if ((i >> (p - 1)) & 1) != q:
                    break
                a[p - 1] = q
            else:
                continue
            break
    else:
        for j in range(n):
            tmp = (i >> j) & 1
            if a[j] != -1 and a[j] != tmp:
                break
        else:
            ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [[] for i in range(N)]

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

ans = 0
for bits in range(2**N):
  l = [0] * N
  for i in range(N):
    l[i] = (bits >> i) % 2

  fail = False
  for i in range(N):
    if fail: break
    if l[i] == 0: continue # 不親切はパス
    for x, y in A[i]:
      if y != l[x-1]:
        fail = True
        break
  else:
    if not fail:
      ans = max(ans, sum(l))

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

ans = 0
for C in product([0,1], repeat=N):
  if sum(C) <= ans:
    continue
  for i, c in enumerate(C):
    if c:
      for x, y in XY[i]:
        if C[x-1] != y:
          break
      else:
        continue
      break
  else:
    ans = max(ans, sum(C))

print(ans)