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 combinations
from collections import defaultdict


N = int(input().strip())

Pos = defaultdict(set)
Neg = defaultdict(set)
for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().strip().split())
        if y == 1:
            Pos[i + 1].add(x)
        else:
            Neg[i + 1].add(x)


def check(positive):
    positive_set = set(positive)
    for x in positive_set:
        if len(Pos[x] - positive_set) != 0:
            return False
        if len(Neg[x].intersection(positive_set)) != 0:
            return False
    return True


people_list = list(range(1, N + 1))
ans = 0
for i in range(N, 0, -1):
    positives = combinations(people_list, i)
    for p in positives:
        if check(p):
            ans = i
            break
    if ans > 0:
        break

print(ans)

Submission status: Accepted

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

    # print(A)
    P = []
    for i in range(2 ** N):
        b = format(i, 'b').zfill(N)
        P.append(b)

    ans = 0  # 矛盾がなかった場合の正直者の数
    for p in P:
        bits = list(p)  # 例: ['1', '0', '1']
        t = list(p)
        mujun = False
        for i, b in enumerate(bits):
            if b == '1':
                ss = A[i]  # 正直者の証言のリスト
                for x, y in ss:  # xはyである
                    if t[x-1] == str(y):
                        pass
                    else:
                        mujun = True
        if not mujun:
            syojiki = bits.count('1')
            ans = max(ans, syojiki)

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#import pysnooper
#import numpy
#import os,re,sys,operator
#from collections import Counter,deque
#from operator import itemgetter,mul
#from itertools import accumulate#,combinations,groupby,combinations_with_replacement,permutations
from sys import stdin,setrecursionlimit
#from bisect import bisect_left,bisect_right
#from copy import deepcopy
#import heapq
#import math
#import string
#from time import time
#from functools import lru_cache,reduce
#from math import factorial
#import sys

setrecursionlimit(10**6)
input=stdin.readline

n=int(input().rstrip())
info=[]
num=[]
ans=0
for _ in range(n):
    a=int(input().rstrip())
    num.append(a)
    x=[tuple(map(int,input().split())) for _ in range(a)]
    info.append(x)
for i in range(2**n):
    s=bin(i)[2:].zfill(n)
    now=s.count("1")
    check=[bool(int(ii)) for ii in s]
    ch=True
    for j in range(n):
        if (not ch) or (not check[j]): continue
        for k in range(num[j]):
            if check[info[j][k][0]-1]!=bool(info[j][k][1]):
                ch=False
                break
    if ch:
        ans=max(ans,now)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
x = []
y = []
# offsets
x.append([])
y.append([])
for i in range(N):
    A = int(input())
    xtmp = []
    ytmp = []
    for _ in range(A):
        xx, yy = [int(x) for x in input().split()]
        xtmp.append(xx)
        ytmp.append(yy)
    x.append(xtmp)
    y.append(ytmp)

num_honest = 0

for i in range(2**N):
    is_honest_inv = '{:015b}'.format(i) + '0' # add dummy
    is_honest = [int(is_honest_inv[15-i]) for i in range(N+1)]
    # print(is_honest_inv, is_honest)
    is_ok = True
    for j in range(1, N+1):
        for xx, yy in zip(x[j], y[j]):
            # print(xx, yy, is_honest[xx])
            if is_honest[j] == 1:
                if is_honest[xx] != yy:
                    is_ok = False
                    break
        if not is_ok:
            break
    if is_ok:
        num_honest = max(num_honest, sum(is_honest))
        # print(f'OK: {num_honest}')
print(num_honest)

Submission status: Accepted

Solution code:
N = int(input())
A = []
for i in range(N):
  A.append([])
  A_tmp = int(input())
  for j in range(A_tmp):
    XY = [int(k) for k in input().split()]
    XY[0]-=1
    A[i].append(XY)

ans = 0


for i in range(2**N):
  bin_i_list = [int(x) for x in '{:0=15b}'.format(i)]
  bin_i_list.reverse()
  bin_i_list = bin_i_list[:N]
  judge = True
  #Judge
  for j in range(len(A)):
    if bin_i_list[j] != 0:
      for XY in A[j]:
        X =XY[0]
        Y =XY[1]
        if bin_i_list[X] != Y:
          judge = False
          break
  if judge:
    ans = max(ans,bin_i_list.count(1))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

E = []

for n in range(N):
    A = int(input())
    for _ in range(A):
        x, y = list(map(int, input().split()))
        E.append((n, x-1, y))

ans = 0
for k in range((1<<N)-1, -1, -1):
    l = [(k>>i)&1 for i in range(N)]
    OK = True
    for e0, e1, e2 in E:
        if (l[e0]==1 and l[e1]!=e2):
            OK = False
            break
    if OK: ans = max(ans, sum(l))

print(ans)

Submission status: Accepted

Solution code:
#import pysnooper
#import numpy
#import os,re,sys,operator
#from collections import Counter,deque
#from operator import itemgetter,mul
#from itertools import accumulate#,combinations,groupby,combinations_with_replacement,permutations
from sys import stdin,setrecursionlimit
#from bisect import bisect_left,bisect_right
#from copy import deepcopy
#import heapq
#import math
#import string
#from time import time
#from functools import lru_cache,reduce
#from math import factorial
#import sys

setrecursionlimit(10**6)
input=stdin.readline

n=int(input().rstrip())
info=[]
num=[]
ans=0
for _ in range(n):
    a=int(input().rstrip())
    num.append(a)
    x=[tuple(map(int,input().split())) for _ in range(a)]
    info.append(x)
#print(info)
for i in range(2**n):
    s=bin(i)[2:].zfill(n)
    now=s.count("1")
    check=[bool(int(ii)) for ii in s]
    ch=True
    for j in range(n):
        #print(check)
        if (not ch) or (not check[j]): continue
        for k in range(num[j]):
            #print(check[info[j][k][0]-1],info[j][k][1])
            if check[info[j][k][0]-1]!=bool(info[j][k][1]):
                ch=False
                break
    #print(ch)
    if ch:
        ans=max(ans,now)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

N=int(input())

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

s=[0,1]
lis=list(product(s,repeat=N))

L=len(lis)
ans=0
for i in range(L): 
    f=True
    for j in range(N):
        if lis[i][j]==1:
            for k in range(len(P[j])):
                if P[j][k][1]==lis[i][P[j][k][0]]:
                    continue
                else:
                    f=False
                    break
            if f==False:
                break
    if f:
        cnt=lis[i].count(1)
        ans=max(ans,cnt)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
d = [-1] * N
a = []
x = [[0, 0] for _ in range(N)]
cnt = 0
def dfs(v):
    global cnt
    if v == N:
        cntF = True
        for i in range(N):
            if d[i] != 1:
                continue
            for j in range(len(a[i])):
                if a[i][j][1] != d[a[i][j][0] - 1]:
                    cntF = False
                    break
            if cntF == False:
                break

        if cntF:
            cnt = max(cnt, sum(d))
        return

    d[v] = 0
    dfs(v + 1)
    d[v] = 1
    dfs(v + 1)
    return

for i in range(N):
    tmp = int(input())
    tmplst = [[0, 0] for _ in range(tmp)]
    for j in range(tmp):
        x1, y1 = map(int, input().split())
        tmplst[j][0] = x1
        tmplst[j][1] = y1
    a.append(tmplst)
dfs(0)
print(cnt)

Submission status: Accepted

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

ans = 0
for i in range(2**N):
    flag = False
    cnt = 0
    bit = bin(i)[2:].zfill(N)
    memo2 = [int(b) for b in bit]
    # print(i, ans)
    for ii, b in enumerate(memo2):
        cnt += b
        if b:
            for x, y in memo[ii]:
                if memo2[x] == y:
                    continue
                else:
                    flag = True
                    break
        else:
            continue
            # for x, y in memo[ii]:
            #     if memo2[x] != y:
            #         continue
            #     else:
            #         flag = True
            #         break
        if flag:
            break
    if flag:
        continue
    ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = [0]*n
for i in range(n):
  a = int(input())
  A[i] = [ tuple(map(int, input().split())) for _ in range(a) ]
ans = 0
for i in range(2**n):
  P = [2]*n
  f = False
  for j in range(n):
    if i >> j & 1:
      if P[j] != 2 and P[j] ^ 1:
          f = True
          break
      P[j] = 1
      for x, y in A[j]:
        if P[x-1] != 2 and P[x-1] ^ y:
          f = True
          break
        P[x-1] = y
  if f:
    continue
  c = bin(i).count("1")
  if P.count(1) <= c:
    ans = max(ans, c)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
dh = [[] for i in range(N)]
du = [[] for i in range(N)]
for i in range(N):
    t = int(input())
    for j in range(t):
        x, y = map(int, input().split())
        if y == 1: dh[i].append(x-1)
        else: du[i].append(x-1)

best = 0
def check(bitmask):
    global best
    isH = [False for i in range(N)]
    isU = [False for i in range(N)]
    
    for i in range(N):
        if bitmask % 2:
            isH[i] = True
        else:
            isU[i] = True
        bitmask //= 2
    
    valid = True
    for i in range(N):
        if isU[i]: continue
        for t in dh[i]:
            if isU[t]: valid = False
        for t in du[i]:
            if isH[t]: valid = False

    if valid: best = max(best, sum(isH))

for i in range(pow(2, N)): check(i)

print(best)

Submission status: Accepted

Solution code:
n=int(input())
s=[[] for i in range(n)]
for i in range(n):
  a=int(input())
  for j in range(a):
    s[i].append(list(map(int,input().split())))
for i in range(2**n)[::-1]:
  cnt=format(i,"b").zfill(n)
  flag=0
  for j in range(n):
    if cnt[j]=="0":
      continue
    else:
      for h in s[j]:
        if int(cnt[h[0]-1])^h[1]==1:
          flag=1
          break
      if flag:
        break
  if flag==0:
    print(cnt.count("1"))
    exit()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N = int(input())
A = [[] for i in range(N)]

def check(target):
    one_count = 0
    cans = 0
    for idx, flag in enumerate(target):
        if flag == "1":
            one_count += 1
            for x, y in A[idx]:
                if int(target[x]) != y:
                    return 0
    
    cans = max(cans, one_count)
    return cans

def dns(S):
    ans = 0
    if len(S) == N:
        ans = max(ans, check(S))
    else:
        ans = max(dns(S+"0"), dns(S+"1"))
    
    return ans

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

kotae = dns("")

print(kotae)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
from itertools import combinations

def _i(): return int(sys.stdin.readline().strip())
def _ia(): return [ int(x) for x in sys.stdin.readline().strip().split() ]

n = _i()
xy = list()
for _ in range(n):
    tmp = []
    for _ in range(_i()):
        x,y = _ia()
        tmp.append((x-1,y))
    xy.append(tmp)
#
a = set(range(n))
for f in range(n+1):
    for p in combinations(range(n),f):
        h = a - set(p)
        tmp = [ None ] * n
        flag = True
        for i in h:
            if not i in h: continue
            for x,y in xy[i]:
                if y==1 and x not in h:
                    flag = False
                    break
                if y==0 and x in h:
                    flag = False
                    break
                #
                tx = tmp[x]
                if tx is None:
                    tmp[x] = y
                else:
                    if tx==y: continue
                    else:
                        flag = False
                        break
            #
            if not flag: break
        if flag:
            print(n-f)
            exit()

Submission status: Accepted

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

mh,h = 0,0
f = True

for i in range(2**n):
    # 全探索
    p = bin(i)
    p = p[2:].zfill(n)
    h = p.count("1")
    f = True
    for j in range(n):
        # 全探索で得られたすべてのパターンに対し
        if (p[j] == "1"):
            # j人目が正直者のとき
            for k in range(a[j]):
                # j人目の全ての証言に対し
                if (y[j][k] != int(p[x[j][k]])):
                    #実際の状況と合致していなければ X
                    f = False
    if (f):
        if (mh < h):
            mh = h

print(mh)

Submission status: Accepted

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())
wit = [[] for _ in range(N)]
A = []

for i in range(N):
    A = int(stdin.readline().rstrip())
    for n in range(A):
        wit[i].append([int(x) for x in stdin.readline().rstrip().split()])

ans = 0

for i in range(2 ** N):
    s = bin(i)[2:].zfill(N)
    one_cnt = 0
    tmp = 0
    for j in range(N):
        if s[j] == '1':
            one_cnt += 1
            cnt = 0
            for k in wit[j]:
                if k[1] == 1:
                    if s[k[0] - 1] == '1':
                        cnt += 1
                elif k[1] == 0:
                    if s[k[0] - 1] == '0':
                        cnt += 1
            if cnt == len(wit[j]):
                tmp += 1
    if tmp == one_cnt:
        ans = max(ans, one_cnt)

print(ans)

Submission status: Accepted

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

for i in range(2**n-1, -1, -1):
  #print('0%db' % n)
  num = format(i, '0%db' % n)
  #print(num)
  flag = False
  for j in range(n):
    #print(num[j])
    if int(num[j]) == 1:
      for k in range(a[j]):
        #print(xy[j][k])
        if int(num[xy[j][k][0]-1]) != xy[j][k][1]:
          flag = True
          break
      if flag:
        break
  if not flag:
    cnt = 0
    for l in range(n):
      if int(num[l]):
        cnt += 1
    break
print(cnt)

Submission status: Accepted

Solution code:
from itertools import product
def trueCheck(i,x):
    for j in range(1,N+1):
        if B[i][j]==1:
            if x[j-1]==0:
                return 1
        elif B[i][j]==0:
            if x[j-1]==1:
                return 1
    return 0
N = int(input())
A = [0]
B = {i:[-1 for _ in range(N+1)] for i in range(1,N+1)}
for i in range(1,N+1):
    A.append(int(input()))
    for _ in range(A[-1]):
        x,y = map(int,input().split())
        B[i][x] = y
cmax = 0
for z in product([0,1],repeat=N):
    flag = 0
    for i in range(1,N+1):
        if z[i-1]==1:
            flag = trueCheck(i,z)            
        if flag==1:break
    if flag==0:
        cmax = max(cmax,sum(z))
print(cmax)

Submission status: Accepted

Solution code:
#import copy
N = int(input())
a = []
s = []
for i in range(N):
    a.append(int(input()))
    tmp = []
    for j in range(a[i]):
        tmp.append(list(map(int,input().split())))
    s.append(tmp)
#print(a)
#print(s)
def dfs(i,honest):
    if i==N:
        #print(honest)
        for h in honest:
            for j in range(a[h-1]):
                #print("{},{},{}".format(s[a[h-1]][j][0],s[a[h-1]][j][1],j))
                if s[h-1][j][1] == 1:
                    if s[h-1][j][0] not in honest:
                        return 0
                else:
                    if s[h-1][j][0] in honest:
                        return 0
        return len(honest)
    return max([dfs(i+1, honest+[i+1]),dfs(i+1, honest)])

print(dfs(0,[]))

Submission status: Accepted

Solution code:
def read():
    N = int(input().strip())
    A = []
    X = []
    Y = []
    for i in range(N):
        
        a = int(input().strip())
        A.append(a)
        x = [-1 for i in range(a)]
        y = [-1 for i in range(a)]
        for i in range(a):
            x[i], y[i] = list(map(int, input().strip().split()))
            x[i] -= 1
        X.append(x)
        Y.append(y)
    return N, A, X, Y

def is_honest(ptn, x):
    return (ptn >> x) & 1

def count_honest(ptn, N):
    count = 0
    for i in range(N):
        if is_honest(ptn, i):
            count += 1
    return count

def check_ptn(ptn, N, A, X, Y):
    count = 0
    for i in range(N):
        if is_honest(ptn, i) == 1:
            for x, y in zip(X[i], Y[i]):
                if is_honest(ptn, x) != y:
                    return False
    return True


def solve(N, A, X, Y):
    ptns = 1 << N
    max_honest = 0
    for ptn in range(ptns):
        if check_ptn(ptn, N, A, X, Y):
            n_honest = count_honest(ptn, N)
            if n_honest > max_honest:
                max_honest = n_honest
    return max_honest

if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

Submission status: Accepted

Solution code:
# coding: utf-8
n = int(input())

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

result = 0
for i in range(2**n):
    katei = []
    is_out = 0
    ninzu = 0
    for j in range(n):
        if int(i / (2**(j))) % 2:
            katei.append(1)
            ninzu += 1
        else:
            katei.append(0)
    if ninzu <= result:
        continue
    for j in range(n):
        if katei[j] == 1:
            for gen in syogen[j]:
                if katei[gen[0]-1] != gen[1]:
                    is_out = 1
    if is_out == 0:
        result = ninzu

print(result)

Submission status: Accepted

Solution code:
n = int(input())
hf = [[None] for i in range(n)]

for i in range(n):
    tmp = []
    for j in range(int(input())):
        tmp.append(list(map(int, input().split())))
    hf[i] = tmp
ans = 0
for i in range(2 ** n):
    f = 0
    b = bin(i)[2:].zfill(n)
    for j in range(n):
        if b[j] == "0":
            continue
        else:
            for x, y in hf[j]:
                if b[x - 1] != str(y):
                    f = 1
    if f == 0:
        ans = max(ans, b.count("1"))
print(ans)

Submission status: Accepted

Solution code:
def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista

def wszystkie_mozliwosci(N):
    if N==0:
        return [[]]
    poprzedni = wszystkie_mozliwosci(N-1)
    wynik = []
    for przyp in poprzedni:
        wynik.append(przyp + [False])
        wynik.append(przyp + [True])
    return wynik

def C():
    N = wczytaj_liste()[0]
    zeznania = []
    odp = 0
    for i in range(N):
        A = wczytaj_liste()[0]
        zeznania.append([])
        for j in range(A):
            x, y = wczytaj_liste()
            zeznania[-1].append((x-1,y))
    
    for czy_szczery in wszystkie_mozliwosci(N):
        dasie = True
        for i in range(N):
            if czy_szczery[i]:
                for x,y in zeznania[i]: 
                    if y == 1 and not czy_szczery[x]:
                        dasie = False
                    if y == 0 and czy_szczery[x]:
                        dasie = False
        if dasie:
            ile_szczerych = sum(czy_szczery)
            if ile_szczerych > odp:
                odp = ile_szczerych

    print(odp)
C()

Submission status: Accepted

Solution code:
N = int(input())

import collections
i2unkinds = collections.defaultdict(set)
i2honest = collections.defaultdict(set)
for i in range(N):
  A = int(input())
  for _ in range(A):
    x, y = map(int, input().split())
    if (y == 0):
      i2unkinds[i].add(x - 1)
    else:
      i2honest[i].add(x - 1)



ans = 0
def recursive(i, says, honest, unkinds):
  if i == N:
    if not (honest & unkinds) and not (honest ^ says) and says:
      global ans
      ans = max(ans, len(honest))
  else:
    recursive(i + 1, says | {i}, honest | {i} | i2honest[i], unkinds | i2unkinds[i])
    recursive(i + 1, says, honest, unkinds)

recursive(0, set(), set(), set())
print(ans)

Submission status: Accepted

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

def check(bit,P):
  con = False
  T = [-1]*N
  for i in range(N):
    if bit[i] == '1':
      for j in range(N):
        if P[i][j] == 1:
          if bit[j] == '0':
            return True        
        elif P[i][j] == 0:
          if bit[j] == '1':
            return True
  return False
          

cnt = 0
for i in range(2**N):
  bit = bin(i)[2:].zfill(N)
  if not check(bit,P):
    cnt = max(cnt,bit.count('1'))
    #print(bit)

    
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
xy = [[] for _ in range(n)]
for i in range(n):
  a = int(input())
  for j in range(a):
    x, y = map(int, input().split())
    x -= 1
    xy[i] += [[x, y]]
result = 0
for i in range(2**n):
  dic = {i:-1 for i in range(n)}
  flag = True 
  ans = 0
  for j in range(n):
    if (i>>j)&1:
      if dic[j] != -1 and dic[j] != 1:
        flag = False
        break
      dic[j] = 1
      for x, y in xy[j]:
        if dic[x] == -1:
          dic[x] = y 
        elif dic[x] != -1 and dic[x] != y:
          flag = False
          break
      if flag:
        ans += 1
    else:
      if dic[j] != -1 and dic[j] == 1:
        flag = False
        break
      dic[j] = 0
      """
      for x, y in xy[j]:
        if dic[x] == -1:
          dic[x] = 1-y 
        elif dic[x] != -1 and dic[x] == y:
          flag = False
          break
      """

  if flag:
    result = max(result, ans)

print(result)

Submission status: Accepted

Solution code:
import itertools

#n桁のm値のbitを生成
def bit(n, m):
    bit_list = list(itertools.product([i for i in range(m)], repeat=n))
    return bit_list

N = int(input())

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

bits = bit(N, 2)
res = 0
for ptr in bits:
    flag = True
    result = [0 for _ in range(N)]

    for i in range(N):
        if ptr[i] == 1:
            result[i] = 1 # 真
        else:
            result[i] = -1 # 戯

    for i in range(N):
        if ptr[i] == 1:
            for j in range(len(A[i])):
                if A[i][j][1] == 0:
                    if result[A[i][j][0] - 1] == 1:
                        flag = False
                        break
                else:
                    if result[A[i][j][0] - 1] == -1:
                        flag = False
                        break
        else:
            if result[i] == 1:
                break
            result[i] = -1

        if flag == False:
            break

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

        res = max(res, tmp)

print(res)

Submission status: Accepted

Solution code:
n = int(input())
data = [[]for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        data[i].append(list(map(int, input().split())))
max_honest = 0
def bfs(honest):
    if len(honest) == n:
        global max_honest
        for i in range(len(data)):
            if honest[i] == 1:
                for j in data[i]:
                    target, istrue = j
                    if (honest[target-1] == 1 and istrue == 0) or (honest[target-1] == 0 and istrue == 1):
                        return
            else:
                continue
        max_honest = max(max_honest, honest.count(1))
    else:
        bfs(honest + [0])
        bfs(honest + [1])
bfs([])
print(max_honest)

Submission status: Accepted

Solution code:
N = int(input())

t = []

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

ans = 0

for i in range(1 << N):
    ok = 1
    for j in range(N):
        if 1 << j & i:
            for a_t in t[j]:
                if 1 << (a_t[0]-1) & i:
                    if a_t[1] != 1:
                        ok = 0
                        break
                else:
                    if a_t[1] != 0:
                        ok = 0
                        break
        if ok == 0:
            break
    if ok:
        if ans < sum(list(map(int, list(bin(i)[2:])))):
            ans = sum(list(map(int, list(bin(i)[2:]))))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
lis = [[] for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        lis[i].append(tuple(map(int,input().split())))

from itertools import product

ans = 0
for i in product((0,1),repeat=n):
    for j,k in enumerate(i):
        if k==0:
            continue
        else:
            if all(map(lambda x:i[x[0]-1]==x[1],lis[j])):
                continue
            else:
                break
    else:
        ans = max(ans,sum(i))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

stm = [[] for i in range(n)]

def possible(honest):
    #print(honest)
    for i in range(n):
        if honest[i] == '0':
            continue
        for j in range(len(stm[i])):
            #print(stm[i][j])
            #print(honest[stm[i][j][0]-1])
            if stm[i][j][1] == 1 and honest[stm[i][j][0]-1] == '0':
                return False
            elif stm[i][j][1] == 0 and honest[stm[i][j][0]-1] == '1':
                return False
    return True

            

for i in range(n):
    a = int(input())
    for _ in range(a):
        x,y = map(int, input().split())
        stm[i].append([x,y])
   
count = 0
for k in range(2**n):
    hon = list(bin(k)[2:])
    hon = ['0']*(n-len(hon)) + hon
    if possible(hon):
        count = max(count, sum([int(x) for x in hon]))
print(count)

Submission status: Accepted

Solution code:
from itertools import product
n = int(input())
xys = []
for _ in range(n):
    a = int(input())
    tmp = []
    for _ in range(a):
        x, y = map(int, input().split())
        tmp.append((x-1, y))
    xys.append(tmp)

ans = 0
for people in product(range(2), repeat=n):
    isOK = True

    for i in range(n):
        if not people[i]:
            continue
        for x, y in xys[i]:
            if people[x] != y:
                isOK = False
                break

        if not isOK:
            break

    if isOK:
        ans = max(ans, sum(people))

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**N):
    temp_ans = 0
    network = [0] * N
    for j in range(N):
        if (i >> j) & 1:
            temp_ans += 1
            network[j] = 1
    for hito in range(N):
        flg = False
        if network[hito] == 1:
            for x, y in xys[hito]:
                if network[x - 1] != y:
                    flg = True
                    break
            if flg:
                break
    else:
        # print(ans, temp_ans, i)
        ans = max(ans, temp_ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
info = [[] for _ in range(N)]
people = [-1] * N
for i in range(N):
    A = int(input())
    if A == 0:
        info[i].append([0])
    for j in range(A):
        x , y = map(int,input().split())
        info[i].append([A , x - 1 , y])
#print(info[0][0][0])
ans = 0
# ビット全探索を行う
for i in range(2 ** N):
    cnt = 0
    Flag = True
    # ビットが１の時、正直者としてpeopleに格納
    for j in range(N):
        if i >> j & 1:
            cnt += 1
            people[j] = 1
        else:
            people[j] = 0
    for j in range(N):
        # 正直者の発言と実際に正直者であるかを判定
        if i >> j & 1:
            info_num = info[j][0][0]
            for k in range(info_num):
                judge = info[j][k][2]
                origin = people[info[j][k][1]]
                if judge != origin:
                    Flag = False
                    break
        if not Flag:
            break
    if Flag:
        if ans < cnt:
            ans = cnt
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
s=[[-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())
        s[i][x-1]=y
from itertools import product
r=0
for t in product((0,1),repeat=N):
    f=1
    for i in range(N):
        for j in range(N):
            if not ((t[i]==1 and s[i][j] in (t[j],-1)) or t[i]==0):
                f=0
    if f==1:
        r=max(r,sum(t))
print(r)

Submission status: Accepted

Solution code:
N = int(input())
T = [[] for k in range(N)]
for p in range(N):
    A = int(input())
    for k in range(A):
        x, y = map(int,input().split())
        T[p].append([x-1,y])

ans = 0
for k in range(2**N):
    t = []
    f = []
    for d in range(N):
        if (k>>d)&1 == 1:
            t.append(d)
        else:
            f.append(d)
    flag = 1
    for p in range(N):
        if p in t:
            for e in T[p]:
                if e[1] == 1 and e[0] in f:
                    flag = 0
                    break
                elif e[1] == 0 and e[0] in t:
                    flag = 0
                    break
    if flag == 1:
        ans = max(ans,len(t))
print(ans)