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=[[-1]*15]*15
for i in range(n):
  a=int(input())
  if a:
    for j in range(a):
      x,y=map(int,input().split())
      x-=1
      test[i][x]=y
Num=[0]
for i in range(1,(2**n)):
  i=bin(i)
  s=str(i)
  s=list(s)
  s=s[2:]
  s.reverse()
  if (len(s))!=n:
    for i in range(n-len(s)):
      s.append('0')
  s.reverse()
  lst=[]
  Lst=[]
  for j in range(len(s)):
    t=s[j]
    lst.append(int(t))
  for k in range(n):
    if lst[k]:
      Lst.append(test[k])
  Lst_2=[[] for _ in range(n)]
  for N in range(15):
    for m in range(len(Lst)):
      Lst_2[m].append(Lst[m][N])
      Lst_2[m].append(-1)
  for I in range(len(Lst_2)):
      if len(set(Lst_2[I])-set([-1]))>1:
        break  
      if I==len(Lst_2)-1 and len(set(Lst_2[I])-set([-1]))<=1:
        Num.append(list(s).count('1'))
print(max(Num))

Submission status: Wrong Answer

Solution code:
#入力
n = int(input())
A = []
for i in range(n):
  A.append([])
  A[i].append(int(input()))
  for j in range(A[i][0]):
    A[i].append([int(_) for _ in input().split()])
    
def bit_count(num):
  cc = 0
  while num:
    cc += num & 1
    num >>= 1
  return cc

#bit全探索
res = 0
for bit in range(2 ** n):
  for i in range(n): #i番目の人の発言について検証
    z = ((bit >> i) & 1) ^ 1 #i番目の人が正直者かそうでないか
    for j in range(A[i][0]):
      x, y = A[i][j+1]
      if (bit >> (x-1)) & 1 != y ^ z:
        break
    else:
      continue
    break
  else:
    res = max(res, bit_count(bit))
print(res)

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

#0埋め　桁合わせ
def digit(n, r):
    n = str(n)
    l = len(n)
    for i in range(r - l):
        n = '0' + n
    return n

def solv(i):
    global honest, flag
    tmp = []
    for j in range(len(arr[i])):
        if honest[arr[i][j][0] - 1] - arr[i][j][1] >= 90:
            honest[arr[i][j][0] - 1] = arr[i][j][1]
            if arr[i][j][1]:
                tmp.append(arr[i][j][0] - 1)
        elif honest[arr[i][j][0] - 1] - arr[i][j][1] != 0:
            flag = False
            break
    if flag:
        for j in tmp:
            solv(j)

n = INT()
arr = []
for _ in range(n):
    a = INT()
    arr.append([LIST() for _ in range(a)])
ans = 0
for i in range(2 ** n):
    bitstr = digit(bin(i)[2:], n)
    bit = [int(i) for i in bitstr]
    honest = [100 for _ in range(n)]
    flag = True
    for j in range(n):
        if bit[j]:
            honest[j] = 1
            solv(j)
    debug(flag, bit, honest)
    if flag:
        ans = max(ans, honest.count(1))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

#0埋め　桁合わせ
def digit(n, r):
    n = str(n)
    l = len(n)
    for i in range(r - l):
        n = '0' + n
    return n

def solv(i):
    global honest, flag
    if honest[i] != 1:
        return 0
    for j in range(len(arr[i])):
        if honest[arr[i][j][0] - 1] - arr[i][j][1] >= 90:
            honest[arr[i][j][0] - 1] = arr[i][j][1]
            solv(arr[i][j][0] - 1)
        elif honest[arr[i][j][0] - 1] - arr[i][j][1] != 0:
            flag = False
            break
    return 0

n = INT()
arr = []
for _ in range(n):
    a = INT()
    arr.append([LIST() for _ in range(a)])
ans = 0
for i in range(2 ** n):
    bitstr = digit(bin(i)[2:], n)
    bit = [int(i) for i in bitstr]
    honest = [100 for _ in range(n)]
    flag = True
    for j in range(n):
        if bit[j]:
            honest[j] = 1
            solv(j)
    debug(flag, bit, honest)
    if flag:
        ans = max(ans, honest.count(1))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

#0埋め　桁合わせ
def digit(n, r):
    n = str(n)
    l = len(n)
    for i in range(r - l):
        n = '0' + n
    return n

def solv(i):
    global honest, flag
    if honest[i] == 0:
        return 0
    for j in range(len(arr[i])):
        if honest[arr[i][j][0] - 1] - arr[i][j][1] >= 90:
            honest[arr[i][j][0] - 1] = arr[i][j][1]
            solv(arr[i][j][0] - 1)
        elif honest[arr[i][j][0] - 1] - arr[i][j][1] != 0:
            flag = False
            break
    return 0

n = INT()
arr = []
for _ in range(n):
    a = INT()
    arr.append([LIST() for _ in range(a)])
ans = 0
for i in range(2 ** n):
    bitstr = digit(bin(i)[2:], n)
    bit = [int(i) for i in bitstr]
    honest = [100 for _ in range(n)]
    flag = True
    for j in range(n):
        if bit[j]:
            honest[j] = 1
            solv(j)
    debug(flag, bit, honest)
    if flag:
        ans = max(ans, honest.count(1))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

#0埋め　桁合わせ
def digit(n, r):
    n = str(n)
    l = len(n)
    for i in range(r - l):
        n = '0' + n
    return n

def solv(i):
    global honest, flag
    if bit[i] == 0 and honest[i] != 1:
        return 0
    for j in range(len(arr[i])):
        if honest[arr[i][j][0] - 1] - arr[i][j][1] >= 90:
            honest[arr[i][j][0] - 1] = arr[i][j][1]
            solv(arr[i][j][0] - 1)
        elif honest[arr[i][j][0] - 1] - arr[i][j][1] != 0:
            flag = False
            break
    return 0

n = INT()
arr = []
for _ in range(n):
    a = INT()
    arr.append([LIST() for _ in range(a)])
ans = 0
for i in range(2 ** n):
    bitstr = digit(bin(i)[2:], n)
    bit = [int(i) for i in bitstr]
    honest = [100 for _ in range(n)]
    flag = True
    for j in range(n):
        if bit[j]:
            honest[j] = 1
            solv(j)
    debug(flag, bit, honest)
    if flag:
        ans = max(ans, honest.count(1))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

#0埋め　桁合わせ
def digit(n, r):
    n = str(n)
    l = len(n)
    for i in range(r - l):
        n = '0' + n
    return n

def solv(i):
    global honest, flag
    if bit[i] == 0 and honest[i] != 1:
        return 0
    if bit[i]:
        honest[i] = 1
    for j in range(len(arr[i])):
        if arr[i][j][1] == 1 and honest[arr[i][j][0] - 1] == -1:
            honest[arr[i][j][0] - 1] = 1
            solv(arr[i][j][0] - 1)
        elif arr[i][j][1] == 0 and honest[arr[i][j][0] - 1] == -1:
            honest[arr[i][j][0] - 1] = 0
        elif arr[i][j][1] != honest[arr[i][j][0] - 1]:
            flag = True
            break

n = INT()
arr = []
for _ in range(n):
    a = INT()
    arr.append([LIST() for _ in range(a)])
ans = 0
for i in range(2 ** n):
    bitstr = digit(bin(i)[2:], n)
    bit = [int(i) for i in bitstr]
    honest = [-1 for _ in range(n)]
    flag = False
    for j in range(n):
        if bit[j]:
            solv(j)
    debug(flag, bit, honest)
    if not flag:
        ans = max(ans, honest.count(1))
print(ans)

Submission status: Wrong Answer

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

ans=0
for i in range(2**N):
    S=format(i,'b').zfill(N)
    flag=True
    for j in range(N):
        if S[j]=='1':
            for x,y in M[j]:
                if S[x-1]!=y:
                    flag=False
        else:
            for x,y in M[j]:
                if S[x-1]==y:
                    flag=False
    if flag:
        ans=max(ans,S.count('1'))
print(ans)

Submission status: Wrong Answer

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
#template
N = int(input())
A = [0]*N
says = [[-1]*(N+1) for _ in range(N+1)]
for i in range(N):
    A[i] = int(input())
    for j in range(A[i]):
        x,y = inputlist()
        says[i+1][x] = y

suma = sum(A)

ans = 0

for i in range(2**N):
    bn = bin(i)
    bn = bn[1:]
    if len(bn) < N+1:
        for s in range(N+1-len(bn)):
            bn+= '0'
    flag = True
    for x in range(1,N+1):
        if bn[x] == '1':
            for y in range(1,N+1):
                if says[x][y] == -1:
                    continue
                if says[x][y] != int(bn[y]):
                    flag = False
                    break

    if flag:
        bn = bn[1:]
        c = 0
        for i in range(N):
            if bn[i] == '1':
                c+=1
        ans = max(c,ans)

print(ans)

Submission status: Wrong Answer

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
#template
N = int(input())
A = [0]*N
says = [[-1]*(N+1) for _ in range(N+1)]
for i in range(N):
    A[i] = int(input())
    for j in range(A[i]):
        x,y = inputlist()
        says[i+1][x] = y

suma = sum(A)

ans = 0

for i in range(2**N):
    bn = bin(i)
    bn = bn[1:]
    if len(bn) < N+1:
        for s in range(N+1-len(bn)):
            bn+= '0'
    count = 0
    for x in range(1,N+1):
        if bn[x] == '1':
            for y in range(1,N+1):
                if says[x][y] == int(bn[y]):
                    count+=1
        if bn[x] == '0':
            for y in range(1,N+1):
                if says[x][y] != -1 and says[x][y] != int(bn[y]):
                    count +=1
    if count == suma:
        bn = bn[1:]
        c = 0
        for i in range(N):
            if bn[i] == '1':
                c+=1
        ans = max(c,ans)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
work = []
for i in range(n):
    a = int(input())
    work.append([list(map(int, input().split())) for i in range(a)])
result = 0
for i in range(2**n):
    state = bin(i)[2:].zfill(n)
    honest = []
    unkind = []
    for j in range(n):
        if state[j] == "0":
            unkind.append(j)
        else:
            honest.append(j)
    flag = True
    for human in honest:
        for x, y in work[human-1]:
            if y == 1 and x in unkind:
                flag = False
                break
            elif y == 0 and x in honest:
                flag = False
                break
        if not flag:
            break
    if flag:
        result = result if result>len(honest) else len(honest)
print(result)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
work = []
for i in range(n):
    a = int(input())
    work.append([list(map(int, input().split())) for i in range(a)])
result = 0
for i in range(n):
    count = 0
    d = deque([work[i]])
    honest = deque([i])
    unkind = deque()
    while len(d) > 0:
        human = d.popleft()
        for x, y in human:
            if y == 1:
                if x not in honest:
                    d.append(work[x-1])
                    honest.append(x)
            else:
                if x not in unkind:
                    unkind.append(x)
    finish = False
    while not finish:
        finish = True
        for i in range(1, n+1):
            if i not in honest and i not in unkind:
                flag = True
                for x, y in work[i-1]:
                    if y == 1 and x in unkind:
                        flag = False
                        finish = False
                        break
                    elif y == 0 and x in honest:
                        flag = False
                        finish = False
                        break
                    elif x not in honest and x not in unkind:
                        flag = -1
                        break
                    else:
                        finish = False
                if flag:
                    honest.append(i)
                elif not flag:
                    unkind.append(i)
    if len(set(honest) & set(unkind)) == 0:
        count = n - len(unkind)
        result = result if result > count else count
print(result)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
work = []
for i in range(n):
    a = int(input())
    work.append([list(map(int, input().split())) for i in range(a)])
result = 0
for i in range(n):
    count = 0
    d = deque([work[i]])
    honest = deque([i])
    unkind = deque()
    while len(d) > 0:
        human = d.popleft()
        for x, y in human:
            if y == 1:
                if x not in honest:
                    d.append(work[x-1])
                    honest.append(x)
            else:
                if x not in unkind:
                    unkind.append(x)
    finish = False
    while not finish:
        finish = True
        for i in range(1, n+1):
            if i not in honest and i not in unkind:
                flag = True
                for x, y in work[i-1]:
                    if y == 1 and x in unkind:
                        flag = False
                        break
                    elif y == 0 and x in honest:
                        flag = False
                        break
                    elif x not in honest and x not in unkind:
                        finish = False
                        flag = -1
                        break
                if flag:
                    honest.append(i)
                elif not flag:
                    unkind.append(i)
    if len(set(honest) & set(unkind)) == 0:
        count = n - len(unkind)
        result = result if result > count else count
print(result)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
work = []
for i in range(n):
    a = int(input())
    work.append([list(map(int, input().split())) for i in range(a)])
result = 0
for i in range(n):
    count = 0
    d = deque([work[i]])
    honest = deque([i])
    unkind = deque()
    while len(d) > 0:
        human = d.popleft()
        for x, y in human:
            if y == 1:
                if x not in honest:
                    d.append(work[x-1])
                    honest.append(x)
            else:
                if x not in unkind:
                    unkind.append(x)
    finish = False
    while not finish:
        finish = True
        for i in range(1, n+1):
            if i not in honest and i not in unkind:
                flag = True
                for x, y in work[i-1]:
                    if y == 1 and x in unkind:
                        flag = False
                        break
                    elif y == 0 and x in honest:
                        flag = False
                        break
                    elif x not in honest and x not in unkind:
                        finish = False
                if flag:
                    honest.append(i)
                else:
                    unkind.append(i)
    if len(set(honest) & set(unkind)) == 0:
        count = n - len(unkind)
        result = result if result > count else count
print(result)

Submission status: Wrong Answer

Solution code:
import math

if __name__ == '__main__':
    n = int(input())
    ans = 0
    is_honest = [-1] * n
    evidence = []
    for i in range(n):
        a = int(input())
        tmp = []
        for j in range(a):
            x, y = map(int, input().split())
            tmp.append((x - 1, y))
        evidence.append(tmp)

    # 1 -> Honest, 0 -> Liar
    for i in range(2 ** n):
        flag = True
        for j in range(n):
            # j is Liar
            if not (i & (1 << j)):
                continue
            for x, y in evidence[j]:
                if y == 1 and not (i & (1 << x)):
                    flag = False
                elif y == 0 and (i & (1 << x)):
                    flag = False
        if flag:
            print(bin(i))
            count = 0
            for k in range(n):
                if i & (1 << k):
                    count += 1
            ans = max(ans, count)

    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools

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

a = np.array(list(itertools.product([0, 1], repeat=n)), dtype=np.bool)
for i, x, y in info:
    bl = (~a[:, i]) | (a[:, x] == bool(y))
    print(bl)
    a = a[bl]

ans = a.sum(axis=1).max()
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())


def make_remark_list(i, r):
    # -1: 不明, 0: 嘘つき, 1: 真実
    people = [-1] * n
    people[i] = 1
    for x, y in r:
        people[x - 1] = y
    return people


def check(x, y):
    new_list = []
    for a, b in zip(x, y):
        a, b = min(a, b), max(a, b)
        if (a, b) == (0, 1):
            return False
        elif (a, b) == (-1, 0):
            new_list.append(0)
        else:
            new_list.append(max(a, b))
    return new_list


remarks = []
for i in range(n):
    a = int(input())
    r = [tuple(map(int, input().split())) for _ in range(a)]
    remarks.append(make_remark_list(i, r))
print(remarks)

def max_count(r, cnt, i = 0):
    tmp = r
    for j, r_j in enumerate(remarks):
        if j < i: continue
        if tmp[j] == 0:
            continue
        elif tmp[j] == 1:
            if check(tmp, r_j):
                tmp = check(tmp, r_j)
                cnt += 1
            else:
                cnt = 0
                break
        else:
            tmp[j] = 1
            if check(tmp, r_j):
                cnt_1, tmp_1 = max_count(tmp, cnt, j)
                tmp[j] = 0
                cnt_0, tmp_0 = max_count(tmp, cnt, j)
                if cnt_0 > cnt_1:
                    return cnt_0, tmp_0
                else:
                    return cnt_1, tmp_1
            else:
                tmp[j] = 0
    return cnt, tmp

r = [-1] * n
cnt, r = max_count(r, 0)
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [0]*N
relation = []
for i in range(N):
    tmp = []
    A[i] = int(input())
    for j in range(A[i]):
        tmp.append(list(map(int, input().split())))
    relation.append(tmp)

ans = 0

for i in range(1<<N):
    cond = [0]*N

    for j in range(N):
        if 1&(i>>j):  # 右シフトして論理積（bit全探索）
            cond[j] = 1

    stop_flag = False
    mujun = False
    for i, p in enumerate(cond):
        # 不親切の場合は嘘でも本当でも良いので判定なし
        # 親切のbitが立っていた場合、判定あり
        if p:
            for k in range(A[j]):
                if cond[relation[j][k][0]-1] != relation[j][k][1]:
                    mujun = True
                    stop_flag = True
                    break

        if stop_flag:
            break

    if not mujun:
        ans = max(ans, sum(cond))

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
path = []
ans = 0
for i in range(N):
    A = int(input())
    path.append([])
    for j in range(A):
        x, y = map(int,input().split())
        x -= 1
        path[-1].append((x, y))
for i in range(1<<N):
    i |= (1<<N)
    judge = True
    for j in range(N):
        if (1<<j) & i:
            for k in range(len(path[j])):
                if path[j][k][1] != int(bin(i)[-path[j][k][0] - 1]):
                    judge = False
        else:
            for k in range(len(path[j])):
                if path[j][k][1] == int(bin(i)[-path[j][k][0] - 1]):
                    judge = False
    if judge:
        if ans < bin(i).count("1") - 1:
            ans = bin(i).count("1") - 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
path = []
ans = 0
for i in range(N):
    A = int(input())
    path.append([])
    for j in range(A):
        x, y = map(int,input().split())
        x -= 1
        path[-1].append((x, y))
for i in range(1<<N):
    i |= (1<<(N + 1))
    judge = True
    for j in range(N):
        if (1<<j) & i:
            for k in range(len(path[j])):
                if path[j][k][1] != int(bin(i)[-path[j][k][0] - 1]):
                    judge = False
        else:
            for k in range(len(path[j])):
                if path[j][k][1] == int(bin(i)[-path[j][k][0] - 1]):
                    judge = False
    if judge:
        if ans < bin(i).count("1") - 1:
            ans = bin(i).count("1") - 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
test_list = [[[int(i) for i in input().split()] for j in range(int(input()))] for k in range(n)]
    
man_list = [[int(j) for j in bin(i)[2:].zfill(n)] for i in range(2**n)]
     
ans = 0
bad = 0
     
for man in man_list:
    for j in range(n):
        if man[j] == 1:
          for k in test_list[j]:
            x = k[0] - 1
            y = k[1]
            if man[x] != y:
              bad = 1
              break
        if bad == 1:
          bad = 0
          break
        else:
            ans = max(ans, sum(man))
     
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
test_list = [[[int(i) for i in input().split()] for j in range(int(input()))] for k in range(n)]
    
man_list = [[int(j) for j in bin(i)[2:].zfill(n)] for i in range(2**n)]
     
ans = 0
bad = 0
     
for man in man_list:
    for j in range(n):
        if man[j] == 1:
          for k in test_list[j]:
            x = k[0] - 1
            y = k[1]
            if man[x] != y:
              bad = 1
              break
        if bad == 1:
          bad = 0
          break
    else:
        ans = max(ans, sum(man))
     
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

def trust_remark(i, r):
    # -1: 不明, 0: 嘘つき, 1: 真実
    people = [-1] * n
    people[i] = 1
    for x, y in r:
        people[x - 1] = y
    return people

def check(x, y):
    new_list = []
    for a, b in zip(x, y):
        if abs(a) != abs(b):
            return False
        else:
            new_list.append(max(a, b))
    return new_list

remarks = []
for i in range(n):
    a = int(input())
    r = [tuple(map(int, input().split())) for _ in range(a)]
    remarks.append(trust_remark(i, r))

dp = []
cnt_max = 0
for i, r_i in enumerate(remarks):
    if i in dp: continue
    cnt = 0
    tmp = [0] * i + r_i[i:]
    for j, r_j in enumerate(remarks[i:]):
        j += i
        if tmp[j] == 0: continue
        if check(tmp, r_j):
            tmp = check(tmp, r_j)
            cnt += 1
        elif r_i[j] == -1:
            tmp[j] = 0
            continue
        else:
            cnt = 0
            break
    if cnt != 0:
        for j, x in enumerate(tmp):
            if x == 1: dp.append(j)
    cnt_max = max(cnt, cnt_max)

print(cnt_max)

Submission status: Wrong Answer

Solution code:
n = int(input())

def trust_remark(i, r):
    # -1: 不明, 0: 嘘つき, 1: 真実
    people = [-1] * n
    people[i] = 1
    for x, y in r:
        people[x - 1] = y
    return people

def check(x, y):
    new_list = []
    for a, b in zip(x, y):
        if abs(a) != abs(b):
            return False
        else:
            new_list.append(max(a, b))
    return new_list

remarks = []
for i in range(n):
    a = int(input())
    r = [tuple(map(int, input().split())) for _ in range(a)]
    remarks.append(trust_remark(i, r))

dp = []
cnt_max = 0
for i, r_i in enumerate(remarks):
    # if i in dp: continue
    cnt = 0
    tmp = [0] * i + r_i[i:]
    for j, r_j in enumerate(remarks[i:]):
        j += i
        if r_i[j] == 0: continue
        if check(tmp, r_j):
            tmp = check(tmp, r_j)
            cnt += 1
        elif r_i[j] == -1:
            tmp[j] = 0
            continue
        else:
            cnt = 0
            break
    # if cnt != 0:
        # for j, x in enumerate(tmp):
            # if x == 1: dp.append(j)
    cnt_max = max(cnt, cnt_max)

print(cnt_max)

Submission status: Wrong Answer

Solution code:
n = int(input())

def trust_remark(i, r):
    # -1: 不明, 0: 嘘つき, 1: 真実
    people = [-1] * n
    people[i] = 1
    for x, y in r:
        people[x - 1] = y
    return people

def check(x, y):
    new_list = []
    for a, b in zip(x, y):
        if abs(a) != abs(b):
            return False
        else:
            new_list.append(max(a, b))
    return new_list

remarks = []
for i in range(n):
    a = int(input())
    r = [tuple(map(int, input().split())) for _ in range(a)]
    remarks.append(trust_remark(i, r))

dp = []
cnt_max = 0
for i, r_i in enumerate(remarks):
    if i in dp: continue
    cnt = 0
    tmp = [0] * i + r_i[i:]
    for j, r_j in enumerate(remarks[i:]):
        j += i
        if r_i[j] == 0: continue
        if check(tmp, r_j):
            tmp = check(tmp, r_j)
            cnt += 1
        elif r_i[j] == -1:
            tmp[j] = 0
            continue
        else:
            cnt = 0
            break
    if cnt != 0:
        for j, x in enumerate(tmp):
            if x == 1: dp.append(j)
        cnt_max = max(cnt, cnt_max)

print(cnt_max)