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: Wrong Answer

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: Wrong Answer

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  
      for t in ALL[k]:
        if t[1]==0:
          if people[t[0]-1]!=1 and people[t[0]-1]!=-1:
            people[t[0]-1]=-2
          else:
            people[t[0]-1]=1
        else:
          if people[t[0]-1]!=0 and people[t[0]-1]!=-1:
            people[t[0]-1]=-2
          else:
            people[t[0]-1]=0
  if not -2 in people:
    ans=max(ans,anssub)
print(ans)

Submission status: Wrong Answer

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  
      for t in ALL[k]:
        if t[1]==0:
          if people[t[0]-1]!=1 and people[t[0]-1]!=-1:
            people[t[0]-1]=-2
          else:
            people[t[0]-1]=1
        else:
          if people[t[0]-1]!=0 and people[t[0]-1]!=-1:
            people[t[0]-1]=-2
          else:
            people[t[0]-1]=0
  if not -2 in people:
    ans=max(ans,anssub)
print(ans)

Submission status: Wrong Answer

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:
        people[k]=-2        
      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:
        people[k]=-2
      people[k]=0  
      for t in ALL[k]:
        if t[1]==0:
          if people[t[0]-1]!=1 and people[t[0]-1]!=-1:
            people[t[0]-1]=-2
          else:
            people[t[0]-1]=1
        else:
          if people[t[0]-1]!=0 and people[t[0]-1]!=-1:
            people[t[0]-1]=-2
          else:
            people[t[0]-1]=0
  if not -2 in people:
    ans=max(ans,anssub)
print(ans)

Submission status: Wrong Answer

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]==1:
        people[k]=-2        
      people[k]=0
      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]==0:
        people[k]=-2
      people[k]=1  
      for t in ALL[k]:
        if t[1]==0:
          if people[t[0]-1]!=1 and people[t[0]-1]!=-1:
            people[t[0]-1]=-2
          else:
            people[t[0]-1]=1
        else:
          if people[t[0]-1]!=0 and people[t[0]-1]!=-1:
            people[t[0]-1]=-2
          else:
            people[t[0]-1]=0
  if not -2 in people:
    ans=max(ans,anssub)
print(ans)

Submission status: Wrong Answer

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]==1:
        people[k]=-2        
      people[k]=0
      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]==0:
        people[k]=-2
      people[k]=1  
      for t in ALL[k]:
        if t[1]==0:
          if people[t[0]-1]!=1 and people[t[0]-1]!=-1:
            people[t[0]-1]=-2
          else:
            people[t[0]-1]=1
        else:
          if people[t[0]-1]!=0 and people[t[0]-1]!=-1:
            people[t[0]-1]=-2
          else:
            people[t[0]-1]=0
  if not -2 in people:
    ans=max(ans,anssub)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N=int(input())
A=[]
B=[]
for i in range(N):
    a=int(input())
    A.append(a)
    b=[list(map(int,input().split())) for i in range(a)]
    B.append(b)
result=[]
D1=[]
for i in range(2**N):
    listA={}
    D2=[0 for i in range(N)]
    for j in range(N):
        if ((i>>j)&1):
            listA[j+1]=B[j]
            D2[j]=1
    result.append(listA)
    D1.append(D2)
ans=0
for _,d in enumerate(result):
    C=[-1 for i in range(N)]
    for i,value in d.items(): 
        for j in value:
            C[j[0]-1]=j[1]
#     print(D1[_],C)
    if not any(((C[j]==0 and D1[_][j]==1) or (C[j]==1 and D1[_][j]==0))for j in range(N)):
            ans=max(ans,Counter(D1[_])[1])
print(ans)

Submission status: Wrong Answer

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 honest:
                        continue
                    elif k[0] in liar:
                        break
                    else:
                        honest += [k[0]]
                else:
                    if k[0] in liar:
                        continue
                    elif k[0] in honest:
                        break
                    else:
                        honest += [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: Wrong Answer

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)]
    evidence = []
    for j,a in enumerate(xy):
        for x,y in a:
            if bit[j]==1:
                evidence.append([x,y])
            else:
                evidence.append([x,y^1])
    status = {}
    for ex,ey in evidence:
        if not ex in status:
            status[ex] = ey
        else:
            if status[ex]!=ey:
                break
    else:
        ans = max(ans,min(sum(bit),sum(status.values())))
print(ans)

Submission status: Wrong Answer

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
    honest = [0] * n
    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

                honest[j] = 1
    if flg == True:
        ans = max(ans, sum(honest))

print(ans)

Submission status: Wrong Answer

Solution code:
def check(T):
    is_possible = True
    for i in range(N):
        tt = []
        for j in range(len(tl)):
            tt.append(T[j][i])
        if tt.count(1) > 0 and tt.count(0) > 0:
            is_possible = False
    return is_possible

N = int(input())
T = [None] * N

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

ans = 0
mask = 0
while (mask < (1 << N)):
    ans_t = 0
    tl = [[y for y in x] for x in T]

    for i in range(N):
        if not (mask & (1 <<i)):
            for j in range(N):
                if tl[i][j] == None:
                    continue
                else:
                    tl[i][j] = not tl[i][j]
            ans_t += 1

    if check(tl):
        ans = max(ans, N-ans_t)
    mask += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=[]
xy=[]
ans=0
for i in range(n):
  ai=int(input())
  A.append(ai)
  small_xy=[]
  for j in range(ai):
    small_xy.append(list(map(int,input().split())))
  xy.append(small_xy)

for i in range(1,2 ** n):#全bit探索
  h = [0] * n
  for j in range(n):  #ここでビットで正直者たちのフラグを立てていく
    if (i >> j) & 1:
        h[j] = 1
  break_num=0
  for j in range(n):
    for x,y in xy[j]:
      if h[j]==1 and h[x-1]==y:#正直ものの証言&証言とビットが一致する
        pass
      elif h[j]==0 and h[x-1]!=y:#不正直ものの証言&証言とビットが一致しない
        pass
      else:
        break_num=1
        break
    if break_num==1:
      break

  if break_num==0 and ans<sum(h):#矛盾ないかつansより大きければ
    ans=sum(h)
    
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=[]
xy=[]
ans=0
for i in range(n):
  ai=int(input())
  A.append(ai)
  small_xy=[]
  for j in range(ai):
    small_xy.append(list(map(int,input().split())))
  xy.append(small_xy)

for i in range(2 ** n):#全bit探索
  h = [0] * n
  for j in range(n):  #ここでビットで正直者たちのフラグを立てていく
    if (i >> j) & 1:
        h[j] = 1
  break_num=0
  for num,small_xy in enumerate(xy):#Ai個のリスト
    for XY in small_xy:#1個のリスト
      if h[num]==1 and h[XY[0]-1]==XY[1]:#正直ものの証言&証言とビットが一致する
        pass
      elif h[num]==0 and h[XY[0]-1]!=XY[1]:#不正直ものの証言&証言とビットが一致しない
        pass
      else:
        break_num=1
        break
    if break_num==1:
      break

  if break_num==0 and ans<sum(h):#矛盾ないかつansより大きければ
    ans=sum(h)
    
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

arr = []

for _ in range(n):
  a = int(input())
  tmp = [None] * n
  for _ in range(a):
    x, y = map(int, input().split())
    tmp[x-1] = y
  arr.append(tmp)
  
ans = 0
row = 0
for i in range(2**n):
  row = 0
  honest = set()
  lier = set()
  stack = set()
  while i > 0:
    if i % 2 == 1:
      honest.add(row)
      for p,v in enumerate(arr[row]):
        if v == 1:
          honest.add(p)
          stack.add(p)
        elif v == 0:
          lier.add(p)
    i //= 2
    row += 1
    
  while stack:
    row = stack.pop()
    for p,v in enumerate(arr[row]):
      if v == 1:
        honest.add(p)
      elif v == 0:
        lier.add(p)
 
  if len(honest & lier) == 0:
    ans = max(ans, len(honest))

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

N = int(input())


As = []
xys = []
for i in range(N):
    tmp = []
    As.append(int(input()))
    for i in range(As[-1]):
        tmp.append(list(map(int, input().split())))
    
    xys.append(tmp)

#bit演算の準備
bit_list = list(itertools.product(range(2), repeat = N))

#loop
ans = 0 #ansの初期設定
for bit in bit_list:
    unkind_count = 0
    for Aindex, A in enumerate(As):
        if(bit[Aindex] == 0):
            continue #Unkindの意見は参考にしない
        for xy in xys[Aindex]:
#            print(xy)
            #真偽値を値化
            honest_to_unkind = (xy[1] == 0 and bit[xy[0]-1] == 1)
            unkind_to_honest = (xy[1] == 1 and bit[xy[0]-1] == 0)

            if(honest_to_unkind or unkind_to_honest):
                unkind_count +=1
    
        if(unkind_count == 0):
#            print("yatta")
            ans = max(ans, sum(bit))

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

arr = []

for _ in range(n):
  a = int(input())
  tmp = [None] * n
  for _ in range(a):
    x, y = map(int, input().split())
    tmp[x-1] = y
  arr.append(tmp)
  
ans = 0
row = 0
for i in range(2**n):
  row = 0
  honest = set()
  while i > 0:
    if i % 2 == 1:
      honest.add(row)
      [honest.add(j) for j in range(len(arr[row])) if arr[row][j] == 1]
    i //= 2
    row += 1
    
  ok = True
  dic = {}
  people = len(honest)
  while honest:
    p = honest.pop()
    if p in dic and dic[p] != 1:
      ok = False
      break
    dic[p] = 1
    for k,v in enumerate(arr[p]):
      if v == None: continue
      if k in dic and dic[k] != v:
        ok = False
        break
      dic[k] = v
  if ok:
    ans = max(ans, people)

print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(2**N):
  flag = True
  for j in range(N):
    for k in range(A[j]):
      if ((i >> (x[j][k]-1)) & 1) != (y[j][k] == ((i >> j) & 1)):
        flag = False
        break
  if flag:
    count = sum([int(b) for b in bin(i)[2:]])
    ans = max(ans, count)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product
n = int(input())
a = []
xy = []
for i in range(n):
    a.append(int(input()))
    for j in range(a[i]):
        xy.append(list(map(int,input().split())) ) 

cnt = 0
for bit in product([0,1],repeat=n):
    fl = [1] * n #1が正直
    hantei = True
    for i,j in enumerate(bit):
        if j == 1:
            fl[i] = 0
    for k in range(n):
        for l in range(a[k]):
            #証言が矛盾するか判定する
            if fl[k] == 1:
                if fl[xy[l][0]-1] != xy[l][1]:
                    hantei = False
            elif fl[k] == 0:
                if fl[xy[l][0]-1] == xy[l][1]:
                    hantei = False
        if hantei:
            cnt = max(cnt,sum(fl))

print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())

xy = [[] * n for _ 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
def judge(f):
    for i in range(n):
        for j in range(len(xy[i])):
            if f[xy[i][j][0] - 1] != xy[i][j][1] ^ (f[i] ^ 1):
                return False
    return True

for i in range(2 ** n):
    flag = [0] * n
    for j in range(n):
        if i >> j & 1:
            flag[j] = 1
    if judge(flag):
        ans = max(ans, sum(flag))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

xy = [[] * n for _ 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
def judge(f):
    for i in range(n):
        print(xy[i], flag)
        for j in range(len(xy[i])):
            if f[xy[i][j][0] - 1] != xy[i][j][1] ^ (f[i] ^ 1):
                return False
    return True

for i in range(2 ** n):
    flag = [0] * n
    for j in range(n):
        if i >> j & 1:
            flag[j] = 1
    print()
    if judge(flag):
        ans = max(ans, sum(flag))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

xy = [[] * n for _ 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
def judge(p, f):
    for i in range(n):
        for j in range(len(xy[i])):
            if (i in p and flag[xy[i][j][0] - 1] != xy[i][j][1]) or (i not in p and flag[xy[i][j][0] - 1] != xy[i][j][1] ^ 1):
                return False
    return True

for i in range(2 ** n):
    patern = []
    flag = [-1] * n
    for j in range(n):
        if i >> j & 1:
            patern.append(j)
            flag[j] = 1
        else:
            flag[j] = 0
    if judge(patern, flag):
        ans = max(ans, len(patern))
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
shougens = []
for _ in range(N):
    A = int(input())
    s = [] 
    for _ in range(A):
        s.append(tuple(map(int, input().split())))
    shougens.append(s)

maxcount = 0
for li in itertools.product([0, 1], repeat=N):
    for man, shojiki in enumerate(li):
        ss = shougens[man]
        is_break = False
        for x, y in ss:
            x = x - 1
            if not shojiki:
                y = not y
            
            if li[x] != y:
                # 現在のパターンと矛盾した場合
                is_break = True
                break
        
        if is_break:
            break
    else:
        # iのビット1の数
        bitcount = li.count(1)
        if maxcount <= bitcount:
            maxcount = bitcount

print(maxcount)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

import sys
import math

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

# honest_claims[claimer] = a list of honest persons who claimee claims
honest_claims = [0 for _ in range(N)]
unkind_claims = [0 for _ in range(N)]

for i in range(N):
    A = int(input())
    for _ in range(1,A+1):
        j,claim = list(map(int, input().split()))
        if claim == 1:
            honest_claims[i] |= 1<<(j-1)
        else:
            unkind_claims[i] |= 1<<(j-1)

#print([bin(i) for i in honest_claims])
#print([bin(i) for i in unkind_claims])

def get_unkind_claim(honests):
    unkinds = 0
    i = 0
    for _ in range(N):
        if honests & 1 > 0:
            unkinds |= unkind_claims[i]
        honests = honests >> 1
        i += 1
    return unkinds

def get_honest_claim(honests):
    honest_claim = 0
    i = 0
    for _ in range(N):
        if honests & 1 > 0:
            honest_claim |= honest_claims[i]
        honests = honests >> 1
        i += 1
    return honest_claim

def count_1(honests):
    count = 0
    while(honests>0):
        if honests & 1 > 0:
            count += 1
        honests = honests >> 1
    return count

max_honests = 0

for honests in range(1,N+1):
    unkind_claim = get_unkind_claim(honests)
    honest_claim = get_honest_claim(honests)
    if unkind_claim & honests > 0:
        continue
    if (honest_claim | honests) > honests:
        continue
    else:
        max_honests = max(max_honests, count_1(honests))

print(max_honests)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

import sys
import math

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

# honest_claims[claimer] = a list of honest persons who claimee claims
honest_claims = [0 for _ in range(N)]
unkind_claims = [0 for _ in range(N)]

for i in range(N):
    A = int(input())
    for _ in range(1,A+1):
        j,claim = list(map(int, input().split()))
        if claim == 1:
            honest_claims[i] |= 1<<(j-1)
        else:
            unkind_claims[i] |= 1<<(j-1)

#print([bin(i) for i in honest_claims])
#print([bin(i) for i in unkind_claims])

def get_unkind_claim(honests):
    unkinds = 0
    i = 0
    for _ in range(N):
        if honests & 1 > 0:
            unkinds |= unkind_claims[i]
        honests = honests >> 1
        i += 1
    return unkinds

def get_honest_claim(honests):
    honest_claim = 0
    i = 0
    for _ in range(N):
        if honests & 1 > 0:
            honest_claim |= honest_claims[i]
        honests = honests >> 1
        i += 1
    return honest_claim

def count_1(honests):
    count = 0
    while(honests>0):
        if honests & 1 > 0:
            count += 1
        honests = honests >> 1
    return count

max_honests = 0

for honests in range(1,N+1):
    unkind_claim = get_unkind_claim(honests)
    honest_claim = get_honest_claim(honests)
    if unkind_claim & honests > 0:
        continue
    if honest_claim | honests > honests:
        continue
    else:
        max_honests = max(max_honests, count_1(honests))

print(max_honests)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

import sys
import math

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

# honest_claims[claimer] = a list of honest persons who claimee claims
honest_claims = [0 for _ in range(N)]
unkind_claims = [0 for _ in range(N)]

for i in range(N):
    A = int(input())
    for _ in range(1,A+1):
        j,claim = list(map(int, input().split()))
        if claim == 1:
            honest_claims[i] |= 1<<(j-1)
        else:
            unkind_claims[i] |= 1<<(j-1)

print([bin(i) for i in honest_claims])
print([bin(i) for i in unkind_claims])

def get_unkind_claim(honests):
    unkinds = 0
    i = 0
    for _ in range(N):
        if honests & 1 > 0:
            unkinds |= unkind_claims[i]
        honests = honests >> 1
        i += 1
    return unkinds

def get_honest_claim(honests):
    honest_claim = 0
    i = 0
    for _ in range(N):
        if honests & 1 > 0:
            honest_claim |= honest_claims[i]
        honests = honests >> 1
        i += 1
    return honest_claim

def count_1(honests):
    count = 0
    while(honests>0):
        if honests & 1 > 0:
            count += 1
        honests = honests >> 1
    return count

max_honests = 0

for honests in range(1,N+1):
    unkind_claim = get_unkind_claim(honests)
    honest_claim = get_honest_claim(honests)
    if unkind_claim & honests > 0:
        continue
    if honest_claim | honests > honests:
        continue
    else:
        max_honests = max(max_honests, count_1(honests))

print(max_honests)

Submission status: Wrong Answer

Solution code:
from itertools import product
n = int(input())
a = []
xy = []
for i in range(n):
    a.append(int(input()))
    for j in range(a[i]):
        xy.append(list(map(int,input().split())) ) 


cnt = 0 
for bit in product([0,1],repeat=n):
    fl = [1] * n #1が正直
    for i,j in enumerate(bit):
        hantei = True
        if j == 1:
            fl[i] = 0
    for k in range(n):
        for l in range(a[k]):
            #証言が矛盾するか判定する
            if fl[k] == 1:
              if fl[xy[l][0]-1] != xy[l][1]:
                hantei = False
            else:
                if fl[xy[l][0]-1] == xy[l][1]:
                    hantei = False
    if hantei:
        cnt = max(cnt,fl.count(1))

print(cnt)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

import sys
import math

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

# honest_claims[claimer] = a list of honest persons who claimee claims
honest_claims = [[] for _ in range(N+1)]
unkind_claims = [[] for _ in range(N+1)]

for i in range(1,N+1):
    A = int(input())
    for _ in range(1,A+1):
        j,claim = list(map(int, input().split()))
        if claim == 1:
            honest_claims[i].append(j)
        else:
            unkind_claims[i].append(j)

# return a list of honest persons whom #i claims
def get_honests(i, known_honests):
    honests = honest_claims[i]

    # child honests
    child_honests = []
    for honest in list(set(honests) - set(known_honests)):
        child_honests += get_honests(honest, known_honests + [honest])

    return list(set([i]+honests+child_honests))


def get_unkinds(honests):
    unkinds = []

    # unkinds whom honests claim
    for honest in honests:
        unkinds += unkind_claims[honest]

    # unkinds who claim honests are unkind
    for i in range(1,N+1):
        _unkinds = unkind_claims[i]
        if set(honests)&set(_unkinds):
            unkinds.append(i)
    
    return list(set(unkinds))

# suppose #i is honest
max_nrof_honests = 0

for i in range(1,N+1):
    honests = get_honests(i, [i])
    unkinds = get_unkinds(honests)

    if set(honests) & set(unkinds):
        continue
    nrof_unkinds = len(unkinds)
    max_nrof_honests = max(max_nrof_honests, N-nrof_unkinds)

    #print(i, honests, unkinds)

print(max_nrof_honests)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

import sys
import math

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

# honest_claims[claimer] = a list of honest persons who claimee claims
honest_claims = [[] for _ in range(N+1)]
unkind_claims = [[] for _ in range(N+1)]

for i in range(1,N+1):
    A = int(input())
    for _ in range(1,A+1):
        j,claim = list(map(int, input().split()))
        if claim == 1:
            honest_claims[i].append(j)
        else:
            unkind_claims[i].append(j)

# return a list of honest persons whom #i claims
def get_honests(i, known_honests):
    honests = honest_claims[i]

    # child honests
    child_honests = []
    for honest in list(set(honests) - set(known_honests)):
        child_honests += get_honests(honest, known_honests + [honest])

    return list(set([i]+honests+child_honests))


def get_unkinds(honests):
    unkinds = []

    # unkinds whom honests claim
    for honest in honests:
        unkinds += unkind_claims[honest]

    # unkinds who claim honests are unkind
    for i in range(1,N+1):
        _unkinds = unkind_claims[i]
        if set(honests)&set(_unkinds):
            unkinds.append(i)
    
    return list(set(unkinds))

# suppose #i is honest
max_nrof_honests = 0

for i in range(1,N+1):
    honests = get_honests(i, [i])
    unkinds = get_unkinds(honests)

    nrof_unkinds = len(unkinds)
    max_nrof_honests = max(max_nrof_honests, N-nrof_unkinds)

    #print(i, honests, unkinds)

print(max_nrof_honests)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

import sys
import math

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

# honest_claims[claimer] = a list of honest persons who claimee claims
honest_claims = [[] for _ in range(N+1)]
unkind_claims = [[] for _ in range(N+1)]

for i in range(1,N+1):
    A = int(input())
    for _ in range(1,A+1):
        j,claim = list(map(int, input().split()))
        if claim == 1:
            honest_claims[i].append(j)
        else:
            unkind_claims[i].append(j)

# return a list of honest persons whom #i claims
def get_honests(i, depth):
    if depth == 0:
        return []
    honests = honest_claims[i]

    # child honests
    child_honests = []
    for honest in honests:
        child_honests += get_honests(honest, depth-1)

    return list(set([i]+honests+child_honests))


def get_unkinds(honests):
    unkinds = []

    # unkinds whom honests claim
    for honest in honests:
        unkinds += unkind_claims[honest]

    # unkinds who claim honests are unkind
    for i in range(1,N+1):
        _unkinds = unkind_claims[i]
        if set(honests)&set(_unkinds):
            unkinds.append(i)
    
    return list(set(unkinds))

# suppose #i is honest
max_nrof_honests = 0

for i in range(1,N+1):
    honests = get_honests(i, N)
    unkinds = get_unkinds(honests)

    nrof_unkinds = len(unkinds)
    max_nrof_honests = max(max_nrof_honests, N-nrof_unkinds)

    #print(i, honests, unkinds)

print(max_nrof_honests)

Submission status: Wrong Answer

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

mx = 0
for bit in range(1, 1<<n):
    flag = True
    p = [-1] * n
    for i in range(n):
        if bit & (1<<i):
            for j in range(a[i]):
                if p[x[i][j]-1] == -1 and p[i] != 0:
                    p[i] = 1
                    p[x[i][j]-1] = y[i][j]
                elif p[x[i][j]-1] != y[i][j] or p[i] == 0:
                    flag = False
    if flag: mx = max(mx, bin(bit).count('1'))

print(mx)

Submission status: Wrong Answer

Solution code:
import itertools
n=int(input())
l=[]
for i in range(n):
  d=int(input())
  for dd in range(d):
    x,y=map(int,input().split())
    l.append([i,x-1,y])
out=0
for p in itertools.product([0,1],repeat=n):
  for ll in l:
    if p[ll[0]]==1 and p[ll[1]]!=ll[2]:
      out+=1
      break
print(2**n-out)

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = 0
xy = [[] for _ 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-1, y])
for i in range(1<<N):
  flag = 1
  count = list()
  for j in range(N):
    if i>>j & 1:
      count.append(j)
  tl = [-1]*N
  for k in count:
    for x, y in xy[k]:
      if(y == 1):
        if(tl[x] == 0):
          flag = 0
        tl[x] = 1
      else:
        if(tl[x] == 1):
          flag = 0
        tl[x] = 0
  for k in range(N):
    if k in count:
      if tl[k] != 1:
        flag = 0
    else:
      if tl[k] == 1:
        flag = 0
  if(flag == 1):
    ans = max(ans, tl.count(1))
print(ans)