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 sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XY = []
for _ in range(N):
    A = int(input())
    xy = [list(mapint()) for _ in range(A)]
    XY.append(xy)

ans = 0
for i in range(1<<N):
    honest = [-1]*N
    cnt = 0
    for j in range(N):
        if (i>>j)&1:
            cnt += 1
            if honest[j]==0:
                break
            honest[j] = 1
            flg = False
            for x, y in XY[j]:
                if y==0:
                    if honest[x-1]==1:
                        break
                    else:
                        honest[x-1] = 0
                if y==1:
                    if honest[x-1]==0:
                        break
                    else:
                        honest[x-1] = 1
            else:
                flg = True
            if not flg:
                break
    else:
        ans = max(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XY = []
for _ in range(N):
    A = int(input())
    xy = [list(mapint()) for _ in range(A)]
    XY.append(xy)

ans = 0
for i in range(1<<N):
    honest = [-1]*N
    cnt = 0
    for j in range(N):
        if (i>>j)&1:
            cnt += 1
            if honest[j]==0:
                break
            honest[j] = 1
            for x, y in XY[j]:
                if y==0:
                    if honest[x-1]==1:
                        break
                    else:
                        honest[x-1] = 0
                if y==1:
                    if honest[x-1]==0:
                        break
                    else:
                        honest[x-1] = 1
            else:
                ans = max(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XY = []
for _ in range(N):
    A = int(input())
    xy = [list(mapint()) for _ in range(A)]
    XY.append(xy)

ans = 0
for i in range(1<<N):
    honest = [-1]*N
    cnt = 0
    for j in range(N):
        if (i>>j)&1:
            cnt += 1
            honest[j] = 1
            for x, y in XY[j]:
                if y==0:
                    if honest[x-1]==1:
                        break
                    else:
                        honest[x-1] = 0
                if y==1:
                    if honest[x-1]==0:
                        break
                    else:
                        honest[x-1] = 1
            else:
                ans = max(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product

def solve():
    N = int(input())
    graph = {i: [] for i in range(1, N+1)}
    for i in range(N): 
        A = int(input())
        for _ in range(A):
            x,y = map(int, input().split())
            graph[i+1].append((x,y))
            
    def dfs(nodes):
        searched = [-1] * N
        stack = [i+1 for i,node in enumerate(nodes) if node == 1]
        ret_len = len(stack)
        
        while stack:
            node = stack.pop(0)
            for x,y in graph[node]:
                if nodes[x-1] != y: return -1
                if searched[x-1] == -1:
                    searched[x-1] = y
                    if y == 1: stack.append(x)
                        
        # print(nodes, searched)
        return ret_len
                    
        
    ret = 0
    for nodes in product([0,1], repeat=N):
        ret = max(ret, dfs(nodes))
        
    print(ret)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

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

ans=[0]
for i in range(2**n):
    ch=1
    for k in range(0,n):
        if ((i>>k)&1):
            c=1
        else:
            c=0
        for q in a[k]:
            if ((i>>q[0])&1)==(q[1]^c):
                ch=0
    if ch==1:
        ans.append(bin(i).count("1"))
print(max(ans))

Submission status: Wrong Answer

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

ans = 0
for i in range(2**n):
    f = [False]*n
    xy = []
    for j in range(n):
        if (i >> j) & 1:
            f[j] = True
            xy.append(v[j])
    flag = True
    for xyi in xy:
        for x,y in xyi:
            if not (f[x-1] and y):
                flag = False
                break
    if flag:
        ans = max(ans,len(xy))
print(ans)

Submission status: Wrong Answer

Solution code:
from typing import List

# 人iの証言を人jに対する証言をリストで格納。1:正直者, 0:不親切, -1:言及なし
def io_info() -> List[List[int]]:
    N = int(input())
    res = [[-1] * N for _ in range(N)]
    for n in range(N):
        a = int(input())
        for _ in range(a):
            x, y = map(int, input().split())
            res[n][x-1] = y
    return res

def main():
    infos = io_info()
    n = len(infos)
    ans = 0
    for i in range(1 << n):
        d = [0] * n
        for j in range(n):
            # iのj+1ビット目が1かどうか,d[j]が正直なら1を割り当てる
            if (i >> j & 1):
                d[j] = 1
        ok = True
        for k in range(n):
            if infos[j][k] == -1: continue
            if infos[j][k] != d[k]: ok = False
        if ok: ans = max(ans, bin(i).count("1"))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from typing import List, Tuple

def io_readline() -> List[List[Tuple[int, ...]]]:
    N = int(input())
    res = []
    for n in range(N):
        a_n = int(input())
        n_testimony = []
        for _ in range(a_n):
            testimony = tuple(map(int, input().split()))
            n_testimony.append(testimony)
        res.append(n_testimony)
    return res


infos = io_readline()
ans = 0
for i in range(2 ** len(infos)):
    cnt = bin(i).count("1")
    if cnt <= ans:
        continue

    for j in range(len(infos)):
        if i & (1 << j):
            for x, y in infos[j]:
                if y == 1 and i % (1 << x):
                    continue
                elif y == 0 and i % (1 << x) == 0:
                    continue
                else:
                    break
            else:
                continue
            break
    else:
        ans = cnt

print(ans)

Submission status: Wrong Answer

Solution code:
from typing import List, Tuple

def io_readline() -> List[List[Tuple[int, ...]]]:
    N = int(input())
    res = []
    for n in range(N):
        a_n = int(input())
        n_testimony = []
        for _ in range(a_n):
            testimony = tuple(map(int, input().split()))
            n_testimony.append(testimony)
        res.append(n_testimony)
    return res


infos = io_readline()
ans = 0
for i in range(2 ** len(infos)):
    cnt = bin(i).count("1")
    if cnt <= ans:
        continue

    for j in range(2 ** len(infos)):
        # 1を左シフト
        if i & (1 << j):
            for x, y in infos[j]:
                if y == 1 and i % (1 << x):
                    continue
                elif y == 0 and i % (1 << x) == 0:
                    continue
                else:
                    break
            else:
                continue
            break
    else:
        ans = cnt

print(ans)

Submission status: Wrong Answer

Solution code:
from typing import List, Tuple

def io_readline() -> List[List[Tuple[int, ...]]]:
    N = int(input())
    res = []
    for n in range(N):
        a_n = int(input())
        n_testimony = []
        for _ in range(a_n):
            testimony = tuple(map(int, input().split()))
            n_testimony.append(testimony)
        res.append(n_testimony)
    return res


infos = io_readline()
ans = 0
for i in range(2 ** len(infos)):
    cnt = bin(i).count("1")
    if cnt <= ans:
        continue

    for j in range(2 ** len(infos)):
        # 1を左シフト
        if i & (1 << j):
            print(f'{bin(i)}:  {bin(1 << j)}')
            for x, y in infos[j]:
                if y == 1 and i % (1 << x):
                    continue
                elif y == 0 and i % (1 << x) == 0:
                    continue
                else:
                    break
            else:
                continue
            break
    else:
        ans = cnt

print(ans)

Submission status: Wrong Answer

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

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

res = 0
for i in range(2**N-1):
    bi = [j for j in range(N) if (i >> j &1)]
    dic = {}
    for b in bi:
        dic[b] = 1
    
    endfor = False
    for b1 in bi:
        if endfor:
            break
        said = table[b1]
        for k in said.keys():
            if k not in dic.keys():
                if said[k]:
                    endfor = True
                    break
                dic[k] = said[k]
            elif dic[k] == said[k]:
                continue
            else:
                endfor = True
                break
    if not endfor:
        res = max(res, len(bi))

print(res)

Submission status: Wrong Answer

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

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

res = 0
for i in range(2**N-1):
    bi = [j for j in range(N) if (i >> j &1)]
    dic = {}
    for b in bi:
        dic[b] = 1
    
    endfor = False
    for b1 in bi:
        if endfor:
            break
        said = table[b1]
        for k in said.keys():
            if k not in dic.keys():
                dic[k] = said[k]
                if dic[k]:
                    bi.append(k)
            elif dic[k] == said[k]:
                continue
            else:
                endfor = True
    if not endfor:
        res = max(res, len(bi))

print(res)

Submission status: Wrong Answer

Solution code:
import itertools

def main():
    N = int(input())
    xy = [0] * N
    for i in range(N):
        A = int(input())
        xy_list = []
        for _ in range(A):
            x, y = map(int, input().split())
            xy_list.append((x, y))
        xy[i] = xy_list

    res = 0
    tf_gen = itertools.product([0, 1], repeat=N)
    for tf in tf_gen:
        honest = sum(tf)
        able = True
        for i, xy_l in enumerate(xy):
            for (x, y) in xy_l:
                if tf[x-1] != y and tf[i] == 1:
                    able = False
                elif tf[x-1] == y and tf[i] == 0:
                    able = False
        if res < honest and able:
            res = honest
    print(res)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import itertools

def main():
    N = int(input())
    xy = [0] * N
    for i in range(N):
        A = int(input())
        xy_list = []
        for _ in range(A):
            x, y = map(int, input().split())
            xy_list.append((x, y))
        xy[i] = xy_list

    res = 0
    tf_gen = itertools.product([0, 1], repeat=N)
    for tf in tf_gen:
        honest = sum(tf)
        able = True
        for i, xy_l in enumerate(xy):
            for (x, y) in xy_l:
                if tf[x-1] != y and tf[i] == 1:
                    able = False
                elif tf[x-1] == y and tf[i] == 0:
                    able = False
            if not able:
                break
        if res < honest and able:
            res = honest
    print(res)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def II(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
N=II()
Shogens=[[] for i in range(N)]
for i in range(N):
  A=II()
  for j in range(A):
    x,y=MI()
    x-=1
    Shogens[i].append((x,y))
#print(Shogens)

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
ans=0
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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
    N  = int(input())
    R = [[] for i in range(N)]
    for i in range(N):
        A = int(input())
        R[i] = [list(map(int, input().split())) for i in range(A)]
    ans = 0
    for i in range(1<<N):
        CNT = 0
        for j in range(N):
            if not (i>>j & 1):
                continue
            CNT += 1
            for x, y in R[j]:
                if y == 1 and (i>>(x-1) & 1):
                    continue
                else:
                    CNT = 0
                    break

        ans = max(ans, CNT)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict, deque

n, a, s, h = int(input()), [], [], []
for i in range(n): a.append(int(input())); s.append(list(list(map(int, input().split())) for _ in range(a[i])))
for i in range(2 ** n):
    flag = False
    for j in range(n):
        if (i >> j) & n == 1:
            for ps in s[j]:
                if (i >> (ps[0]-1) & 1) != ps[1]: flag = True; break
    if not flag: h.append(bin(i)[2:].count('1'))
print(max(h))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict, deque

n, a, s, h = int(input()), [], [], []
for i in range(n): a.append(int(input())); s.append(list(list(map(int, input().split())) for _ in range(a[i])))
for i in range(2 ** n):
    flag = False
    for j in range(n):
        if (i >> j) & n == 1:
            for ps in s[j]:
                if ((i >> ps[0]-1) & 1) != ps[1]: flag = True; break
    if not flag: h.append(bin(i)[2:].count('1'))
print(max(h))

Submission status: Wrong Answer

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[i])]]
honest = []
for i in range(2 ** n):
    flag = 0
    for j in range(n):
        if (i >> j)&1 == 1: #j番目は正直であるとき
            for person_state in xy[j]:
                if (i >> person_state[0] & 1) != person_state[1]:
                    flag = 1 #矛盾が生じるとflagを立てる
                    break
    if flag == 0:
        honest += [bin(i)[2:].count("1")]
print(max(honest))

Submission status: Wrong Answer

Solution code:
# import itertools
# import math

N = int(input())
# S = input()
# n, *a = map(int, open(0))
# A, B, X = map(int, input().split())
# A = list(map(int, input().split()))
# S = input()

in_list = []

for i in range(N):
    A_i = int(input())
    _list = []
    for j in range(A_i):
        x_ij, y_ij = map(int, input().split())
        _list.append([x_ij, y_ij])
    in_list.append(_list)

cnt = 0
for i in range(2 ** N):
    for j in range(N):
        # print(i, end=" ")
        # print(bin(i)[2:].zfill(N), end=" ")
        # print(j, end=" ")
        # print((i>>j) & 1) # i >> j はiをjビット右シフト、x & y はxとyの同じ位置のビットが両方1の場合1とする→0110 & 1(0001) = 0000
        flg = 0
        if ((i>>j) & 1 == 0): # flgは正直0 嘘1
            flg = 1
        for l in in_list[j]:
            if (((i>>l[0] - 1) ^ l[1]) ^ flg) & 1: # 証言不一致1, 一致0 -> 不一致だが、正直ならやっぱりダメ
                # print(i,bin(i)[2:].zfill(N),(i>>l[0] - 1),(i>>l[0] - 1) ^ l[1],((i>>l[0] - 1) ^ l[1]) ^ flg,l,flg)
                break
        else:
            continue
        break
    else:
        # print(i, bin(i))
        _ = bin(i)[2:].zfill(N).count("1")
        cnt = max(cnt, _)
    continue

print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
proof_list=np.array([[None]*N for i in range(N)])
check_list=[True]*N
for i in range(N):
    A = int(input())
    for j in range(A):
        x,y = map(int,input().split())
        if(y==1):
            proof_list[i][x-1] = True
        else:
            proof_list[i][x-1] = False
proof_list_origin = proof_list.copy()
ans = 0
check = True
for i in range(2**N):
    for j in range(N):
        if((i>>j)&1):
            check_list[j] = False
            for k in range(N):
                if(proof_list[j][k]!=None):
                    proof_list[j][k]= not proof_list[j][k]
        else:
            check_list[j] = True
   
    for l in range(N):
        if((True in proof_list[:,l]) or (False in proof_list[:,l])):
            if((check_list[l] in proof_list[:,l]) and ((not check_list[l]) not in proof_list[:,l])):
                pass
            else:
                check = False
    if(check):
        ans = max(ans,check_list.count(True))
    check = True
    proof_list = proof_list_origin
print(ans)

Submission status: Wrong Answer

Solution code:
#abc147c　HonestOrUnkind
n = int(input())
XY = [[] for _ in range(n)]
for i in range(n):
    num = int(input())
    for j in range(num):
        x, y = map(int, input().split())
        XY[i].append([x-1, y])
honest = 0
for bit in range(1<<n):
    flag = True 
    for i in range(n):
        if (bit>>i) & 1 == 1:
            for a, b in XY[i]:
                if (bit>>a)&1 != b:
                    flag = False 
                    break
    if flag:
        honest = max(honest, bin(i)[2:].count('1'))
print(honest)

Submission status: Wrong Answer

Solution code:
n = int(input())
XY = [[] for _ in range(n)]
for i in range(n):
    for j in range(int(input())):
        x, y = map(int, input().split())
        XY[i].append([x-1, y])
honest = 0
for bit in range(1<<n):
    flag = True 
    for i in range(n):
        if bit>>i & 1:
            for a, b in XY[i]:
                if (bit>>a)&1 != b:
                    flag = False 
                    break
    if flag:
        honest = max(honest, bin(i).count('1'))
print(honest)

Submission status: Wrong Answer

Solution code:
#abc147c　HonestOrUnkind
n = int(input())
XY = [[] for _ in range(n)]
for i in range(n):
    for j in range(int(input())):
        x, y = map(int, input().split())
        XY[i].append([x-1, y])
honest = 0
for bit in range(1<<n):
    flag = True 
    for i in range(n):
        if bit & (1<<i) :
            for a, b in XY[i]:
                if bit & (1<<a) != b:
                    flag = False 
                    break
    if flag:
        honest = max(honest, bin(i).count('1'))
        print(honest)
print(honest)

Submission status: Wrong Answer

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[i])]]

honest = []
for i in range(2 ** n):
    flag = 0
    for j in range(n):
        if (i >> j)&1 == 1: #j番目は正直であるとき
            for per_sta in xy[j]:
                if (i >> per_sta[0] & 1) != per_sta[1]:
                    flag = 1
                    break
    if flag == 0:
        honest += [bin(i)[2:].count("1")]

print(max(honest))

Submission status: Wrong Answer

Solution code:
from typing import List, Tuple

# 入力を受け取る
def get_testimonies(num: int) -> List[List[Tuple[int, ...]]]:
    res = []
    for n in range(num):
        a_n = int(input())
        n_testimony = []
        for _ in range(a_n):
            testimony = tuple(map(int, input().split()))
            n_testimony.append(testimony)
        res.append(n_testimony)
    return res


N = int(input())
infos = get_testimonies(N)

max_cnt = 0
for i in range(len(infos)):
    cnt = 1
    honesty = [x for x, y in infos[i] if y == 1]
    unkind = [x for x, y in infos[i] if y == 0]
    # print(f'i: {i}, honesty: {honesty}, unkind: {unkind}')
    for j in range(len(infos)):
        if j == i or j+1 in unkind:
            continue

        j_honesty = [x for x, y in infos[j] if y == 1]
        j_unkind = [x for x, y in infos[j] if y == 0]
        # print(f'j: {j}, j_honesty: {j_honesty}, j_unkind: {j_unkind}')
        is_contradiction: bool = len([h for h in honesty if h in j_unkind]) + len([u for u in unkind if u in j_honesty]) > 0
        if is_contradiction:
            cnt = 0
            # print("--BREAK--")
            break
        elif j+1 in honesty:
            cnt += 1

    max_cnt = max(max_cnt, cnt)

print(max_cnt)

Submission status: Wrong Answer

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

for i in range(2**n):
    honest = []
    honest_F = False

    for j in range(n):
        if i>>j & 1:
            honest.append(j)

    for j in honest:
        honest_F = False
        judge = lst[j]
        for k in judge:
            if k[1] == 1:
                if not k[0] in honest:
                    break
            else:
                if k[0] in honest:
                    break
        else:
            honest_F = True
    if honest_F:
        ans = max(ans, len(honest))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
n=int(input())
A=[]
xy=[[]]*n
for i in range(n):
    a=int(input())
    A.append(a)
    xy[i]=[list(map(int,input().split())) for _ in range(a)]

ans=0

for bit in range(1<<n):
    tmp=0
    for i in range(n):
        if bit>>i & 1:
            cnt=0
            for elem in xy[i]:
                if elem[1]==1:
                    if bit>>(elem[0]-1) & 1:
                        cnt+=1
                else:
                    if not (bit>>(elem[0]-1) & 1):
                        cnt+=1
            if cnt==A[i]:
                tmp+=1
            else:
                continue
    if bin(tmp) ==bin(bit):
        aa=0
        for p in range(len(bin(bit))):
            if bin(bit)[p]==1:
                aa+=1
        ans=max(aa,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
n=int(input())
A=[]
xy=[[]]*n
for i in range(n):
    a=int(input())
    A.append(a)
    xy[i]=[list(map(int,input().split())) for _ in range(a)]

ans=0

for bit in range(1<<n):
    tmp=0
    for i in range(n):
        if bit>>i & 1:
            cnt=0
            for elem in xy[i]:
                if elem[1]==1:
                    if bit>>(elem[0]-1) & 1:
                        cnt+=1
                else:
                    if bit>>(elem[0]-1) & 1:
                        break
                    else:
                        cnt+=1
            if cnt==A[i]:
                tmp+=1
            else:
                continue
    ans=max(tmp,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3]
import sys
sys.setrecursionlimit(2000)

N = int(input())
syogen = []
for i in range(N):
    N_a = int(input())
    syogen_a = []
    for _ in range(N_a):
        x, y = input().split()
        syogen_a.append([int(x) - 1, int(y)])
    syogen.append(syogen_a)


def syojiki(i):
    for x, y in syogen[i]:
        if y == 1:
            syojiki_list.append(x)
            if len(syojiki_list) >= N:
                return
            syojiki(x)


def check_syojiki(syojikitati):
    d = {}
    for s in range(N):
        if not (s in syojikitati):
            d[s] = 0

    for s in syojikitati:
        d[s] = 1
        for x, y in syogen[s]:
            if not d.get(x) is None:
                if d[x] != y:
                    return False
            else:
                d[x] = y
    return True


max_syojiki = 0

for i in range(2 ** N):
    d = {}
    syojiki_list = []
    for j in range(N):
        if (i >> j) & 1:
            syojiki_list.append(j)
            syojiki(j)
    syojiki_list = list(set(syojiki_list))
    if check_syojiki(syojiki_list):
        max_syojiki = max(max_syojiki, len(syojiki_list))

print(max_syojiki)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3]
import sys
sys.setrecursionlimit(2000)

N = int(input())
syogen = []
for i in range(N):
    N_a = int(input())
    syogen_a = []
    for _ in range(N_a):
        x, y = input().split()
        syogen_a.append([int(x) - 1, int(y)])
    syogen.append(syogen_a)


def syojiki(i):
    for x, y in syogen[i]:
        if y == 1:
            syojiki_list.append(x)
            if len(syojiki_list) >= N:
                return
            syojiki(x)


def check_syojiki(syojikitati):
    d = {}
    for s in syojikitati:
        d[s] = 1
        for x, y in syogen[s]:
            if not d.get(x) is None:
                if d[x] != y:
                    return False
            else:
                d[x] = y
    return True


max_syojiki = 0

for i in range(2 ** N):
    d = {}
    syojiki_list = []
    for j in range(N):
        if (i >> j) & 1:
            syojiki_list.append(j)
            syojiki(j)
    syojiki_list = list(set(syojiki_list))
    if check_syojiki(syojiki_list):
        max_syojiki = max(max_syojiki, len(syojiki_list))

print(max_syojiki)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3]
import sys
sys.setrecursionlimit(2000)

N = int(input())
syogen = []
for i in range(N):
    N_a = int(input())
    syogen_a = []
    for _ in range(N_a):
        x, y = input().split()
        syogen_a.append([int(x) - 1, int(y)])
    syogen.append(syogen_a)

max_syojiki = 0


def syojiki(i):
    for x, y in syogen[i]:
        if y == 1:
            syojiki_list.append(x)
            if len(syojiki_list) >= N:
                return
            syojiki(x)


def check_syojiki(syojikitati):
    d = {}
    for s in syojikitati:
        for x, y in syogen[s]:
            if not d.get(x) is None:
                if d[x] != y:
                    return False
            else:
                d[x] = y
    return True


for i in range(2 ** N):
    d = {}
    num_syojiki = 0
    syojiki_list = []
    for j in range(N):
        if (i >> j) & 1:
            syojiki_list.append(j)
            syojiki(j)
    syojiki_list = list(set(syojiki_list))
    if check_syojiki(syojiki_list):
        max_syojiki = max(max_syojiki, len(syojiki_list))

print(max_syojiki)

Submission status: Wrong Answer

Solution code:
n = int(input())
lst = [True] * n
answers = []
for i in range(n):
	a = int(input())
	answers.append((i, []))
	for j in range(a):
		(x, y) = [int(k) for k in input().split()]
		answers[i][1].append((x, y))

fix = True
while(fix):
	fix = False
	for i, ans in enumerate(answers):
		if lst[i] == False:
			continue
		for x, y in ans[1]:
			if y == 1 and lst[x - 1] == False:
				lst[i] = False
				fix = True
			if y == 0 and lst[x - 1] == True:
				lst[i] = False
				fix = True
print(sum(lst))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import itertools


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


def main():
    N = int(input())
    A = []
    X = [[] for _ in range(N)]
    Y = [[] for _ in range(N)]

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

    #    for i in itertools.product(range(2),repeat=N): ##大きい方からになっていない
    for i in range(N, 0, -1):  # 多い方から
        for honest in itertools.combinations(range(N), i):  # honest 正直者集合
            flag = 1
            for i in range(N):  # i::証言者
                if i not in honest:  # 嘘つきなら検索から外す
                    continue
                for j in range(A[i]):
                    x_temp = X[i][j]
                    y_temp = Y[i][j]

                    if y_temp == 1 and (x_temp not in honest):
                        flag = 0
                        break
                    if y_temp == 0 and (x_temp in honest):
                        flag = 0
                        break
                if flag == 0:
                    break
            if flag == 1:
                print(i)
                exit()

    print(0)

    pass


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import itertools


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


def main():
    N = int(input())
    A = []
    X = [[] for _ in range(N)]
    Y = [[] for _ in range(N)]

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

    #    for i in itertools.product(range(2),repeat=N): ##大きい方からになっていない
    for i in range(N, 0, -1):  # 多い方から
        for honest in itertools.combinations(range(N), i):  # honest 正直者集合
            flag = 1
            for i in range(N):  # i::証言者
                if i not in honest:  # 嘘つきなら検索から外す
                    continue
                for j in range(A[i]):
                    x_temp = X[i][j] -1
                    y_temp = Y[i][j]

                    if y_temp == 1 and (x_temp not in honest):
                        flag = 0
                        break
                    if y_temp == 0 and (x_temp in honest):
                        flag = 0
                        break
                if flag == 0:
                    break
            if flag == 1:
                print(i)
                exit()

    print(0)

    pass


if __name__ == "__main__":
    main()