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())
X=[[] for _ in range(N)]

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

ans=[]
for i in range(2**N):
  judge=True
  count=0
  total=format(i,"b").count("1")
  for j in range(N):
    if (i>>j)&1==1:
      for k in X[j]:
        a,b=k[0],k[1]
        if (i>>a)&1==1 and b==0:
          judge=False
        elif (i>>a)&1!=1 and b==1:
          judge=False
  else:
    if judge:
      ans.append(total)

print(max(ans))

Submission status: Accepted

Solution code:
n = int(input())

# 証言の内容をリストに保存
lst = []
for _ in range(n):
  a = int(input())
  lst.append([[int(i) for i in input().split()] for _ in range(a)])

m = 0
for i in range(2**n):
  flag = True
  for j in range(n):
    if i >> j & 1: # 2進数で見た場合に、101の場合、j=0,2が条件を満たす(101>>0=1,101>>1=10,101>>2=1
      for x,y in lst[j]:
        if (i >> (x-1)&1) != y: # 証言との整合確認 101>>1&1=0 yの結果と矛盾
          flag = False
          break
  '''
  011の場合、j=0,1の時、成立する
  j=0: [x,y]=[2,1], 011>>1&1=1, y=1, OK
  j=1: [x,y]=[1,1], 011>>0&1=1, y=1, OK
  '''
  if flag:
    m = max(m, sum(map(int, bin(i)[2:])))
print(m)

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 = map(int,input().split())
            XY.append((x-1,y))

        A.append(XY)
    # print(A)

    MAX = 0
    for i in range(2**N):
        # print(i)
        flg = 1
        for j in range(N):
            if (i >>j) & 1:
                # print('b')
                for ch in A[j]:
                    # print(i,ch[0],bin(i >> ch[0]),ch[1],(i >> ch[0])^ ch[1])
                    if ((i >> ch[0])^ ch[1])%2 == 1:
                        # print('a',ch[0])
                        flg = 0

        if flg == 1:
            t = bin(i).count('1')
            MAX = max(t,MAX)
        
    print(MAX)



main()

Submission status: Accepted

Solution code:
N=int(input())

evi=[[] for _ in range(N)]

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

ans=0

for i in range(2**N):
    cnt=0
    f=True
    for j in range(N):
        if (i>>j)&1:
            cnt+=1
            for x,y in evi[j]:
                if (i>>x)&1 and y==0:
                    f=False
                    break
                elif (not (i>>x)&1) and y==1:
                    f=False
                    break
        if not f:
            break
    if f:
        ans=max(ans,cnt)

print(ans)

Submission status: Accepted

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

ans=0
for i in range(2**n):
  list=[[] for j in range(n)]
  honest=[]
  for k in range(n):
    if (i>>k)&1:
      honest.append(k)
      for x,y in xy[k]:
        x-=1
        list[x].append(y)

  check=1
  for m in range(n):
    t_l=list[m]
    if t_l:
      if 0 in t_l and 1 in t_l:
        check=0
      elif 1 in t_l and m not in honest:
        check=0
      elif 0 in t_l and m in honest:
        check=0

  if check==1:
    ans=max(ans,len(honest))

print(ans)

Submission status: Accepted

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

ans=0
for i in range(2**n):
  list=[[] for j in range(n)]
  honest=[]
  for k in range(n):
    if (i>>k)&1:
      honest.append(k)
      for x,y in xy[k]:
        x-=1
        list[x].append(y)

  check=1
  for m in range(n):
    t_l=list[m]
    if t_l:
      if 0 in t_l and 1 in t_l:
        check=0
      elif 1 in t_l and m not in honest:
        check=0
      elif 0 in t_l and m in honest:
        check=0

  if check==1:
    ans=max(ans,len(honest))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

a = [0] * n
sl = []

for i in range(n):
  a = int(input())
  s = []
  for j in range(a):
    x, y = map(int, input().split())
    s.append([x, y])
  sl.append(s)
ans = 0

# bit 全探索
# 1 = 正直者、0 = 不親切な人
for i in range(1 << n):
  #print('pattern', bin(i))
  all_ok = True
  for j in range(n):
    # 人j が正直者かどうか
    #print('j : {}'.format(j))
    if i & (1 << j):
      # print(j)
      # 正直者であれば証言に矛盾があってはいけない
      s = sl[j]
      for k in range(len(s)):
        target =  s[k][0]
        kind = s[k][1]
        # print('target {} : kind {}'.format(target, kind))
        #print(target, kind, i & (1 << (target-1)), bool(i & (1 << (target-1))), bool(kind))
        rk = 1 if (i & (1 << (target-1))) > 0 else 0
        if rk != kind :
          #print('証言NG')
          # 証言がNG
          all_ok = False
          break
    if not all_ok:
      break
  else:
    # すべての正直者に矛盾がないパターン
    #print('ok', bin(i))
    ans = max(ans, bin(i).count('1'))
    
#print(sl)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
xy = []
for i in range(N):
    t = []
    A = int(input())
    for l in range(A):
        t.append(list(map(int,input().split())))
    xy.append(t)
ans = 0
for i in range(2**N):
    p = []
    for l in range(N):
        if ((i >> l) & 1) == 1:
            p.append(1)
        else:
            p.append(0)
    c = 0
    if sum(p) > ans:
        for l in range(N):
            if p[l] != 0:
                for j in xy[l]:
                    if p[j[0] - 1] != j[1]:
                        c = 1
        if c == 0 and p != [1,1,1]:
            ans = sum(p)
print(ans)

Submission status: Accepted

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

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

    c_max = 0
    for i in range(2 ** n):
        cnt = 0
        for j in range(n):
            if (i >> j) & 1:
                cnt += 1
                for xy in list_[j]:
                    x, y = xy
                    if ((i >> x) ^ y) & 1:
                        break
                else:
                    continue
                break
        else:
            if cnt > c_max:
                c_max = cnt
            continue

    print(c_max)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def is_honest(i, j):
    return (i >> j) % 2 == 1

def honest_cnt(i):
    ans = 0
    for j in range(n):
        ans += is_honest(i, j)
    return ans 

for i in range(1 << n):
    ok = True
    for j in range(n):
        if not is_honest(i, j):continue
        for (x, y) in shogens[j]:
            if y == 0 and is_honest(i, x): ok = False
            if y == 1 and not is_honest(i, x): ok = False
    if ok:
        ans = max(ans, honest_cnt(i))

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
test=[]
for i in range(n):
  a=int(input())
  testament=[list(map(int,input().split())) for i in range(a)]
  test.append(testament)
ans=0
for i in range(2**n):
  HorL=[0 for j in range(n)]
  success=True
  for j in range(n):
    if i&1==1:
      HorL[j]=1
    i>>=1
  for j in range(n):
    if HorL[j]==1:
      for x,y in test[j]:
        if y==HorL[x-1]:
          pass
        else:
          success=False
          break
    else:
      continue
  if success and ans < sum(HorL):
    ans=sum(HorL)
print(ans)

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 147
# C - HonestOrUnkind2
# https://atcoder.jp/contests/abc147/tasks/abc147_c
import sys
input = sys.stdin.readline
N = int(input())
X = []
for _ in [0]*N:
    A = int(input())
    x = [tuple(map(int, input().split())) for _ in [0]*A]
    X.append(x)

ans = 0
for bit in range(1 << N):
    cnt = 0
    for i in range(N):
        if bit >> i & 1:
            cnt += 1
            for x, y in X[i]:
                if y == 1 and bit >> (x-1) & 1 == 0:
                    break
                if y == 0 and bit >> (x-1) & 1 == 1:
                    break
            else:
                continue
            break
    else:
        ans = max(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
import itertools
N = int(input())

syogens = []

for _ in range(N):
    a = int(input())
    syogens.append([list(map(int, input().split())) for _ in range(a)])


ans = 0
for flags in itertools.product([False, True], repeat=N):
    for f, xys in zip(flags, syogens):
        if not f:
            continue
        else:
            for x, y in xys:
                if y == 1 and not flags[x - 1]:
                    break
                elif y == 0 and flags[x - 1]:
                    break
            else:
                continue
            break
    else:
        ans = max(ans, sum(flags))

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N = int(input())
G = {i:[] for i in range(1,N+1)}
for i in range(1,N+1):
    K = int(input())
    for j in range(K):
        G[i].append(list(map(int,input().split())))
cmax = 0
for z in product((0,1),repeat=N):
    flag = 0
    for i in range(N):
        if z[i]==1:
            ind = i+1
            for [x,y] in G[ind]:
                if z[x-1]==y:continue
                else:
                    flag=1
                    break
            if flag==1:
                break
    if flag==0:
        cmax = max(cmax,sum(z))
print(cmax)

Submission status: Accepted

Solution code:
n = int(input())
testimony = []

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

ans = 0
for p in range(2 ** n):
    cnt = 0
    is_unmatch = False
    for i in range(n):
        if p >> i & 1:
            cnt += 1
            for x, y in testimony[i]:
                if p >> x & 1 != y:
                    is_unmatch = True
                    break
        if is_unmatch:
            cnt = 0
            break
    ans = max(ans, cnt)

print(ans)

Submission status: Accepted

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

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

ans=0
for i in range(1<<n):
  cnt=bin(i).count("1")
  ok=True
  for j in range(n):
    if ok==False:break
    if i&(1<<j):
      for x,y in xy[j]:
        if y==1 and i&(1<<x-1)==0:
          ok=False
        if y==0 and i&(1<<x-1):
          ok=False
  if ok:
    ans=max(cnt,ans)
print(ans)

Submission status: Accepted

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

for p in range(n):
    num = int(input())
    for i in range(num):
        array = list(map(int, input().split()))
        array[0] -= 1
        person[p].append(array)



honest = 0
for i in range(2**n):
    bi_num = format(i, 'b').zfill(n)
    q = 0
    for k in bi_num:
        if k == '1':
            q += 1
    flg = False
    for man in range(n):
        if bi_num[man] == '0':
            continue
        else:
            for hito, t in person[man]:
                if t == 0:
                    if bi_num[hito] == '0':
                        continue
                    else:
                        flg = True
                        break
                elif t == 1:
                    if bi_num[hito] == '1':
                        continue
                    else:
                        flg = True
                        break
    if flg is True:
        continue
    else:
        if honest < q:
            honest = q

print(honest)

Submission status: Accepted

Solution code:
N=int(input())
ALL=[]
for i in range(N):
  A=int(input())
  XY=[]
  for k in range(A):
    x,y=map(int,input().split())
    XY+=[[x,y]]
  ALL+=[XY]
ans=0  
for i in range(2**N):
  people=[-1]*N
  anssub=0
  for k in range(N):
    if ((i >> k) & 1):
      if people[k]==0 or people[k]==-2:
        people[k]=-2        
      else:
        people[k]=1
      anssub+=1
      for t in ALL[k]:
        if people[t[0]-1]!=t[1] and people[t[0]-1]!=-1:
          people[t[0]-1]=-2
        else:
          people[t[0]-1]=t[1]
    else:
      if people[k]==1 or people[k]==-2:
        people[k]=-2
      else:
        people[k]=0  
  if not -2 in people:
    ans=max(ans,anssub)
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    s = [[] for _ in range(n)]
    for i in range(n):
        a = int(input())
        for j in range(a):
            x, y = map(int, input().split())
            s[i].append((x, y))
    ans = 0
    for i in range(2**n):
        ho = [0]*n
        OK = True
        for j in range(n):
            ho[j] = (i>>j)&1
        for j in range(n):
            if ho[j] == 0:
                continue
            else:
                for k in range(len(s[j])):
                    if ho[s[j][k][0]-1] == s[j][k][1]:
                        continue
                    else:
                        OK = False
        if OK:
            ans = max(ans, sum(ho))
    print(ans)


resolve()

Submission status: Accepted

Solution code:
n = int(input())
a, xy = [], []
for i in range(n):
    a_ = int(input())
    xy_ = [list(map(int, input().split())) for i in range(a_)]
    a.append(a_)
    xy.append(xy_)
ans = 0
for bit in range(1 << n):
    OK = True
    cnt = 0
    for i in range(n):
        if (bit >> i) & 1:
            cnt += 1
            for j, k in xy[i]:
                if not (bit >> (j - 1) & 1) == k:
                    OK = False
                    break
    if OK:
        ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import product

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    XY = [[] for _ in range(n)]
    for i in range(n):
        a = int(input())
        for _ in range(a):
            x, y = map(int, input().split())
            XY[i].append([x, y])

    res = 0
    for pattern in product([0, 1], repeat=n):
        for idx, p in enumerate(pattern):
            if p == 1:
                for x, y in XY[idx]:
                    if pattern[x - 1] != y:
                        break
                else:
                    continue
                break
        else:
            cnt = sum(pattern)
            res = max(res, cnt)

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

def calc(state):
    ret = 0
    for i, S in enumerate(A):
        if (state & (1 << i)) == 0:
            continue
        ret += 1
        for x, y in S:
            if (state & (1 << x)) != (y << x):
                return 0
    return ret

ans = 0
for state in range(1 << N):
    ans = max(ans, calc(state))
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
g = [[] for _ in range(n)]
for i in range(n):
    a = inp()
    for j in range(a):
        x,y = inpl()
        g[i].append([x-1,y])
res = 0
for fl in itertools.product(range(2), repeat=n):
    ch = [i for i in fl]
    ok = True
    for i,f in enumerate(fl):
        if not f: continue
        for x,y in g[i]:
            if ch[x] != y:
                ok = False
    if ok: res = max(res, sum(fl))
print(res)

Submission status: Accepted

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

N = int(input())

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

ans = 0
for i in range(2 ** N): #1の時正直者
    tmp = 0
    flag = True
    for j in range(N):
        if (i >> j) & 1:
            tmp += 1
            for x, y in lst[j]:
                if y == 0:
                    if (i >> (x - 1)) & 1:
                        pass
                    else:
                        continue
                if y == 1:
                    if (i >> (x - 1)) & 1:
                        continue
                
                flag = False
                break
        if not flag:
            break
    if flag:
        ans = max(ans, tmp)
                    
print (ans)

Submission status: Accepted

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

ans = 0
for b in range(1<<N):
    for i in range(N):
        if b&(1<<i):
            for x,y in A[i]:
                if y:
                    if b&(1<<x)==0:
                        break
                else:
                    if b&(1<<x):
                        break
            else:
                continue
            break
    else:
        t = bin(b).count('1')
        ans = max(ans, t)
print(ans)

Submission status: Accepted

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

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

ans = 0
for pair in product(range(2), repeat=N):
    isOK = True
    for i, p in enumerate(pair):
        if not p:
            continue
        for x, y in mention[i]:
            if pair[x - 1] != y:
                isOK = False
    if isOK:
        ans = max(ans, sum(pair))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
XY = []
ans = 0

for i in range(n):
    z = []
    
    for j in range(int(input())):
        x,y = map(int,input().split())
        z.append([x,y])
        
    XY.append(z)
        
for i in range(2**n):
    honest = 0
    mujunn = 0
    
    for j in range(n):
        if (i>>j) & 1:
            honest += 1
            
            for k in XY[j]:
                x = k[0] - 1
                y = k[1]
                
                if (i>>x)&1 != y:
                    mujunn = 1
                    break
                    
        if mujunn == 1:
            break
                
    if mujunn == 0:
        ans = max(ans,honest)
        
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
XY = []
ans = 0

for i in range(n):
    z = []
    
    for j in range(int(input())):
        x,y = map(int,input().split())
        z.append([x,y])
        
    XY.append(z)
        
for i in range(2**n):
    honest = 0
    mujunn = 0
    
    for j in range(n):
        if (i>>j) & 1:
            honest += 1
            
            for k in XY[j]:
                x = k[0] - 1
                y = k[1]
                
                if (i>>x)&1 != y:
                    mujunn = 1
                
    if mujunn == 0:
        ans = max(ans,honest)
        
print(ans)

Submission status: Accepted

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

ans = 0
for bit in range(1 << N):
    truth = set()
    false = set()
    ppl_truth = set()
    ppl_false = set()
    for i in range(N):
        if (bit >> i) & 1:
            ppl_truth.add(i)
            truth |= A[i][1]
            false |= A[i][0]
        else:
            ppl_false.add(i)
    if ppl_truth >= truth and ppl_false >= false:
        ans = max(ans, len(ppl_truth))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
tests = [[] for _ in range(N)]
ans = 0

for i in range(N):
    for _ in range(int(input())):
        x, y = map(int, input().split())
        tests[i].append((x-1, y))
        
for i in range(1<<N):
    FLG = True
    count = bin(i).count("1")
    for j in range(N):
        if i>>j & 1:
            for test in tests[j]:
                if int(bin(i>>test[0])[-1]) != test[1]:
                    FLG = False
                    break
            if not FLG:
                break
    if FLG:
        ans = max(ans, count)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

# 証言者ごとに整理する
testimony_list = []
for i in range(N):
    array = [-1] * N
    testimony_list.append(array)
for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split())
        # iさんの、xさんへの証言
        testimony_list[i][x - 1] = y

max_count = 0
for i in range(2 ** N):
    failed = False
    for j in range(N):
        if not (i >> j & 1):
            continue
        array = testimony_list[j]
        for k in range(N):
            if array[k] == -1:
                continue
            if (i >> k & 1) != array[k]:  # 正直者に対して不親切 or 不親切に対して正直者と証言
                failed = True
                break
    if not failed:
        # 「0b010110」の「0b」を除外して1の数をカウント
        max_count = max(max_count, bin(i)[2:].count("1"))
print(max_count)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def is_nth_bit_set(x, n):
    if x & (1 << n):
        return True
    else:
        return False


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

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

    total = 2 ** N
    ans = 0
    for pattern in range(total):
        flag = True
        tmp = 0
        for i in range(N):
            if is_nth_bit_set(pattern, i):
                tmp += 1
                for x, y in comments[i]:
                    if is_nth_bit_set(pattern, x) == bool(y):
                        continue
                    else:
                        flag = False
                        break
            else:
                continue

            if not flag:
                break

        if flag:
            if tmp > ans:
                ans = tmp

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import product

N = int(input())
answers = {}
for i in range(N):
    A = int(input())
    answers[i + 1] = [tuple(map(int, input().split(' '))) for _ in range(A)]

max_people = 0

for bits in product((False, True), repeat=N):
    for index, bit in enumerate(bits, start=1):
        if not bit:
            continue

        for people, true_or_false in answers[index]:
            if bool(bits[people - 1]) != bool(true_or_false):
                break
        else:
            continue
        break
    else:
        max_people = max(max_people, bits.count(True))

print(max_people)

Submission status: Accepted

Solution code:
n = int(input())
l = []
A = []
for i in range(n):
    a = int(input())
    A += [a]
    l_1 = []
    for j in range(a):
        l_1 += [list(map(int, input().split()))]
    l += [l_1]

ans = 0

for i in range(1 << n):
    honest = []
    liar = []
    for j in range(n):
        if ((i >> j) & 1):
            if j + 1 in liar:
                break
            elif j + 1 not in honest:
                honest += [j + 1]
            sugg = l[j]

            for k in sugg:
                if k[1] == 1:
                    if k[0] in liar:
                        break
                    elif k[0] not in honest:
                        honest += [k[0]]
                else:
                    if k[0] in honest:
                        break
                    elif k[0] not in liar:
                        liar += [k[0]]
            else:
                continue
            break

        else:
            if j + 1 in honest:
                break
            elif j + 1 not in liar:
                liar += [j + 1]
    else:
        if ans < len(honest):
            ans = len(honest)

print(ans)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N = I()
xy = [[LI() for _ in range(I())] for _ in range(N)]
ans = 0
for i in range(2**N):
    bit = [i>>j&1 for j in range(N)]
    if ans >= sum(bit):
        continue
    for j,a in enumerate(xy):
        if bit[j]==1:
            for x,y in a:
                if bit[x-1]!=y:
                    break
            else:
                continue
            break
    else:
        ans = max(ans,sum(bit))
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    A_arr = []
    x_y_arr = []
    line = 1
    for i in range(N):
        _ = int(_in[line])  # type:int
        A_arr.append(_)
        tmp = {}
        for j in range(_):
            x,y = list(map(int,_in[line+j+1].split(' ')))  # type:list(int)
            tmp[x] = y
        x_y_arr.append(tmp)
        line += _+1
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = 0
    for bit in range(1<<N):
        # bit = 0: Unkind, 1: Honest
        for i in range(N):
            if bit&(1<<i): # Honest
                for k,v in x_y_arr[i].items():
                    if bit&(1<<(k-1))==0 and v==1:
                        break
                    elif bit&(1<<(k-1))>0 and v==0:
                        break
                else:
                    continue
                break
        else:
            _ = bin(bit).count('1')
            cnt = max(cnt,_)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

N = getN()
convict = [[] for _ in range(N)]
for i in range(N):
    a = getN()
    for j in range(a):
        x, y = getNM()
        convict[i].append([x - 1, y])
ans = 0
# 状態を生成
for bit in range(1 << N):
    flag = True
    # 人iの証言について
    for i in range(N):
        # 正直者のフラグが立っていれば
        if bit & (1 << i):
            for j in convict[i]:
                # もし正直者が行ったことに間違いがあれば
                if j[1] == 0 and bit & (1 << j[0]) > 0:
                    flag = False
                if j[1] == 1 and bit & (1 << j[0]) == 0:
                    flag = False
    if flag:
        index = str(bin(bit)).count('1')
        ans = max(ans, index)
print(ans)

Submission status: Accepted

Solution code:
import math
import copy
from queue import Queue
import heapq
import numpy as np

MOD = 5000000007

#n = int(input())
#s = int(input())
#a, b, c, x, y = [int(i) for i in input().split()]
#table = [[int(i)  for i in input().split()] for j in range(m)]
#table = [list(input()) for n in range(r)] #table[h][w]
#p = [int(i) for i in input().split()]
#s = [int(i) for i in range(n)]
#p = [int(input()) for i in range(m)]
#s = input()

#list = list(s)
#a = [0 for _ in range(n+1)]
#dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

n = int(input())
word_list = [[] for i in range(n)]

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

ans = 0

for i in range(2**n):
    peoples = []
    flag = 1
    for j in range(n):
        if(i >> j & 1):
            peoples.append(1)
        else:
            peoples.append(0)

    for k in range(n):
        if peoples[k] == 1:
            words = word_list[k]
            for word in words:
                if peoples[word[0]] != word[1]:
                    flag = 0
                    break

    if flag:
        ans = max(ans,sum(peoples))

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2 ** n):
    flg = True
    for j in range(n):
        for k in range(A[j]):
            if (i >> j) & 1:
                if ((i >> (X[j][k] - 1)) & 1) != Y[j][k]:
                    flg = False
                    break

    if flg == True:
        ans = max(ans, sum([int(b) for b in bin(i)[2:]]))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
Testimony = []
for a_ in range(N):
    A_ = int(input())
    A = [tuple(map(int, input().split())) for _ in range(A_)]
    Testimony.append(A)

ans = 0


for i in range(1, 2**N):
    Honesty = [-1] * N
    flag = True
    for j in range(N):
        if not flag:
            break
        if (i >> j) & 1 == 1:
            if Honesty[j] == 0:
                flag = False
                break
            Honesty[j] = 1
            for jx, jy in Testimony[j]:
                jx -= 1
                if Honesty[jx] < 0:
                    Honesty[jx] = jy
                elif Honesty[jx] != jy:
                    flag = False
                    break
        else:
            if Honesty[j] == 1:
                flag = False
                break
            else:
                Honesty[j] = 0

    if flag:
        ans = max(ans, str(bin(i)).count('1'))

print(ans)