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:
# 不親切な人の証言は、正しかろうが間違っていようが検証できないので無視する
# bit全探索で正直者を仮定・固定して、証言に矛盾が出なければ人数を数えて記録する
from itertools import product
n = int(input())
Ev = [[] for _ in range(n)]

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

bit = list(product([1, 0], repeat=n))

ans = 0
for b in bit:
    for i, v in enumerate(b):  # v == 1 or 0
        if v == 1:
            for x, y in Ev[i]:  # 証言１つ１つを取り出して検証
                if b[x] != y:  # bitで仮定している正直者リストと矛盾する証言を正直者が行ったらアウト
                    break
            else:
                continue
            break
    else:
        ans = max(b.count(1), ans)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

dic = {(i,j):set([]) for i in range(1,N+1) for j in range(2)}

for i in range(1,N+1):
  a = int(input())
  for _ in range(a):
    x,y = map(int, input().split())
    dic[(i,y)].add(x)
    
p = 2**N
rlt = 0

for b in range(p):
  s0 = set([])
  s1 = set([])
  for i in range(N):
    if b&(1<<i):
      s1.add(i+1)
    else:
      s0.add(i+1)
  f = 1
  for i in s1:
    for k in dic[(i,1)]:
      if k in s0:
        f = 0
        break
    for k in dic[(i,0)]:
      if k in s1:
        f = 0
        break
    if f == 0:
      break
  if f == 1:
    rlt = max(len(s1),rlt)
    
print(rlt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[15]:


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


# In[16]:


ans = 0
for i in range(2**N):
    for j,a_list in enumerate(xy_list):
        if (i>>j)&1 == 1:
            for k,(x,y) in enumerate(a_list):
                if (i>>(x-1))&1 != y:
                    break
            else:
                continue
            break
    else:
        ans = max(ans, bin(i)[2:].count("1"))
print(ans)


# In[ ]:

Submission status: Accepted

Solution code:
n = int(input())
g = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    for _ in range(a):
        x,y = map(int,input().split())
        g[i].append((x-1,y))
ans = 0
for bit in range(1<<n):
    f = True
    for i in range(n):
        if bit&(1<<i) and f:
            for x,y in g[i]:
                if y ==1 and bit&(1<<x):
                    continue
                elif y ==0 and bit&(1<<x)==0:
                    continue
                else:
                    f = False
                    break
    if f:
        ans = max(ans,bin(bit).count('1'))
print(ans)

Submission status: Accepted

Solution code:
#ABC147　C　やってる途中
n=int(input())
l=[]
for i in range(n):
  a=int(input())
  l_=[]
  for j in range(a):
    xy=list(map(int,input().split()))
    l_.append(xy)
  l.append(l_)
ans=0
for i in range(2**n):
  table=[0]*n
  flag=False
  for j in range(n):
    if (i>>j)&1:
      table[j]=1
  for j in range(n):
    for k in l[j]:
   
      if k[1]!=table[k[0]-1] and table[j]==1:
        flag=True
        break

        if flag:
          break

  if flag==True:
    continue


  ans = max(ans, table.count(1))


print(ans)

Submission status: Accepted

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

ans=0
for r in range(2**n):
  ans1=0
  za=[0 for i in range(n)]
  for w in range(n):
    if (r>>w)&1:
      ans1+=1
      za[w]+=1
  ch=0
  for h in range(n):
    if za[h]==1:
      for p in s[h]:
        A=p[0]-1
        B=p[1]
        if za[A]!=B:
          ch+=1
  if ch==0:
    ans=max(ans,ans1)
    
print(ans)

Submission status: Accepted

Solution code:
#C - HonestOrUnkind2
N = int(input())
A = []
X = []
Y = []
for _ in range(N):
    a = int(input())
    A.append(a)
    box_x = []
    box_y = []
    for _ in range(a):
        x,y = map(int,input().split())
        box_x.append(x)
        box_y.append(y)
    X.append(box_x)
    Y.append(box_y)

person = [2]*N

maxim = 0
for i in range(1<<N):
    c_person = person.copy()
    honest = 0
    for j in range(N):
        mask = 1<<j
        if mask&i != 0:
            c_person[j] = 1
        else:
            c_person[j] = 0
    #正直者かどうかの仮定
    for k,l in enumerate(c_person):
        #kが正直者のとき
        if l == 1:
            #kの証言を判定
            for m,n in zip(X[k],Y[k]):
                #矛盾があるなら honest = 0でbreak
                if c_person[m-1] != n:
                    honest = 0
                    break
            else:
                honest = sum(c_person)
                continue
            break
    maxim = max(maxim,honest)
                
print(maxim)

Submission status: Accepted

Solution code:
N=int(input())
T=[[] for _ in range(N)]
for i in range(N):
  n=int(input())
  for j in range(n):
    T[i].append(tuple(map(int,input().split())))
ans=0
for i in range(2**N):
  true,t,f=set(),set(),set()
  for j in range(N):
    if i>>j&1:
      true.add(j+1)
      for a,b in T[j]:
        if b:
          t.add(a)
        else:
          f.add(a)
  if t<=true and not(f&true):
    ans=max(ans,len(true))
print(ans)

Submission status: Accepted

Solution code:
import itertools
n=int(input())
s=[[] for i in range(n)]
for i in range(n):
  a=int(input())
  for j in range(a):
    x,y=[int(x) for x in input().split()]
    x-=1
    s[i].append([x,y])

l=[]
a=itertools.product(range(2),repeat=n)
for i in a:
  l.append(i)

ans=0
for i in range(2**n):
  c=[]
  for j in range(n):
    if l[i][j]==1:
      for k in s[j]:
        if l[i][k[0]]!=k[1]:
          c.append(False)
  if c==[]:
    ans=max(ans,sum(l[i]))
print(ans)

Submission status: Accepted

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

ans=0

for katei in range(2**n):
    hantei=katei
    muzyun=False
    for i in range(1,n+1):
        if hantei & 1:
            for j in range(len(syougen[i])):
                taisyou=syougen[i][j][0]
                if katei>>taisyou-1 & 1 != syougen[i][j][1]:
                    muzyun=True
                    break
        hantei>>=1
    if muzyun==False:
        ans=max(bin(katei).count("1"),ans)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ans = 0
al = []
xy = [[] for _ in range(n)]
for k in range(n):
    a = int(input())
    al.append(a)
    for l in range(a):
        x,y = map(int,input().split())
        xy[k].append([x,y])
for i in range(2**n):
    kinds = [0]*n
    jud = 1
    for j in range(n):
        if (i >> j) & 1:
            kinds[j] = 1
    for k in range(n):
        if kinds[k] == 1:
            a = al[k]
            for l in range(a):
                x = xy[k][l][0]
                y = xy[k][l][1]
                if kinds[x-1] != y:
                    jud = 0
    if jud == 1:
        ans = max(ans,kinds.count(1))
print(ans)

Submission status: Accepted

Solution code:
#
# abc147 c
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
1
2 1
1
1 1
1
2 0"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """2
1
2 0
1
1 0"""
        output = """1"""
        self.assertIO(input, output)


def resolve():
    N = int(input())
    C = []
    for i in range(N):
        a = int(input())
        C.append([list(map(int, input().split())) for j in range(a)])

    ans = 0
    for bit in range(1 << N):
        f = True
        for i in range(N):
            if bit & (1 << i):
                for c in C[i]:
                    if bit & (1 << c[0]-1) != (1 << c[0]-1)*c[1]:
                        f = False
                        break
        if f == True:
            ans = max(ans, bin(bit).count("1"))
    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
#
# abc147 c
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
1
2 1
1
1 1
1
2 0"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """2
1
2 0
1
1 0"""
        output = """1"""
        self.assertIO(input, output)


def resolve():
    N = int(input())
    C = []
    for i in range(N):
        a = int(input())
        C.append([list(map(int, input().split())) for j in range(a)])

    ans = 0
    for bit in range(1 << N):
        t = 0
        for i in range(N):
            if bit & (1 << i):
                for c in C[i]:
                    if bit & (1 << c[0]-1) != (1 << c[0]-1)*c[1]:
                        break
                else:
                    t += 1
        if t == bin(bit).count("1"):
            ans = max(ans, t)
    print(ans)


if __name__ == "__main__":
     # unittest.main()
     resolve()

Submission status: Accepted

Solution code:
N = int(input())
a = [0] * N
xy = [[]] * N
for i in range(N):
    a[i] = int(input())
    xy[i] = [list(map(int, input().split())) for _ in range(a[i])]
# print(xy)
ans = 0
for i in range(2 ** N):
    tf = [False] * N
    for j in range(N):
        if (i >> j) & 1:
            tf[j] = True
    flag = False
    for j in range(N):
        for k in xy[j]:
            # 正直者が嘘をついたことになれば矛盾している
            if tf[j] and k[1] != tf[k[0] - 1]:
                flag = True
                break
        if flag:
            break
    if flag:
        continue
    ans = max(ans, tf.count(True))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [0] * n
xy = [[]] * n
for i in range(n):
    a[i] = int(input())
    xy[i] = [list(map(int, input().split())) for j in range(a[i])]
ans = 0
for i in range(2**n):
    tf = [False] * n
    for j in range(n):
        if (i>>j) & 1:
            tf[j] = True
    flag = False
    for j in range(n):
        for k in xy[j]:
            if tf[j] and k[1] != tf[k[0]-1]:
                flag = True
                break
        if flag:
            break
    if flag:
        continue
    ans = max(ans, tf.count(True))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
h = [[] for _ in range(n)]
u = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        if y == 1:
            h[i].append(x)
        elif y == 0:
            u[i].append(x)

ans = 0
for i in range(2**n):
    hs, us = set(), set()
    honest, unkind = set(), set()
    for j in range(n):
        if i & (1 << j):
            hs |= set(h[j])
            us |= set(u[j])
            honest.add(j+1)
        else:
            unkind.add(j+1)
    if not hs <= honest:
        continue
    if not us <= unkind:
        continue
    ans = max(ans, len(honest))

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

n=int(input())
w=[]
ans=chk=0
for i in range(n):
    a=int(input())
    t=[]
    for j in range(a):
        x,y=map(int,input().split())
        t.append((x,y))
    w.append(t)
for i in range(1,2**n):
    l=[0]*n
    for j in range(n):
        if i&1: l[j]=1
        i=i>>1
    chk=1
    for j in range(n):
        if l[j]:
            for k in w[j]:
                if l[k[0]-1]!=k[1]:
                    chk=0
                    break
    if chk: ans=max(ans,sum(l))
print(ans)

Submission status: Accepted

Solution code:
import itertools

n=int(input())

lis=[]
for i in range(n):
    ai=int(input())
    lisi=[]
    for _ in range(ai):
        xi,yi=map(int,input().split())
        lisi.append([xi-1,yi])
    lis.append(lisi)


ans=-1
for binary in itertools.product([1,0],repeat=n):
    check=0
    for i in range(n):
        if binary[i]==1:
            for j in range(len(lis[i])):
                if binary[lis[i][j][0]]!=lis[i][j][1]:
                    check+=1
    if check==0:
        ans=max(ans,sum(binary))

print(ans)

Submission status: Accepted

Solution code:
import itertools

N = int(input())
# [[1番の人の証言], [2番の人の証言], ..., [N番の人の証言]]
l = [[-1 for _ in range(N)] for _ in range(N)]
# N人についてそれぞれ証言をまとめる
for i in range(N):
    # 証言の数
    a = int(input())
    # 各証言をlに格納
    for _ in range(a):
        x, y = map(int, input().split())
        l[i][x - 1] = y

ans = 0

# 全通りを列挙
perm = list(itertools.product([0, 1], repeat=N))
# それぞれの選び方について
for p in perm:
    flag = True
    # pの中身を左から順に見ていく
    for j in range(N):
        # 既に破綻していたら、以降は証言をチェックする必要はない
        if flag == False:
            break
        # jの全員に対する証言について
        for k in range(N):
            # 狂人(p[j]==0)の証言は意味がないので無視して良い
            if p[j] == 1:
                # l[j][k] == -1 なら、その人に対する証言は存在しない
                # kについての証言と、kの実情が異なる場合（矛盾）
                if l[j][k] != -1 and l[j][k] != p[k]:
                    flag = False
                    break

    # 一つも矛盾が存在しなかった場合
    # sum(d)は聖人の総数を表す
    if flag == True:
        ans = max(ans, sum(p))

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
n = int(input())
state = [None] + [[set(),set()] for _ in range(n)]

for i in range(1,n+1):
    a = int(input())
    for _ in range(a):
        x,y = map(int,input().split())
        if y == 0:
            state[i][0].add(x)
        if y == 1:
            state[i][1].add(x)

ans = 0
#正直者の人数を仮定
for i in range(1,n+1):
    #正直者の選び方を仮定
    for j in combinations(list(range(1,n+1)), i):
        assum = set(j)
        state_lst = []
        #正直者の証言抽出
        for each_state in j:
            state_lst.append(state[each_state])
        #証言の矛盾を確認
        for each_state in state_lst:
            crr0 = assum.isdisjoint(each_state[0])
            crr1 = assum >= each_state[1]
            crr = crr0 and crr1
            if not crr:
                break
        else:
            ans = i

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = []
L = []
for i in range(N):
  a = int(input())
  A.append(a)
  tmp = []
  for i in range(a):
    tmp.append(list(map(int, input().split())))
  L.append(tmp)

ans = 0
for i in range(1, 2**N):
  tmp = [-1] * N
  flag = True
  d = []
  for j in range(N):
    if (i>>j) & 1:
      if tmp[j] == 0:
        flag = False
        break
      tmp[j] = 1
      l = L[j]
      for k in range(len(L[j])):
        p, t = l[k][0], l[k][1]
        if tmp[p-1] < 0:
          tmp[p-1] = t
        elif tmp[p-1] != t:
          flag = False
          break
      if flag == False:
        break
    else:
      d.append(j)
  for m in range(len(d)):
    n = d[m]
    if tmp[n] == 1:
      flag = False
      break
  if flag:
    ans = max(ans, tmp.count(1))
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

N = int(input())

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

ans = 0
for i in range(0,2**N):
    flag = 1
    for j in range(N):
        if ((i >> j) & 1):
            for xx in x[j]:
                if xx[1] == 1:
                    if not ((i >> xx[0]) & 1):
                        flag = 0
                        break
                else:
                    if ((i >> xx[0]) & 1):
                        flag = 0
                        break

        if flag == 0:
            break

    if flag == 0:
        continue
    else:
        ans = max(ans, popcount(i))

print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A_lst = [0] * N
    xy_lst = [[]] * N
    ans = 0

    for i in range(N):  # 入力
        A = int(input())
        A_lst[i] = A
        xy_lst[i] = [[]] * A

        for j in range(A):
            x, y = map(int, input().split())
            xy_lst[i][j] = [x, y]  # 3次元配列 i人目のj番目の証言の[x,y]

    for i in range(2 ** N):  # ビット全探索
        honest_unkind = [0] * N
        flag = True

        for j in range(N):  # 1つ状態を決める
            if (i >> j) & 1 == 1:
                honest_unkind[j] = 1  # 1:honest, 0:unkind

        for j in range(N):  # 1人ずつ証言を検証する
            if flag == False:
                break

            for k in range(A_lst[j]):  # 各人の証言がk個
                if honest_unkind[j] == 1:  # j番目の人がhonestだったら
                    if xy_lst[j][k][1] == 0 and honest_unkind[xy_lst[j][k][0] - 1] == 1:
                        flag = False  # 矛盾したら終了
                        break
                    if xy_lst[j][k][1] == 1 and honest_unkind[xy_lst[j][k][0] - 1] == 0:
                        flag = False
                        break
                # if honest_unkind[j] == 0:  # j番目の人がunkindだったら
                #     if xy_lst[j][k][1] == 0 and honest_unkind[xy_lst[j][k][0] - 1] == 0:
                #         flag = False
                #         break
                #     if xy_lst[j][k][1] == 1 and honest_unkind[xy_lst[j][k][0] - 1] == 1:
                #         flag = False
                #         break

        if flag == True:  # 全員の証言が矛盾しなかった場合
            cnt = sum(honest_unkind)
            if cnt > ans:
                ans = cnt

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
ev=[]
for i in range(n):
    a=int(input())
    ev.append([list(map(int,input().split())) for _ in range(a)])
ans=0
for i in range(2**n):
    bit=(bin(i)[2:].zfill(n))
    flag=1
    for j in range(n):
        if bit[j]=="0":
            continue
        for e in ev[j]:
            if int(bit[e[0]-1])!=e[1]:
                flag=0
    if flag:
        ans=max(ans,bit.count("1"))
print(ans)

Submission status: Accepted

Solution code:
def popcount(x):
    x = (x & 0x5555555555555555) + (x >> 1  & 0x5555555555555555)
    x = (x & 0x3333333333333333) + (x >> 2  & 0x3333333333333333)
    x = (x & 0x0f0f0f0f0f0f0f0f) + (x >> 4  & 0x0f0f0f0f0f0f0f0f)
    x = (x & 0x00ff00ff00ff00ff) + (x >> 8  & 0x00ff00ff00ff00ff)
    x = (x & 0x0000ffff0000ffff) + (x >> 16 & 0x0000ffff0000ffff)
    x = (x & 0x00000000ffffffff) + (x >> 32 & 0x00000000ffffffff)
    return x
n = int(input())

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

ans = 0
for bits in range(1, 1<<n):
    possible = True
    for i in range(n):
        if not bits >> i & 1:
            continue
        for x, y in testimonies[i]:
            if bits >> x & 1 != y: 
                possible = False
                break
        if not possible:
            break
    if possible:
        ans = max(ans, popcount(bits))
print(ans)

Submission status: Accepted

Solution code:
import sys;      from decimal import Decimal
import math;     from itertools import combinations, product
import bisect;   from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 6 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

def Main():
    n = read_int()
    testimony = [[] for _ in range(n)]
    ans = 0

    for i in range(n):
        for _ in range(read_int()):
            x, y = read_ints()
            testimony[i].append((x-1, y))
    
    for bit in range(1 << n):
        flag = True
        for i in range(n):
            if (bit >> i) & 1:
                for x, y in testimony[i]:
                    if (bit >> x) & 1 != y:
                        flag = False
                        break
                else:
                    continue
                break
        
        if flag:
            ans = max(ans, bin(bit).count('1'))
    
    print(ans)


if __name__ ==  '__main__':
    Main()

Submission status: Accepted

Solution code:
n = int(input())
A = []
X = []

for _ in range(n):
    a = int(input())
    A.append(a)
    Y = []
    for _ in range(a):
        x, y = map(int, input().split())
        Y.append(x)
        Y.append(y)
    X.append(Y)

# print("X",X)
ans = 0

for i in range(2**n):
    flg = True
    honest = [0]*n
    count = 0
    for j in range(n):
        if ((i >> j) & 1):
            honest[j] = 1
    # print("honest",honest)
    for k in range(n):
        for l in range(0,len(X[k]),2):
            # print(honest[X[k][l]-1], X[k][l+1])
            if honest[X[k][l]-1] != X[k][l+1] and honest[k] == 1:
                # print('hi')
                flg = False

    if flg:
        count = sum(honest)
        # print("count", count)
        ans = max(ans, count)



print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2 ** N):
    for (j,x,y) in A:
        if i & 1 << j:
            if y == 1:
                if not i & (1 << x):
                    break
            else:
                if i & (1 << x):
                    break
    else:
        ans = max(ans, sum([1 for x in bin(i) if x == '1']))
print(ans)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
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
info = [[] for _ in range(n)]
for i in range(n):
    a = I()
    for _ in range(a):
        x, y = LI()
        info[i].append((x-1, y))

for i in range(1, 1 << n):
    ret = 0
    for j in range(n):
        if i >> j & 1:
            ret += 1
            for x, y in info[j]:
                if y == 0 and i >> x & 1:
                    break
                elif y == 1 and not i >> x & 1: 
                    break
            else:
                continue
            break
    else:
        ans = max(ans, ret)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
L = []
for _ in range(N):
  L.append([list(map(int, input().split())) for _ in range(int(input()))])
for ls in L:
  for l in ls:
    l[0] -= 1
M = 0
for i in range(1<<N):
  A, Normal = [], True
  for j in range(N):
    if (i>>j)&1:
      A.append(j)
  for a in A:
    for l in L[a]:
      if l[0] in A and l[1]==0:
        Normal = False
      if l[1]==1 and l[0] not in A:
        Normal = False
  if Normal:
    M = max(M, len(A))
print(M)

Submission status: Accepted

Solution code:
N=int(input())
D=[{} for _ in range(N+1)]

for i in range(1,N+1):
    A=int(input())
    for k in range(A):
        p,x=map(int,input().split())
        D[i][p]=x

Max=0
for x in range(2**N):
    y=x

    B=["*"]*(N+1)
    for i in range(N):
        B[i+1]=y%2
        y>>=1

    Flag=True
    for i in range(1,N+1):
        if B[i]==1:
            for k in D[i]:
                Flag&=(B[k]==D[i][k])

    if Flag:
        Max=max(Max,B.count(1))

print(Max)

Submission status: Accepted

Solution code:
n = int(input())
a, xy = [], []
for _ in range(n):
    a_t = int(input())
    xy_t = [list(map(int, input().split())) for _ in range(a_t)]
    a.append(a_t)
    xy.append(xy_t)

ans = 0
for i in range(2**n):
    flag = True
    for j in range(n):
        if (i >> j) & 1:
            for k in xy[j]:
                if (i >> (k[0]-1)) & 1 != k[1]:
                    flag = False
                    break
    if flag:
        ans = max(ans, bin(i).count('1'))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a, xy = [], []
for _ in range(n):
    a_t = int(input())
    xy_t = [list(map(int, input().split())) for _ in range(a_t)]
    a.append(a_t)
    xy.append(xy_t)

ans = 0
for i in range(2**n):
    flag = True
    for j in range(n):
        if (i >> j) & 1:
            for k in xy[j]:
                if (i >> (k[0]-1)) & 1 != k[1]:
                    flag = False
    if flag:
        ans = max(ans, bin(i).count('1'))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
d = {}
for i in range(N):
    d[i] = {}

for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = [int(i) for i in input().split()]
        d[i][x-1] = y
# 整合性はどうやって取れるか？
# 人iが正直者として整合性がなりたち、その人数がmax_countを更新するなら増やす
max_i = 0
for i in range(2 ** N):
    tmp = [-1 for i in range(N)]
    counter = 0
    flag = 0
    for j in range(N):
        if ((i >> j) & 1):
            counter += 1
            tmp[j] = 1
        else:
            tmp[j] = 0
    for j in range(N):
        if ((i >> j) & 1):
            for key in d[j].keys():
                if tmp[key] != d[j][key]:
                    flag = 1

        if flag == 1:
            break
    if flag == 0 and max_i < counter:
        max_i = counter
print(max_i)

Submission status: Accepted

Solution code:
N = int(input())
 
testimony = [[] for _ in range(N)]
 
for i in range(N):
    num = int(input())
    for j in range(num):
        person, state = map(int, input().split())
        testimony[i].append([person-1, state])
        
honest = 0
for i in range(2**N):
    flag = 0
    for j in range(N):
        if (i>>j)&1 == 1: # j番目は正直と仮定
            for x,y in testimony[j]:
                if (i>>x)&1 != y: # j番目は正直だが矛盾を発見
                    flag = 1
                    break
    if flag == 0:  # 矛盾がある場合はflag == 1になる
        honest = max(honest, bin(i)[2:].count('1'))  # 1の数をカウントし最大となるものを選択
print(honest)

Submission status: Accepted

Solution code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
N = int(input())
 
testimony = [[] for _ in range(N)]
 
for i in range(N):
    num = int(input())
    for j in range(num):
        person, state = map(int, input().split())
        testimony[i].append([person-1, state])
        
honest = 0
for i in range(1, 2**N):
    flag = 0
    for j in range(N):
        if (i>>j)&1 == 1: # j番目は正直と仮定
            for x,y in testimony[j]:
                if (i>>x)&1 != y: # j番目は正直だが矛盾を発見
                    flag = 1
                    break
    if flag == 0:  # 矛盾がある場合はflag == 1になる
        honest = max(honest, bin(i)[2:].count('1'))  # 1の数をカウントし最大となるものを選択
print(honest)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

N = int(input())
info = []
for i in range(N):
    A = int(input())
    for _ in range(A):
        x,y = map(int,input().split())
        info.append((i,x-1,y))
        
A = np.array(list(itertools.product([0,1],repeat=N)),np.bool)
for i,x,y in info:
    bl = (~A[:,i]) | (A[:,x] == bool(y))
    A = A[bl]
 
answer = A.sum(axis = 1).max()
print(answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

# あるbit列に対するコストの計算
def count(zerone):
    one = 0
    cnt = 0
    for i in range(N):
        flag = True
        if zerone[i] == 1:
            one += 1
            for j in range(len(A[i])):
                if A[i][j][1] != zerone[A[i][j][0]-1]:
                    flag = False
                    break
        if flag:
            cnt += 1
    if cnt == N:
        return one
    else:
        return 0

# bit列の列挙
def dfs(bits):
    if len(bits) == N:
        return count(bits)
    res = 0
    for i in range(2):
        bits.append(i)
        res = max(res, dfs(bits))
        bits.pop()
    return res

# main
N = int(input())
A = [[] for _ in range(N)]
for i in range(N):
    a = int(input())
    for _ in range(a):
        A[i].append([int(x) for x in input().split()])

ans = dfs([])
print(ans)