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:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def count_bit_one(bits, n):
    ret = 0
    for keta in range(n):
        if bits & 2**keta:
            ret += 1
    return ret

def is_honest(bits, i):
    return bits & 2**i != 0

n = int(input())
aaa = [None] * n
for i in range(n):
    a = int(input())
    aaa[i] = [ get_nums_l() for _ in range(a)]

ans = -1
# 0:不親切 1:正直
for bits in range(n**2):
    ng = False
    for keta in range(n):
        if is_honest(bits, keta):
            for a in aaa[keta]:
                if is_honest(bits, a[0]-1) != (a[1]==1):
                    ng = True
                    break
        if ng:
            break
    if not ng:
        ans = max(ans, count_bit_one(bits, n))

print(ans)

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def count_bit_one(bits, n):
    ret = 0
    for keta in range(n):
        if bits & 2**keta:
            ret += 1
    return ret

n = int(input())
aaa = [None] * n
for i in range(n):
    a = int(input())
    aaa[i] = [ get_nums_l() for _ in range(a)]

ans = -1
for bits in range(n**2):
    ng = False
    for keta in range(n):
        if bits & 2**keta != 0:
            for a in aaa[keta]:
                if (bits & 2**(a[0]-1) != 0) != (a[1]==1):
                    ng = True
                    break
        if ng:
            break
    if not ng:
        ans = max(ans, count_bit_one(bits, n))

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[0 for j in range(N)]
B=[[] for j in range(N)]
for i in range(N):
 A[i]=int(input())
 for j in range(A[i]):
  x,y=map(int,input().split())
  B[i].append([x,y])
F=0
for i in range(2**N):
 E=0
 Sui=[0]*N
 for j in range(N):
  if ((i >> j) & 1):
   Sui[j]+=1
 E=0
 for k in range(N):
  D=0
  for l in range(A[k]):
   if (Sui[B[k][l][0]-1]+Sui[k]+B[k][l][1])%2==1:
    D+=1
  if D==A[k]:
   E+=1
 if E==N:
  H=0
  for h in range(N):
   H+=Sui[h]
  F=max(F,H)
print(F)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=[[] for i in range(n)]
D=[1]*n

for i in range(n):
    a=int(input())
    #B.append(a)
    for j in range(a):
        b,c=map(int,input().split())
        if c==0:
          D[b-1]=0
          continue
        #A[i].append(b)
        #A[i].append(c)
#for i in range(n):
    
print(sum(D))
#print(cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
a_list_sum = []
for i in range(n):
    a_tmp=int(input())
    a_list_tmp=[list(map(int,input().split())) for _ in range(a_tmp)]
    a_list_sum_tmp=[]
    a_list_sum_tmp.append(a_tmp)
    a_list_sum_tmp.append(a_list_tmp)
    a_list_sum.append(a_list_sum_tmp)
    
import itertools
L = [0, 1] #生成する数字
bit_list = list(itertools.product([0, 1], repeat=n))
print(bit_list)

#bit全探索
for i in range(len(bit_list)):
    count = 0
    #証言者
    for j in range(len(a_list_sum)):
        #正直者について
        if bit_list[i][j] == 1:
            #証言数
            for k in range(len(a_list_sum[j][1])):
                #対象者
                person_id = a_list_sum[j][1][k][0] - 1
                #審議
                is_honest = a_list_sum[j][1][k][1]
                #countが増えることが食い違いを生む
                if bit_list[i][person_id] != is_honest:
                    count += 1
    if count == 0:
        ans = sum(bit_list[i])
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
g = [[-1]*15]*15
for i in range(N):
  m = int(input())
  for _ in range(m):
    x,y = map(int,input().split())
    x -= 1
    g[i][x] = y
ans = 0

for i in range(1<<N):
  d = [0]*N
  for j in range(N):
    if (i>>j&1):
      d[j] = 1
  flag = True
  for j in range(N):
    if d[j]:
      for k in range(N):
        if g[j][k] == -1:
          continue
        if g[j][k] != d[k]:
          flag = False
  if flag:
    ans = max(ans,sum(d))
print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(1<<N):
  d = [0]*N
  for j in range(N):
    if (i>>j&1):
      d[j] = 1
  flag = True
  for j in range(N):
    if d[j] == 1:
      for k in range(N):
        if g[j][k] == -1:
          continue
        if g[j][k] != d[k]:
          flag = False
    ans = max(ans,sum(d))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

for i in range(n):
    a_tmp = int(input())
    for _ in range(a_tmp):
        x,y = map(int,input().split())
        s[i].append([x,y])

#print(s)

mx = 2**n -1


def hantei(num):
    flag=0
    bi =[0 for _ in range(n)]
    for j in range(n):
        bi[j] = (num>>j)%2
    
    for j in range(n):
        if((num>>j)%2 == 1):
            for x,y in s[j]:
                if(y != bi[x-1]):
                    flag = 1
                    return flag
    
    return flag

ans = 0 
for i in range(mx):
    if(hantei(i) == 0):
        #print(i)
        ans = max(ans,bin(i)[2::].count("1"))
        
print(ans)

#print(bin(3)[2::].count("1"))
#print(hantei(3))

Submission status: Wrong Answer

Solution code:
n = int(input())

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

for i in range(n):
    a_tmp = int(input())
    for _ in range(a_tmp):
        x,y = map(int,input().split())
        s[i].append([x,y])

#print(s)

mx = 2**n -1


def hantei(num):
    flag=0
    bi =[0 for _ in range(n)]
    for j in range(n):
        if((num>>j)%2 == 1):
            for x,y in s[j]:
                if(y != bi[x-1]):
                    flag = 1
                    return flag
    
    return flag

ans = 0 
for i in range(mx):
    if(hantei(i) == 0):
        #print(i)
        ans = max(ans,bin(i)[2::].count("1"))
        
print(ans)

#print(bin(3)[2::].count("1"))
#print(hantei(3))

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = []
for i in range(n):
  a = int(input())
  list_ = []
  for _  in range(a):
    tuple_a = (map(int,input().split()))
    list_.append(tuple_a)
  a_list.append(list_)
print(a_list)

case_list = []
for i in range(2**n):
  case = [0 for i in range(n)]
  for j in range(n):
    if ((i >> j) & 1): 
      case[j] = 1
  case_list.append(case)
print(case_list)

Submission status: Wrong Answer

Solution code:
N = int(input())
box = []
for i in range(N):
    temp = int(input())
    box.append([])
    for _ in range(temp):
        box[i].append(list(map(int, input().split())))


ans = 0


# bit全探索
for i in range(N ** 2):
    temp = [True for _ in range(N)]
    flg = True
    for j in range(N):
        if ((i >> j) & 1):
            temp[j] = True
                
        else:
            temp[j] = False
        
    for nn, n in enumerate(temp):
        if n:
            for l, m in box[nn]:
                if m == 0:
                    if temp[l-1]:
                        flg = False
                        break
                else:
                    if not temp[l-1]:
                        flg = False
                        break
            
    if flg:
        ans = max(ans, temp.count(True))

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())

S=[[-1]*N for _ in range(N)]
for _ in range(N):
  A=int(input())
  for i in range(A):
    x, y=map(int, input().split())
    S[i][x-1]=y
ans=0   
for s in range(2**N):
  ok=True
  for i in range(N):
    #正直者について見ていく
    if (s>>i&1)==1:
      for j in range(N):
        #それぞれ正直者の証言が矛盾ないか
        if S[i][j]!=-1 and (s>>j&1)!=S[i][j]:
          ok=False
  if ok:
    ans=max(ans, bin(s).count("1"))
    
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())

S=[[-1]*N for _ in range(N)]
for _ in range(N):
  A=int(input())
  for i in range(A):
    x, y=map(int, input().split())
    S[i][x-1]=y
ans=0   
for s in range(2**N):
  ok=True
  for i in range(N):
    #正直者について見ていく
    if (s<<i&1)==1:
      for j in range(N):
        #それぞれ正直者の証言が矛盾ないか
        if S[i][j]!=-1 and (s>>j&1)!=S[i][j]:
          ok=False
  if ok:
    ans=max(ans, bin(s).count("1"))
    
print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(n):
    honests = [-1 for _ in range(n)]
    honests[i] = 1
    reached = [False for _ in range(n)]
    stack = [i]
    contradict = False
    while len(stack) > 0:
        target = stack.pop(0)
        reached[target] = True
        test = tests[target]
        for xy in test:
            x = xy[0]-1
            y = xy[1]
            if honests[x] >= 0 and honests[x] != y:
                contradict = True
                stack = []
                break
            honests[x] = y
            if not reached[x] and y == 1:
                stack.append(x)
    if contradict:
        continue
    ans = max(ans, sum([j for j in honests if j > 0]))
print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(n):
    honests = [-1 for _ in range(n)]
    honests[i] = 1
    reached = [False for _ in range(n)]
    stack = [i]
    contradict = False
    while len(stack) > 0:
        target = stack.pop(0)
        reached[target] = True
        test = tests[target]
        for xy in test:
            x = xy[0]-1
            y = xy[1]
            if honests[target] == 0:
                continue
            if honests[x] == 1 and y == 0:
                contradict = True
                stack = []
                break
            honests[x] = y
            if not reached[x]:
                stack.append(x)
    if contradict:
        continue
    ans = max(ans, sum([j for j in honests if j > 0]))
print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(n):
    honests = [-1 for _ in range(n)]
    honests[i] = 1
    reached = [False for _ in range(n)]
    stack = [i]
    contradict = False
    while len(stack) > 0:
        target = stack.pop(0)
        reached[target] = True
        test = tests[target]
        for xy in test:
            x = xy[0]
            y = xy[1]
            if honests[target] == 0:
                y = int(not y)
            if honests[x-1] is not -1 and honests[x-1] != y:
                contradict = True
                stack = []
                break
            honests[x-1] = y
            if not reached[x-1]:
                stack.append(x-1)
    if contradict:
        continue
    ans = max(ans, sum([j for j in honests if j > 0]))
print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(n):
    honests = [-1 for _ in range(n)]
    honests[i] = 1
    reached = [False for _ in range(n)]
    stack = [i]
    contradict = False
    while len(stack) > 0:
        target = stack.pop(0)
        reached[target] = True
        test = tests[target]
        for xy in test:
            x = xy[0]
            y = xy[1]
            if honests[target] == 0:
                y = not y
            if honests[x-1] >= 0 and honests[x-1] != y:
                contradict = True
                stack = []
                break
            honests[x-1] = y
            if not reached[x-1]:
                stack.append(x-1)
    if contradict:
        continue
    ans = max(ans, sum([j for j in honests if j > 0]))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
w = [[] for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        w[i].append([int(x) for x in input().split()])

ans = 0
for i in range(2**n):
    flag = 1
    f = [0]*n
    num = 0
    for j in range(n):
        if i & 1<<j:
            f[j] = 1
            num += 1
    for j in range(n):
        if f[j]==1:
            for k in w[j]:
                if k[1]!=f[k[0]-1]:
                    flag = 0
        else:
            for k in w[j]:
                if k[1]==f[k[0]-1]:
                    flag = 0
    
    if flag == 1:
        ans = max(ans,num)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

g = [[-1]*n]*n

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

ans = 0
for s in range(2**n):
	ok = True
	for i in range(n):
		if (s>>i&1) == 1:
			for j in range(n):
				if g[i][j] != -1 and (s>>j&1) != g[i][j]:
					ok = False
	if ok:
		ans = max(ans, bin(s).count("1"))

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

g = [[-1] * n] * n

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

ans = 0
for s in range(2**n):
	ok = True
	for i in range(n):
		if (s>>i&1) == 1:
			for j in range(n):
				if g[i][j] == -1: continue
				if (s>>j&1) != g[i][j]:ok = False
	if ok:
		ans = max(ans, bin(s).count("1"))

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
g = [[-1] * n] * n

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

ans = 0
for s in range(2**n):
	ok = True
	for i in range(n):
		if (s>>i&1) == 1:
			for j in range(n):
				if g[i][j] == -1: continue
				if (s>>j&1) != g[i][j]: ok = False
	if ok:
		ans = max(ans, bin(s).count("1"))

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    testimony = [[] for i in range(N)]
    for i in range(N):
        for j in range(int(input())):
            x,y = map(int,input().split())
            testimony[i].append([x,y])
    
    ans = 0
    for i in range(2**N):##証言について、2^N通り
        for j in range(N):##N人について検証
            flag = True
            if (i>>j)&1:##正直者である場合
                for x,y in testimony[j]:
                    if ((i>>x)&1) != y:##嘘をついている
                        flag = False
                        break
                if not flag:
                    break        
        if flag:##全員正直であった場合
            tmp = list(bin(i))
            ans = max(ans,tmp[2:].count("1"))

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import itertools
 
n = int(input())
l =[]
 
for _ in range(n):
  a = int(input())
  m = []
  for _ in range(a):
    xn, yn = map(int, input().split())
    m.append([xn-1, yn])
  l.append(m)
 
for i in itertools.product([1, 0], repeat=n):
  i = list(i)
  print(i)
  flg = 0
  for j in range(n):
    for k in l[j]:
      if i[j] == 1:
        if i[k[0]] != k[1]:
          flg += 1
          break
      if flg != 0:
        break
  if flg == 0:
    break
    
print(sum(i))

Submission status: Wrong Answer

Solution code:
import itertools
 
n = int(input())
l =[]
 
for _ in range(n):
  a = int(input())
  m = []
  for _ in range(a):
    xn, yn = map(int, input().split())
    m.append([xn-1, yn])
  l.append(m)
 
for i in itertools.product([1, 0], repeat=n):
  i = list(i)
  print(i)
  flg = 0
  for j in range(n):
    for k in l[j]:
      if i[j] == 1:
        if i[k[0]] != k[1]:
          flg += 1
          break
  if flg == 0:
    break
    
print(sum(i))

Submission status: Wrong Answer

Solution code:
import itertools

n = int(input())
l =[]

for _ in range(n):
  a = int(input())
  m = []
  for _ in range(a):
    xn, yn = map(int, input().split())
    m.append([xn-1, yn])
  l.append(m)

for i in itertools.product([1, 0], repeat=n):
  i = list(i)
  flg = 0
  for j in range(n):
    for k in l[j]:
      if i[j] == 1:
        if i[k[0]] != k[1]:
          flg += 1
          break
      if flg != 0:
        break
  print(i)
  if flg == 0:
    break
    
print(sum(i))

Submission status: Wrong Answer

Solution code:
import itertools

n = int(input())
l =[]

for _ in range(n):
  a = int(input())
  m = []
  for _ in range(a):
    xn, yn = map(int, input().split())
    m.append([xn-1, yn])
  l.append(m)

for i in itertools.product([1, 0], repeat=n):
  i = list(i)
  flg = 0
  for j in range(n):
    for k in l[j]:
      if i[j] == 1:
        if i[k[0]] != k[1]:
          flg += 1
          break
      else:
        if i[k[0]] == k[1]:
          flg += 1
          break
      if flg != 0:
        break
  if flg == 0:
    break
    
print(sum(i))

Submission status: Wrong Answer

Solution code:
N = int(input())
true_humans = []

for i in range(2**3):
    ls = [False for n in range(N)]
    for j in range(len(ls)):
        if (i >> j) & 1:
            ls[j] = True
    true_humans.append(ls)    
    

testimonys = []
for n in range(N):
  A = int(input())
  tmp = {}
  for a in range(A):
    x, y = map(int, input().split())
    y = bool(y)
    tmp[x] = y
  testimonys.append(tmp)

true_mem = 0

for humans in true_humans:
  flg = True
  for human_index in range(len(humans)):
    is_true_man = humans[human_index]
    values = testimonys[human_index]
    for key, value in values.items():
      value = value if is_true_man else not value
      if value != humans[key-1]:
        flg = False
        break
    if not flg:
      break
  if flg:
    true_mem = max(true_mem, sum([1 for i in humans if i == True]))
  
print(true_mem)

Submission status: Wrong Answer

Solution code:
# HonestOrUnkind2
# input
N = int(input())
maxlen = len(bin(2**N-1)[2:])
testimonies = {}

for i in range(N):
    testimony = []
    n = int(input())
    for j in range(n):
        x, y = input().split()        
        testimony.append({'x':int(x), 'y':int(y)})
    testimonies[i+1] = testimony

possible_num = 0
for _ in range(2**N):
    A = {}
    case = [int(e) for e in (bin(_)[2:].zfill(maxlen))]
    for i, t in enumerate(case):
        # 仮定によって正直者になる人を全て列挙する必要がある
        if t == 1:
            if i+1 not in A.keys():
                A[i+1] = [1]
            else:
                A[i+1].append(1) # 繰り返しの仮定により正直者
            for testimony in testimonies[i+1]:
                if testimony['x'] not in A.keys():
                    A[testimony['x']] = []
                A[testimony['x']].append(testimony['y'])
                if testimony['y'] == 1:
                    # 仮定により正直者なのでこの人の証言も検証する
                    for testimony_x in testimonies[testimony['x']]:
                        if testimony_x['x'] not in A.keys():
                            A[testimony_x['x']] = []
                        A[testimony_x['x']].append(testimony_x['y'])
                
    if A.values():
        res = [len(set(e)) for e in A.values()]
        if len(res) == len([e for e in res if e == 1]):
            possible_num = max(sum(case), possible_num)
            # print('------')
            # print(case)
            # print('possible:', A)
# output
print(possible_num)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N = inputI()
l = []
for i in range(N):
  a = inputI()
  l.append(inputILL(a))

best = 0
for i in range(pow(2,N)):
  OKAY = True
  count = 0
  temp = i
  while temp:
    temp &= temp -1
    count += 1
  for n in range(N):
    if ((pow(2,n)&i )>> n) & 1:
      for statement in l[n]:
        if not ((pow(2,statement[0]-1)&i)>>(statement[0]-1) )^ statement[1]:
          OKAY = False
  if OKAY == True:
    best = max(best,count)

print(best)

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N = inputI()
l = []
for i in range(N):
  a = inputI()
  l.append(inputILL(a))

best = 0
for i in range(pow(2,N)):
  OKAY = True
  count = 0
  temp = i
  while temp:
    temp &= temp -1
    count += 1
  for n in range(N):
    if (pow(2,n)&i > n) == 1:
      for statement in l[n]:
        if (pow(2,statement[0])^i)>statement[0] & 1:
          OKAY = False
  if OKAY == True:
    best = max(best,count)

print(best)

Submission status: Wrong Answer

Solution code:
from queue import Queue

N = int(input())

data = {}

for i in range(N):
  i = i + 1
  data[i] = {}
  for _ in range(int(input())):
    x, y = map(int, input().split())
    data[i][x] = y

count = 0
for i in data:
  queue = Queue()
  queue.put(i)
  memo = {i: 1}
  contradictory = False
  while not queue.empty() and not contradictory:
    i = queue.get()
    for x, y in data[i].items():
      if x in memo:
        if y != memo[x]:
          contradictory = True
          break
      else:
        memo[x] = y
        if y == 1:
          queue.put(x)

  if not contradictory:
    count = max(count, sum(memo.values()))

print(count)

Submission status: Wrong Answer

Solution code:
from queue import Queue

N = int(input())

data = {}

for i in range(N):
  i = i + 1
  data[i] = {}
  for _ in range(int(input())):
    x, y = map(int, input().split())
    data[i][x] = y

count = 0
for i in data:
  queue = Queue()
  queue.put(i)
  true = set()
  true.add(i)
  contradictory = False
  while not queue.empty() and not contradictory:
    i = queue.get()
    for x, y in data[i].items():
      if y == 1 and x not in true:
        true.add(x)
        queue.put(x)
      if y == 0 and x in true:
        contradictory = True
        break

  if not contradictory:
    count = max(count, len(true))

print(count)

Submission status: Wrong Answer

Solution code:
from queue import Queue

N = int(input())

data = {}

for i in range(N):
  i = i + 1
  data[i] = {}
  for _ in range(int(input())):
    x, y = map(int, input().split())
    data[i][x] = y

count = 0
for i in data:
  memo = {i: 1}
  queue = Queue()
  queue.put(i)

  true = set()
  true.add(i)
  contradictory = False
  while not queue.empty():
    i = queue.get()
    for x, y in data[i].items():
      if y and x not in true:
        true.add(x)
        queue.put(x)
      if x in memo:
        if memo[x] != y:
          contradictory = True
          break
      else:
        memo[x] = y

  if not contradictory:
    count = max(count, len(true))

print(count)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

N = int(input())
A = []
xy = []
ans = []
sm = 0

for _ in range(N):
    temp = int(input())
    A.append([temp, sm])
    sm += temp
    for _ in range(A[-1][0]):
        xy.append(list(map(int, input().split())))

for i in range(2**N):
    flag = True
    binary = bin(i)[2:]
    if len(binary) < N:
        binary = '0' * (N - len(binary)) + binary
    check = [0]*N
    for j, digit in enumerate(binary):
        if digit == '1':
            check[j] = 1

    for j, value in enumerate(check):
        if value == 1:
            for k in range(A[j][0]):
                x = xy[A[j][1]+k-1][0] - 1
                y = xy[A[j][1]+k-1][1]
                if check[x] != y:
                    flag = False
    if flag:
        ans.append(check.count(1))

print(max(ans))

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
a = {"{}".format(i): [] for i in range(1, n+1)}
for key in a.keys():
    t = int(input())
    for _ in range(t): a[key].append(list(map(str, input().split())))
ans = [0]
for key in a.keys():
    q = deque()
    cnt = deque()
    cnt.append(key)
    e = False
    for val in a[key]:
        if val[1] == "1":
            q.append(val[0])
    while len(q) != 0:
        qi = q[0]
        for val in a[qi]:
            if val[0] in cnt:
                if val[1] == "1":
                    continue
                else:
                    e = True
                    break
            else:
                if val[1] == "1":
                    q.append(val[0])
        if e:
            break
        cnt.append(qi)
        q.pop()
    if e: continue
    else:
        ans.append(len(cnt))
print(max(ans))