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):
import math


def inputIntList():
    return [int(s) for s in input().split()]


def inputInt():
    return int(input())


def main():
    N = inputInt()
    xy = [[] for _ in range(N)]
    for i in range(N):
        A = inputInt()
        for _ in range(A):
            xy[i].append(inputIntList())
    ret = 0
    for i in range(2 ** N):
        state = [-1 for _ in range(N)]
        bit = format(i, "b").rjust(N, "0")
        for i, j in enumerate(bit):
            if j == "1":
                state[i] = 1
                for x, y in xy[i]:
                    if state[x - 1] == -1:
                        state[x - 1] = y
                    elif state[x - 1] != y:
                        break
                else:
                    # print(state)
                    continue
                break
        else:
            for i, s in enumerate(state):
                if s == 1:
                    for x, y in xy[i]:
                        if state[x - 1] != y:
                            break
                    else:
                        continue
                    break
            else:
                ret = max(ret, sum(state))
    return ret


if __name__ == "__main__":
    print(main())


import math


def inputIntList():
    return [int(s) for s in input().split()]


def inputInt():
    return int(input())


def main():
    N = inputInt()
    A = [[] for _ in range(N)]
    for i in range(N):
        for _ in range(inputInt()):
            A[i].append(inputIntList())
    ret = 0
    for i in range(2 ** N):
        bits = [i >> j & 1 for j in range(N)]
        for i, a in enumerate(A):
            if bits[i] == 0:
                continue
            for x, y in a:
                if bits[x - 1] == y:
                    continue
                break
            else:
                ret = max(ret, sum(bits))
    return ret


if __name__ == "__main__":
    print(main())


import math


def inputIntList():
    return [int(s) for s in input().split()]


def inputInt():
    return int(input())


def main():
    N = inputInt()
    A = [[] for _ in range(N)]
    for i in range(N):
        for _ in range(inputInt()):
            A[i].append(inputIntList())
    ret = 0
    for i in range(2 ** N):
        bits = [i >> j & 1 for j in range(N)]
        for i, a in enumerate(A):
            if bits[i] == 0:
                continue
            for x, y in a:
                # print(bits, bits[x - 1], y)
                if bits[x - 1] == y:
                    continue
                break
            else:
                continue
            break
        else:
            ret = max(ret, sum(bits))
    return ret


if __name__ == "__main__":
    print(main())


Verdicts: Wrong Answer

Wrong Answer

Accepted