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 numpy as np

N = int(input())
Axy = []
for i in range(N):
  j = []
  j.append(int(input()))
  k = [list(map(int,input().split())) for i in range(j[0])]
  j.append(k)
  Axy.append(j)
  
m = np.empty((N,N))
for i in range(N):
  n = np.full(N, 0)
  for j in range(len(Axy[i][1])):
    if Axy[i][1][j][1] == 1:
      n[Axy[i][1][j][0]-1] = Axy[i][1][j][1]
    elif Axy[i][1][j][1] == 0:
      n[Axy[i][1][j][0]-1] = -1
  m[i] = np.array(n)
  
M = np.dot(m, m)


S = []
for i in range(N):
  s = 0
  for j in range(N):
    s += M[i][j]
  S.append(s)
  
answer = 0
for i in range(N):
  if S[i] == 1:
    answer += 1

print(answer)

Submission status: Wrong Answer

Solution code:
N = int(input())

person = {}
for i in range(N+1)[1:]:
  A = int(input())
  argument = []
  subject = []
  for _ in range(A):
    tmp = str(input()).split(' ')
    argument.append(int(tmp[1]))
    subject.append(int(tmp[0]))
  person[i] = {'argument':argument, 'subject':subject}

max = 0
for key, value in person.items():
  dishonest = False
  possible = [key]
  for argument, subject in zip(value['argument'], value['subject']):
    if argument == 1:
      possible.append(subject)
  possibleset = set(possible)
  if len(possibleset) > 1:
    for cand in possible[1:]:
      for argument, subject in zip(person[cand]['argument'], person[cand]['subject']):
        if (argument == 1 and subject not in possible)\
        or (argument==0 and subject in possible):
          dishonest = True
          break
      if dishonest:
        break
    possible = set(possible)
    if not dishonest and len(possible) > max:
      max = len(possible)
  elif max == 0:
    max = 1

print(max)

Submission status: Wrong Answer

Solution code:
N = int(input())

person = {}
for i in range(N+1)[1:]:
  A = int(input())
  argument = []
  subject = []
  for _ in range(A):
    tmp = str(input()).split(' ')
    argument.append(int(tmp[1]))
    subject.append(int(tmp[0]))
  person[i] = {'argument':argument, 'subject':subject}

max = 0
for key, value in person.items():
  dishonest = False
  possible = [key]
  for argument, subject in zip(value['argument'], value['subject']):
    if argument == 1:
      possible.append(subject)
  if len(possible) > 1:
    for cand in possible[1:]:
      for argument, subject in zip(person[cand]['argument'], person[cand]['subject']):
        if (argument == 1 and subject not in possible)\
        or (argument==0 and subject in possible):
          dishonest = True
          break
      if dishonest:
        break
    if not dishonest and len(possible) > max:
      max = len(possible)
  
  elif max == 0:
    max = 1

print(max)

Submission status: Wrong Answer

Solution code:
import logging

logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.disable(logging.CRITICAL)

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

    A = []
    x = []
    y = []

    for i in range(N):
        Ai = int(input())
        xi = []
        yi = []
        A.append(Ai)
        x.append(xi)
        y.append(yi)

        for j in range(Ai):
            xij, yij = map(int, input().split(' '))
            xi.append(xij)
            yi.append(yij)

    logging.info(A)
    logging.info(x)
    logging.info(y)

    ok_list = [0]
    for bits in range(2 ** N):
        ok_flag = True
        for i in range(N):
            if (bits >> i) & 1 == 0:
                continue

            for j in range(A[i]):
                if (bits >> (x[i][j] - 1) & 1) != y[i][j]:
                    ok_flag = False

    if ok_flag:
        ok_list.append(bin(bits).count('1'))

    print(max(ok_list))

    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
ret = {}
for i in range(0, n):
    a = int(input())
    ret[i] = [[], []]
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        if y == 1:
            ret[i][0].append(x)
        elif y == 0:
            ret[i][1].append(x)
 
dic = {}
 
 
def f(honest_p):
    if honest_p in dic:
        return []
    dic[honest_p] = True
    # print('honest_list: ', honest_p)
    if ret[honest_p][0] == []:
        return [honest_p]
    temp = [honest_p]
    for i in ret[honest_p][0]:
        temp += f(i)
    return temp
 
 
ans = 0
invalida = []
for i in range(0, n):
    dic = {}
    honest = f(i)
    dishonest = ret[i][1]
    for a in honest:
        for b in ret[a][1]:
            if b not in dishonest:
                dishonest.append(b)
    if list(set(honest) & set(dishonest)) != []:
        invalida.append(i)

for i in range(0, n):
    if ret[i] == [[], []]:
        continue
    dic = {}
    honest = list(set(f(i)))
    # print('h', honest)
    dishonest = ret[i][1]
    for a in honest:
        for b in ret[a][1]:
            if b not in dishonest and b not in honest:
                dishonest.append(b)
    # print('d', dishonest)
    temp = []
    for a in honest:
        if a not in dishonest:
            temp.append(a)
    honest = temp
    invalid = []
    for j in range(0, n):
        if j not in honest and j not in dishonest:
            val = True
            for k in ret[j][0]:
                if k in dishonest:
                    val = False
                    break
            for k in ret[j][1]:
                if k in honest:
                    val = False
                    break
            if not val:
                invalid.append(j)
    import itertools
    lst = list(itertools.product([0, 1], repeat=n))
    for string in lst:
        val = True
        for t in honest:
            if string[t] != 1:
                val = False
                break
        for t in dishonest:
            if string[t] != 0:
                val = False
                break
        for t in invalid:
            if string[t] != 0:
                val = False
                break
        for t in invalida:
            if string[t] != 0:
                val = False
                break
        # print(string, honest, dishonest, invalid)    
        if val:
            # print(i, honest, dishonest, invalid, string)
            ans = max(ans, string.count(1))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ret = {}
for i in range(0, n):
    a = int(input())
    ret[i] = [[], []]
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        if y == 1:
            ret[i][0].append(x)
        elif y == 0:
            ret[i][1].append(x)
 
dic = {}
 
 
def f(honest_p):
    if honest_p in dic:
        return []
    dic[honest_p] = True
    # print('honest_list: ', honest_p)
    if ret[honest_p][0] == []:
        return [honest_p]
    temp = [honest_p]
    for i in ret[honest_p][0]:
        temp += f(i)
    return temp
 
 
ans = 0
for i in range(0, n):
    if ret[i] == [[], []]:
        continue
    dic = {}
    honest = list((f(i)))
    # print('h', honest)
    dishonest = ret[i][1]
    for a in honest:
        for b in ret[a][1]:
            if b not in dishonest and b not in honest:
                dishonest.append(b)
    # print('d', dishonest)
    temp = []
    for a in honest:
        if a not in dishonest:
            temp.append(a)
    honest = temp
    invalid = []
    for j in range(0, n):
        if j not in honest and j not in dishonest:
            val = True
            for k in ret[j][0]:
                if k in dishonest:
                    val = False
                    break
            for k in ret[j][1]:
                if k in honest:
                    val = False
                    break
            if not val:
                invalid.append(j)
    import itertools
    lst = list(itertools.product([0, 1], repeat=n))
    for string in lst:
        val = True
        for t in honest:
            if string[t] != 1:
                val = False
                break
        for t in dishonest:
            if string[t] != 0:
                val = False
                break
        for t in invalid:
            if string[t] != 0:
                val = False
                break
        # print(string, honest, dishonest, invalid)    
        if val:
            # print(i, honest, dishonest, invalid, string)
            ans = max(ans, string.count(1))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ret = {}
for i in range(0, n):
    a = int(input())
    ret[i] = [[], []]
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        if y == 1:
            ret[i][0].append(x)
        elif y == 0:
            ret[i][1].append(x)
 
dic = {}
 
 
def f(honest_p):
    if honest_p in dic:
        return []
    dic[honest_p] = True
    # print('honest_list: ', honest_p)
    if ret[honest_p][0] == []:
        return [honest_p]
    temp = [honest_p]
    for i in ret[honest_p][0]:
        temp += f(i)
    return temp
 
 
ans = 0
for i in range(0, n):
    if ret[i] == [[], []]:
        continue
    dic = {}
    honest = list((f(i)))
    # print('h', honest)
    dishonest = ret[i][1]
    for a in honest:
        for b in ret[a][1]:
            if b not in dishonest:
                dishonest.append(b)
    # print('d', dishonest)
    temp = []
    for a in honest:
        if a not in dishonest:
            temp.append(a)
    honest = temp
    invalid = []
    temp = []
    for a in dishonest:
        if a not in honest:
            temp.append(a)
    dishonest = temp
    invalid = []
    for j in range(0, n):
        if j not in honest and j not in dishonest:
            val = True
            for k in ret[j][0]:
                if k in dishonest:
                    val = False
                    break
            for k in ret[j][1]:
                if k in honest:
                    val = False
                    break
            if not val:
                invalid.append(j)
    import itertools
    lst = list(itertools.product([0, 1], repeat=n))
    for string in lst:
        val = True
        for t in honest:
            if string[t] != 1:
                val = False
                break
        for t in dishonest:
            if string[t] != 0:
                val = False
                break
        for t in invalid:
            if string[t] != 0:
                val = False
                break
        # print(string, honest, dishonest, invalid)    
        if val:
            # print(i, honest, dishonest, invalid, string)
            ans = max(ans, string.count(1))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ret = {}
for i in range(0, n):
    a = int(input())
    ret[i] = [[], []]
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        if y == 1:
            ret[i][0].append(x)
        elif y == 0:
            ret[i][1].append(x)
 
dic = {}
 
 
def f(honest_p):
    if honest_p in dic:
        return []
    dic[honest_p] = True
    # print('honest_list: ', honest_p)
    if ret[honest_p][0] == []:
        return [honest_p]
    temp = [honest_p]
    for i in ret[honest_p][0]:
        temp += f(i)
    return temp
 
 
ans = 0
for i in range(0, n):
    if ret[i] == [[], []]:
        continue
    dic = {}
    honest = list((f(i)))
    # print('h', honest)
    dishonest = ret[i][1]
    for a in honest:
        for b in ret[a][1]:
            if b not in dishonest:
                dishonest.append(b)
    # print('d', dishonest)
    temp = []
    for a in honest:
        if a not in dishonest:
            temp.append(a)
    honest = temp
    invalid = []
    for j in range(0, n):
        if j not in honest and j not in dishonest:
            val = True
            for k in ret[j][0]:
                if k in dishonest:
                    val = False
                    break
            for k in ret[j][1]:
                if k in honest:
                    val = False
                    break
            if not val:
                invalid.append(j)
    import itertools
    lst = list(itertools.product([0, 1], repeat=n))
    for string in lst:
        val = True
        for t in honest:
            if string[t] != 1:
                val = False
                break
        for t in dishonest:
            if string[t] != 0:
                val = False
                break
        for t in invalid:
            if string[t] != 0:
                val = False
                break
        # print(string, honest, dishonest, invalid)    
        if val:
            # print(i, honest, dishonest, invalid, string)
            ans = max(ans, string.count(1))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from pprint import pprint

def solve(n, info):
    ans = 0
    for i in range(2 ** n):
        true_info = {}
        p_info = {}
        for j in range(n):
            if ((i >> j) & 1):
                true_info[j] = info[j]
                for x, y in info[j]:
                    if y == 1:
                        true_info[x-1] = info[x-1]
                # pprint(info[j])
                p_info[j] = [1]
        # print("p_info")
        # pprint(p_info)
        # pprint(true_info.keys())
        flag = True
        for _, info_list in true_info.items():
            for x, y in info_list:
                if y == 0 and (x - 1) in p_info:
                    flag =False
                    break
            if not flag:
                break

        if flag:
            # pprint(true_info)
            ans = max(ans, len(p_info))

    print(ans)

if __name__ == '__main__':
    n = int(sys.stdin.readline().strip())
    info = []
    for i in range(n):
        a = int(sys.stdin.readline().strip())
        info.append([])
        for _ in range(a):
            x, y = map(int, sys.stdin.readline().strip().split(" "))
            info[i].append((x, y))
    
    # pprint(info)
    solve(n, info)

Submission status: Wrong Answer

Solution code:
n = int(input())
ret = {}
for i in range(0, n):
    a = int(input())
    ret[i] = [[], []]
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        if y == 1:
            ret[i][0].append(x)
        elif y == 0:
            ret[i][1].append(x)
 
dic = {}
 
 
def f(honest_p):
    if honest_p in dic:
        return []
    dic[honest_p] = True
    # print('honest_list: ', honest_p)
    if ret[honest_p][0] == []:
        return [honest_p]
    temp = [honest_p]
    for i in ret[honest_p][0]:
        temp += f(i)
    return temp
 
 
ans = 0
for i in range(0, n):
    if ret[i] == [[], []]:
        continue
    dic = {}
    honest = list((f(i)))
    # print('h', honest)
    dishonest = ret[i][1]
    for a in honest:
        for b in ret[a][1]:
            if b not in dishonest:
                dishonest.append(b)
    # print('d', dishonest)
    invalid = []
    for j in range(0, n):
        if j not in honest and j not in dishonest:
            val = True
            for k in ret[j][0]:
                if k in dishonest:
                    val = False
                    break
            for k in ret[j][1]:
                if k in honest:
                    val = False
                    break
            if not val:
                invalid.append(j)
    import itertools
    lst = list(itertools.product([0, 1], repeat=n))
    for string in lst:
        val = True
        for t in honest:
            if string[t] != 1:
                val = False
                break
        for t in dishonest:
            if string[t] != 0:
                val = False
                break
        for t in invalid:
            if string[t] != 0:
                val = False
                break
        if val:
            # print(i, honest, dishonest, invalid, string)
            ans = max(ans, string.count(1))
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
xy=[[] for i 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])

m=0
for i in range(2**(N-1)):
  f=True
  for j in range(N):
    if (i>>j)&1>0:
      for k in xy[j]:
        if (i>>k[0])&1!=k[1]:
          f=False
          break
    if f==False:
      break
  if f==True:
    c=0
    while i>0:
      c+= i&1
      i >>= 1
    m=max(m,c)
print(m)

Submission status: Wrong Answer

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

n = inp()
xy = [[] for i in range(n)]
for i in range(n):
    for j in range(inp()):
        a,b = inpl()
        xy[i].append([a,b])
# print(xy)
res = 0
for flag in itertools.product([0,1],repeat=n):
    cnt = 0
    theory = [-1]*n #-1:決まってない 0:不親切 1:正直
    f = True
    for i,j in enumerate(flag):
        if j:
            cnt += 1
        if theory[i] == -1:
            theory[i] = j
        elif theory[i] != j:
            f = False
            break
        for k in xy[i]:
            if theory[k[0]-1] == -1:
                theory[k[0]-1] = k[1]
            else:
                if j:
                    if theory[k[0]-1] != k[1]:
                        f = False
                        break
                else:
                    if theory[k[0]-1] == k[1]:
                        f = False
                        break
        if not f:
            break
    if not f:
        continue
    res = max(res,cnt)
print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
ret = {}
for i in range(0, n):
    a = int(input())
    ret[i] = [[], []]
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        if y == 1:
            ret[i][0].append(x)
        elif y == 0:
            ret[i][1].append(x)
 
dic = {}
 
 
def f(honest_p):
    if honest_p in dic:
        return []
    dic[honest_p] = True
    # print('honest_list: ', honest_p)
    if ret[honest_p][0] == []:
        return [honest_p]
    temp = [honest_p]
    for i in ret[honest_p][0]:
        temp += f(i)
    return temp
 
 
ans = 0
invalid = []
for i in range(0, n):
    dic = {}
    honest = f(i)
    dishonest = ret[i][1]
    for a in honest:
        for b in ret[a][1]:
            if b not in dishonest:
                dishonest.append(b)
    if list(set(honest) & set(dishonest)) != []:
        invalid.append(i)
#print(invalid)
for i in range(0, n):
    if ret[i] == [[],[]]:
        continue
    dic = {}
    honest = list((f(i)))
    # print('h', honest)
    dishonest = ret[i][1]
    for a in honest:
        for b in ret[a][1]:
            if b not in dishonest:
                dishonest.append(b)
    # print('d', dishonest)
    dishonest = list(set(dishonest))
    # print('invalid', invalid)
    string = [0] * n
    for j in honest:
        string[j] = 1
        # print(i, j)
    for j in range(n):
        if j not in invalid:
            string[j] = 1
    invalida = []
    for j in range(0, n):
        if i == j:
            continue
        val = True
        for k in ret[j][1]:
            if k in honest:
                val = False
        for k in ret[j][0]:
            if k in dishonest:
                val = False
        if not val:
            invalida.append(j)
    for j in invalida:
        string[j] = 0
    for j in dishonest:
        string[j] = 0
    if list(set(honest) & set(dishonest)) == []:
        # print(i, string, honest, dishonest)
        ans = max(ans, string.count(1))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
kind = []
unkind = []
f = 0
for _ in range(N):
    a = int(input())
    k = u = 0
    for _ in range(a):
        x, y = [int(_) for _ in input().split()]
        x -= 1
        if y:
            k += 2**x
            f = 1
        else:
            u += 2**x
    kind += [k]
    unkind += [u]
for ans in range(2**N - 1, -1, -1):
    k = 0
    u = 0
    for b in range(N):
        if (ans >> b) & 1:
            k |= kind[b]
            u |= unkind[b]
    if (k & ans) == ans and (u & ans) == 0:
        x = bin(ans).count('1')
        if not f:
            x = max(1, x)
        print(x)
        exit()

Submission status: Wrong Answer

Solution code:
n = int(input())
ret = {}
for i in range(0, n):
    a = int(input())
    ret[i] = [[], []]
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        if y == 1:
            ret[i][0].append(x)
        elif y == 0:
            ret[i][1].append(x)
 
dic = {}
 
 
def f(honest_p):
    if honest_p in dic:
        return []
    dic[honest_p] = True
    # print('honest_list: ', honest_p)
    if ret[honest_p][0] == []:
        return [honest_p]
    temp = [honest_p]
    for i in ret[honest_p][0]:
        temp += f(i)
    return temp
 
 
ans = 0
invalid = []
for i in range(0, n):
    dic = {}
    honest = f(i)
    dishonest = ret[i][1]
    for a in honest:
        for b in ret[a][1]:
            if b not in dishonest:
                dishonest.append(b)
    if list(set(honest) & set(dishonest)) != []:
        invalid.append(i)
#print(invalid)
for i in range(0, n):
    if ret[i] == [[],[]]:
        continue
    dic = {}
    honest = list((f(i)))
    # print('h', honest)
    dishonest = ret[i][1]
    for a in honest:
        for b in ret[a][1]:
            if b not in dishonest:
                dishonest.append(b)
    # print('d', dishonest)
    dishonest = list(set(dishonest))
    # print('invalid', invalid)
    string = [0] * n
    for j in honest:
        string[j] = 1
        # print(i, j)
    for j in range(n):
        if j not in invalid:
            string[j] = 1
    invalida = []
    for j in range(0, n):
        if i == j:
            continue
        val = True
        for k in ret[j][1]:
            if k in honest:
                val = False
        for k in ret[j][0]:
            if k in dishonest:
                val = False
        if not val:
            invalida.append(j)
    for j in invalida:
        string[j] = 0
    if list(set(honest) & set(dishonest)) == []:
        #print(i, string, honest, dishonest)
        ans = max(ans, string.count(1))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ret = {}
for i in range(0, n):
    a = int(input())
    ret[i] = [[], []]
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        if y == 1:
            ret[i][0].append(x)
        elif y == 0:
            ret[i][1].append(x)
 
dic = {}
 
 
def f(honest_p):
    if honest_p in dic:
        return []
    dic[honest_p] = True
    # print('honest_list: ', honest_p)
    if ret[honest_p][0] == []:
        return [honest_p]
    temp = [honest_p]
    for i in ret[honest_p][0]:
        temp += f(i)
    return temp
 
 
ans = 0
invalid = []
for i in range(0, n):
    dic = {}
    honest = f(i)
    dishonest = ret[i][1]
    for a in honest:
        for b in ret[a][1]:
            if b not in dishonest:
                dishonest.append(b)
    if list(set(honest) & set(dishonest)) != []:
        invalid.append(i)
#print(invalid)
for i in range(0, n):
    if ret[i] == [[],[]]:
        continue
    dic = {}
    honest = list((f(i)))
    # print('h', honest)
    dishonest = ret[i][1]
    for a in honest:
        for b in ret[a][1]:
            if b not in dishonest:
                dishonest.append(b)
    # print('d', dishonest)
    dishonest = list(set(dishonest))
    # print('invalid', invalid)
    string = [0] * n
    for j in honest:
        string[j] = 1
        # print(i, j)
    for j in range(n):
        if j not in invalid:
            string[j] = 1
    invalida = []
    for j in range(0, n):
        if i == j:
            continue
        val = True
        for k in ret[j][1]:
            if k in honest:
                val = False
        for k in ret[j][0]:
            if k in dishonest:
                val = False
        if not val:
            invalida.append(j)
    for j in invalida:
        string[j] = 0
    for j in dishonest:
        string[j] = 0
    if list(set(honest) & set(dishonest)) == []:
        #print(i, string, honest, dishonest)
        ans = max(ans, string.count(1))
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
xy=[[] for i 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])

m=0
f=True
for i in range(2**(N-1)):
  for j in range(N):
    if (i>>j)&1==0:
    	continue
    f=True
    for k in xy[j]:
      if (i>>k[0])&1!=k[1]:
        f=False
        break
    if f==False:
      break
  if f==False:
    continue
  c=0
  while i>0:
    if i&1>0:
      c+=1
      i = i>>1
  m=max(m,c)
print(m)

Submission status: Wrong Answer

Solution code:
n = int(input())
ret = {}
for i in range(0, n):
    a = int(input())
    ret[i] = [[], []]
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        if y == 1:
            ret[i][0].append(x)
        elif y == 0:
            ret[i][1].append(x)
 
dic = {}
 
 
def f(honest_p):
    if honest_p in dic:
        return []
    dic[honest_p] = True
    # print('honest_list: ', honest_p)
    if ret[honest_p][0] == []:
        return [honest_p]
    temp = [honest_p]
    for i in ret[honest_p][0]:
        temp += f(i)
    return temp
 
 
ans = 0
invalid = []
for i in range(0, n):
    dic = {}
    honest = f(i)
    dishonest = ret[i][1]
    for a in honest:
        for b in ret[a][1]:
            if b not in dishonest:
                dishonest.append(b)
    if list(set(honest) & set(dishonest)) != []:
        invalid.append(i)
#print(invalid)
for i in range(0, n):
    dic = {}
    honest = list((f(i)))
    # print('h', honest)
    dishonest = ret[i][1]
    for a in honest:
        for b in ret[a][1]:
            if b not in dishonest:
                dishonest.append(b)
    # print('d', dishonest)
    dishonest = list(set(dishonest))
    # print('invalid', invalid)
    string = [0] * n
    for j in honest:
        string[j] = 1
        # print(i, j)
    for j in range(n):
        if j not in invalid:
            string[j] = 1
    invalida = []
    for j in range(0, n):
        if i == j:
            continue
        val = True
        for k in ret[j][1]:
            if k in honest:
                val = False
        for k in ret[j][0]:
            if k in dishonest:
                val = False
        if not val:
            invalida.append(j)
    for j in invalida:
        string[j] = 0
    if list(set(honest) & set(dishonest)) == []:
        # print(i, string, honest, dishonest)
        ans = max(ans, string.count(1))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ret = {}
for i in range(0, n):
    a = int(input())
    ret[i] = [[], []]
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        if y == 1:
            ret[i][0].append(x)
        elif y == 0:
            ret[i][1].append(x)
 
dic = {}
 
 
def f(honest_p):
    if honest_p in dic:
        return []
    dic[honest_p] = True
    # print('honest_list: ', honest_p)
    if ret[honest_p][0] == []:
        return [honest_p]
    temp = [honest_p]
    for i in ret[honest_p][0]:
        temp += f(i)
    return temp
 
 
ans = 0
for i in range(0, n):
    dic = {}
    honest = list((f(i)))
    # print('h', honest)
    dishonest = ret[i][1]
    for a in honest:
        for b in ret[a][1]:
            if b not in dishonest:
                dishonest.append(b)
    # print('d', dishonest)
    dishonest = list(set(dishonest))
    invalid = []
    for j in range(0, n):
        if i == j:
            continue
        val = True
        for k in ret[j][1]:
            if k in honest:
                val = False
        for k in ret[j][0]:
            if k in dishonest:
                val = False
        if not val:
            invalid.append(j)
    # print('invalid', invalid)
    string = [0] * n
    for j in honest:
        string[j] = 1
        # print(i, j)
    if list(set(honest) & set(dishonest)) == []:
        # print(i, string, honest, dishonest)
        ans = max(ans, string.count(1))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ret = {}
for i in range(0, n):
    a = int(input())
    ret[i] = [[], []]
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        if y == 1:
            ret[i][0].append(x)
        elif y == 0:
            ret[i][1].append(x)
 
dic = {}
 
 
def f(honest_p):
    if honest_p in dic:
        return []
    dic[honest_p] = True
    # print('honest_list: ', honest_p)
    if ret[honest_p][0] == []:
        return [honest_p]
    temp = [honest_p]
    for i in ret[honest_p][0]:
        temp += f(i)
    return temp
 
 
ans = 0
for i in range(0, n):
    dic = {}
    honest = list((f(i)))
    # print('h', honest)
    dishonest = ret[i][1]
    for a in honest:
        for b in ret[a][1]:
            if b not in dishonest:
                dishonest.append(b)
    # print('d', dishonest)
    dishonest = list(set(dishonest))
    invalid = []
    for j in range(0, n):
        if i == j:
            continue
        val = True
        for k in ret[j][1]:
            if k in honest:
                val = False
        for k in ret[j][0]:
            if k in dishonest:
                val = False
        if not val:
            invalid.append(j)
    # print('invalid', invalid)
    import itertools
    lst = list(itertools.product([1], repeat=n))
    for string in lst:
        string = list(string)
        for j in dishonest:
            string[j] = 0
        for j in invalid:
            string[j] = 0
        if list(set(honest) & set(dishonest)) == []:
            # print(string)
            ans = max(ans, string.count(1))
print(ans)