Problem: 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?

Submission attempts (in order):
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)
    
    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]:
        
        #         val = False
        if not val:
            invalid.append(j)
    
    import itertools
    lst = list(itertools.product([0, 1], repeat=n))
    for string in lst:
        string = list(string)
        for j in invalid:
            string[j] = 0
        if list(set(honest) & set(dishonest)) == []:
            # print(string)
            ans = max(ans, string.count(1))
print(ans)

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)
ans = 0
for u in ret:
    i = ret[u]
    num = 1 + len(i[0])
    honest = [u] + i[0]
    not_honest = i[1]
    for p in i[0]:
        # print(p, ret[p])
        for h in ret[p][0]:
            honest.append(h)
        for d in ret[p][1]:
            not_honest.append(d)
    honest = list(set(honest))
    not_honest = list(set(not_honest))
    
    if list(set(honest) & set(not_honest)) == []:
        ans = max(ans, len(honest))
    for i in range(0, n):
        if i not in honest and i not in not_honest:
            t_honest, t_not_honest = [i], []
            for h in ret[i][0]:
                t_honest.append(h)
            for d in ret[i][1]:
                t_not_honest.append(d)
            t_honest = list(set(t_honest))
            t_not_honest = list(set(t_not_honest))
            if list(set(honest) & set(t_not_honest)) == []:
                honest = list(set(honest + t_honest))
                ans = max(ans, len(honest))
print(ans)


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())
        if y == 1:
            ret[i][0].append(x)
        elif y == 0:
            ret[i][1].append(x)
ans = 0
for u in ret:
    i = ret[u]
    num = 1 + len(i[0])
    honest = [u] + i[0]
    not_honest = i[1]
    for p in i[0]:
        if p not in ret:
            continue
        for h in ret[p][0]:
            honest.append(h)
        for d in ret[p][1]:
            not_honest.append(d)
    honest = list(set(honest))
    not_honest = list(set(not_honest))
    if list(set(honest) & set(not_honest)) == []:
        ans = max(ans, len(honest))
print(ans)


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)
    
    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]:
        
        #         val = False
        if not val:
            invalid.append(j)
    
    import itertools
    lst = list(itertools.product([0, 1], repeat=n))
    for string in lst:
        string = list(string)
        for j in invalid:
            string[j] = 0
        if list(set(honest) & set(dishonest)) == []:
            # print(string)
            ans = max(ans, string.count(1))
print(ans)

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)
 
ans = 0
import itertools
lst = list(itertools.product([0, 1], repeat=n))
for s in lst:
    var = True
    for i in range(len(s)):
        if s[i] == 1:
            for j in ret[i][0]:
                if s[j] != 1:
                    var = False
                    break
            for j in ret[i][1]:
                if s[j] != 0:
                    var = False
                    break
    if var:
        # print(s)
        ans = max(ans, s.count(1))
print(ans)

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted