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: Accepted

Solution code:
#C
n = int(input())
a = []
testimony = [-1]*n
ans = 0
for i in range(n):
    a.append(int(input()))#証言の個数
    l = []
    for j in range(a[i]):
        l.append(list(map(int, input().split())))
    if l != []:
        testimony[i] = l#iの人のa[i]個の証言のリスト
for i in range(2**n):
    for j in range(n):
        if (i >> j) & 1 and testimony[n-1-j] != -1:
            for k in range(a[n-1-j]):
                if ((i >> (n - testimony[n-1-j][k][0])) & 1) != testimony[n-1-j][k][1]:
                    break
            else:
                continue
            break
    else:
        ans = max(ans, str(bin(i)).count('1'))
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from heapq import heapify, heappop, heappush
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

# ここから書き始める
n = int(input())
t = [[] for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        t[i].append([x, y])
ans = 0
for i in range(1 << n):
    bit = bin(i)[2:].zfill(n)
    ok = True
    for j in range(n):
        if bit[j] == "1":
            for k in t[j]:
                x = k[0]
                y = k[1]
                if bit[x] != str(y):
                    ok = False
                    break
        if not ok:
            break
    if ok:
        ans = max(ans, bit.count("1"))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
testimony = [[None for _ in range(N)] for _ in range(N)]
person = [None] * N

for i in range(N):
    person[i] = int(input())
    for _ in range(person[i]):
        j, good_or_bad = map(int, input().split())
        j -= 1
        testimony[i][j] = good_or_bad

ans = 0
for i in range(1, 1<<N):
    which_person = [None] * N
    for j in range(N):
        which_person[j] = i>>j & 1
    ok = True
    for j in range(N):
        if(which_person[j]): 
            for k in range(N):
                if testimony[j][k] == None: 
                    continue
                if testimony[j][k] != which_person[k]:
                    ok = False
    if ok:
        ans = max(ans, which_person.count(1))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
x = []
y = []
words = []
for i in range(N):
  A = int(input())
  W = []
  for _ in range(A):
    x, y = map(int, input().split())
    W.append([x-1, y])
  words.append(W)
  
ans = 0
for bit in range(1<<N):
  ok = True
  is_honest = [(bit>>i) & 1 for i in range(N)]
  for i in range(N):
    if not is_honest[i]:
      continue
    for x, y in words[i]:
      if is_honest[x] != y:
        ok = False
  if ok:
    ans = max(ans, sum(is_honest))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [0]*n
x = []
y = []
aa = 0
for i in range(n):
    a[i] = int(input())
    for j in range(a[i]):
        b,c = map(int,input().split())
        x.append(b)
        y.append(c)

for i in range(2**n):
    sw = [0]*n
    for j in range(n):
        if (i >> j) & 1:
            sw[j] = 1
    s = 0
    q = 1
    for j in range(n):
        if sw[j] == 1:
            for k in range(a[j]):
                if sw[x[s]-1] != y[s]:
                    q = 0
                    break
                s += 1
        else:
            s += a[j]

    if q == 1:
        su = sum(sw)
        aa = max(aa,su)
print(aa)

Submission status: Accepted

Solution code:
n=int(input())
xy=[[] for i in range(n)]
ans=0
a=[0]*n
for i in range(n):
  a[i]=int(input())
  for j in range(a[i]):
    x,y=map(int,input().split())
    xy[i].append([x,y])
for i in range(2**n):
  temp=[0]*n
  for j in range(n):
    if ((i >> j) & 1):
      temp[j]=1
  count=True
  for j in range(n):
    for k in range(a[j]):
      if temp[j]==1:
        p=xy[j][k][0]-1
        if temp[p]!=xy[j][k][1]:
          count=False
          break
  if count==True:
    ans=max(ans,sum(temp))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = []
lis = [[] for _ in range(n)]
for i in range(n):
    inp = int(input())
    a.append(inp)
    for j in range(inp):
        x, y = map(int, input().split())
        x -= 1
        lis[i].append([x,y])
ans = 0
for i in range(2**n):
    true = []
    now = 0
    for j in range(n):
        if (i >> j) & 1:
            true.append(1)
            now += 1
        else:
            true.append(0)
    flag = False
    for j in range(n):
        if true[j] == 1:
            for xys in lis[j]:
                x = xys[0]
                y = xys[1]
                if true[x] != y:
                    flag = True
                if flag:
                    break
        if flag:
            break
    if not flag:
        ans = max(ans, now)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def count_ones(num):
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count


def main():
    N = int(readline())
    X = []
    for i in range(N):
        A = int(readline())
        tmp = []
        for _ in range(A):
            tmp.append(tuple(map(int, readline().split())))
        X.append(tmp)

    ans = 0
    for i in range(2**N):
        OK = True
        for j in range(N):
            if ((i >> j) & 1):
                for x in X[j]:
                    if ((i >> (x[0] - 1)) & 1) != x[1]:
                        OK = False
                        break
                if not OK:
                    break
        if OK:
            ans = max(ans, count_ones(i))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = [[-1 for i in range(N)] for j in range(N)]

for i in range(N):
  A = int(input())
  for a in range(A):
    x, y = map(int, input().split())
    S[i][x - 1] = y
ans = 0
for i in range(2**N):
  H = [0 for _ in range(N)]
  for _ in range(N):
    if i>>_ &1:
      H[_] = 1
  f = True
  for j in range(N):
    if H[j]:
      for k in range(N):
        if S[j][k] == -1:
          continue
        elif S[j][k] != H[k]:
          f = False
  if f:
    ans = max(ans, H.count(1))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
xy=[[]for _ in range(n)]
for i in range(n):
  a=int(input())
  xy[i]=[list(map(int,input().split())) for _ in range(a)]
ans=0
for i in range(pow(2,n)):
  honest=[]
  for j in range(n):
    if ((i>>j)&1):
      honest.append(1)
    else:
      honest.append(0)
  n_honest=sum(honest)
  if n_honest<=ans:
    continue
  flg=True
  for k in range(n):
    if honest[k]==1:
      for x,y in xy[k]:
        if honest[x-1]==y:
          pass
        else:
          flg=False
          break
    if flg==False:
      break
  if flg:
    ans=n_honest
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
xy = [[-1 for i in range(N)] for j in range(N)]
for i in range(N):
    for j in range(int(input())):
        x, y = map(int, input().split())
        xy[i][x-1] = y

ans = -1
for tf in range((1 << N)):
    
    ls = [0 for i in range(N)]
    for i in range(N):
        if 1 & (tf >> i):
            ls[i] = 1

    can = True
    for j in range(N):
        if ls[j] == 1:
            for k in range(N):
                if xy[j][k] == -1: continue
                if xy[j][k] != ls[k]: can = False

    if can: ans = max(ans, ls.count(1))

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools

input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    A = [[] for _ in range(N)]
    for i in range(N):
        ai = int(input())
        for j in range(ai):
            x, y = map(int, input().split())
            A[i].append((x - 1, y))

    honest = list(itertools.product([0, 1], repeat=N))
    ans = 0

    # print(honest)
    # print(A)

    for h in honest:
        h_list = list(h)
        f = True
        for i, ai in enumerate(h):
            if not f:
                break
            if ai == 0:
                continue
            for x, y in A[i]:
                if h_list[x] == y:
                    #print("OK", i, x, y)
                    continue
                else:
                    f = False
                    #print("NO", i, x, y)
                    break

        if f:
            ans = max(ans, sum(h_list))

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N = int(input())
stmt = [[] for _ in range(N + 1)]
for j in range(1, N + 1):
    a = int(input())
    stmt[j] = [tuple(int(x) for x in input().split()) for _ in range(a)]

ans = 0
for i in range(2 ** N):
    S = "{:0{haba}b}".format(i, haba = N + 1)
    n = S.count("1")  # 正直者の数
    for j in range(1, N + 1):   # すべての人について
        if int(S[j]) == 0:  continue # 人jは不親切
        # 人jは正直者
        for (who, ishonest) in stmt[j]: # 証言チェック
            if int(S[who]) != ishonest:  # 証言と異なる
                break
        else:   # 人jの証言は問題ない
            continue    # 次の人の証言チェックへ
        break
    else:
        ans = max(ans, n)

print(ans)

Submission status: Accepted

Solution code:
def main():
    from itertools import product

    N = int(input())

    g = []
    for _ in range(N):
        a = int(input())
        t = []
        for _ in range(a):
            x, y = map(int, input().split())
            t.append((x - 1, y))
        g.append(t)

    def is_ok(prd):
        for j, bl in enumerate(prd):
            if bl:
                for x, y in g[j]:
                    if prd[x] != y:
                        return False
        return True

    ans = 0
    for prd in product([0, 1], repeat=N):
        if is_ok(prd):
            ans = max(ans, prd.count(1))
    print(ans)


if __name__ == '__main__':
    main()

# bit演算しようとしてはまった

Submission status: Accepted

Solution code:
def main():
    from itertools import product

    N = int(input())

    g = []
    for _ in range(N):
        a = int(input())
        t = []
        for _ in range(a):
            x, y = map(int, input().split())
            x -= 1
            t.append((x, y))
        g.append(t)

    def is_ok(prd):
        for j, bl in enumerate(prd):
            if bl:
                for x, y in g[j]:
                    if prd[x] != y:
                        return False
        return True

    ans = 0
    for prd in product([0, 1], repeat=N):
        *prd, = prd  # list化
        if is_ok(prd):
            ans = max(ans, prd.count(1))
    print(ans)


if __name__ == '__main__':
    main()

# bit演算しようとしてはまった

Submission status: Accepted

Solution code:
import itertools

n = int(input())
persons = list(itertools.product([0, 1], repeat=n))
testimony = [[] for _ in range(n)]


for i in range(n):
    num = int(input())
    for j in range(num):
        person, state = map(int, input().split())
        testimony[i].append([person-1, state])

honest = 0
for i in range(1, 2**n):
    flag = 0
    for j in range(n):
        if (i>>j)&1 == 1:
            for x, y in testimony[j]:
                if (i>>x)&1 != y:
                    flag = 1
                    break
    if flag == 0:
        honest = max(honest, bin(i)[1:].count('1'))
print(honest)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    xy = []
    for _ in range(n):
        ai = int(input())
        xyi = [list(map(int, input().split())) for _ in range(ai)]
        xy.append(xyi)

    ans = 0
    flag = False

    for i in range(1 << n):
        for j in range(n):
            if i & (1 << j):
                for x, y in xy[j]:
                    if y == 1:
                        if not i & (1 << (x - 1)):
                            flag = True
                    if y == 0:
                        if i & (1 << (x - 1)):
                            flag = True
        if not flag:
            tmp = 0
            for j in range(n):
                if i & (1 << j):
                    tmp += 1
            if ans < tmp:
                ans = tmp
        flag = False

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
N = int(input())
evi = [[] for _ in range(N)]
ans = 0
for i in range(N):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        evi[i].append((x,y))

for i in range(1 << N):
    count = 0
    flag = True
    for j in range(N):
        if (i >> j) & 1 == 1:
            count += 1
            for x,y in evi[j]:
                if (i >> x-1) & 1 != y:
                    flag = False
                    break
            if flag == False:
                break
    if flag:
        if ans < count:
            ans = count
print(ans)

Submission status: Accepted

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

b=[] #全部の可能性
for i in range(2**n):
    temp=[]
    for j in range(n):
        if (i>>j)&1==1:
            temp.append(1)
        else:
            temp.append(0)
    b.append(temp)
    
ans=[]
for c in b:
    flag=True
    for i in range(n):
        if flag==True:
            if c[i]==1:
                for k in range(len(xy[i])):
                    if c[xy[i][k][0]]!=xy[i][k][1]:
                        flag=False
                        break
        if i==n-1 and flag==True:
            ans.append(c.count(1))
print(max(ans))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
x = []
y = []
for i in range(N):
    Ai = int(input())
    xi = []
    yi = []
    for j in range(Ai):
        xij, yij = map(int, input().split())
        xi.append(xij)
        yi.append(yij)
    x.append(xi)
    y.append(yi)

ans = 0
for i in range(2**N):
    bit = [i>>j&1 for j in range(N)]
    flag = True
    for j in range(N):
        if bit[j] == 0:
            continue
        for k in range(len(x[j])):
            if not bit[x[j][k] - 1] == y[j][k]:
                flag = False
    if flag:
        ans = max(ans, sum(bit))

print(ans)

Submission status: Accepted

Solution code:
import sys
N=int(input())
data = [[] for _ in range(N)]
for i in range(N):
  cnt = int(input())
  for _ in range(cnt):
    x,y=map(int,sys.stdin.readline().rstrip().split())
    data[i].append((x-1,y))
res = 0
for bit in range(1 << N):
  count = 0
  flag = True
  for i in range(N):
    if bit & (1 << i):
      count += 1
      for xy in data[i]:
        x, y = xy
        if y ==1 and (not(bit & (1 << x))):
          flag = False
          break
        if y == 0 and (bit & (1 << x)):
          flag = False
          break
    if not flag:
      break
  if flag:
    res = max(res, count)
print(res)

Submission status: Accepted

Solution code:
n=int(input())

xy=[[] for i in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        xx,yy=list(map(int,input().split()))
        xy[i].append([xx-1,yy])


ans=[0]
for ii in range(2**n): #1 is honest

    i=bin(ii)[2:].zfill(n)
    ok=True
    for nin in range(n):
        if int(i[-nin])==1:
            for x,y in xy[nin]:
                if y!=int(i[-x]):
                    ok=False
                    break
            if not ok:break
    if ok:
        ans.append(i.count('1'))
print(max(ans))

Submission status: Accepted

Solution code:
N = int(input())

T= [[-1]*N for i in range(N)]
for i in range(N):
    A = int(input())
    for j in range(A):
        X,Y = list(map(int,input().split()))
        T[i][X-1] = Y

import itertools
cases = list(itertools.product([0,1], repeat=N))

out = []
for case in cases:
    flag = 0
    for i in range(N):
        if case[i]==1:
            ops = T[i]
            for j in range(N):
                if ops[j]!=-1 and ops[j]!=case[j]:
                    flag = 1
    if flag==0:
        out.append(sum(case))

print(max(out))

Submission status: Accepted

Solution code:
n = int(input())
mp = [[] for i in range(n)]
for i in range(n):
    m = mp[i]
    a = int(input())
    for j in range(a):
        m.append(list(map(int,input().split())))

ans = 0
maxc = 2**n
cnt = 0
while(cnt < maxc):
    isOK = True
    
    for i in range(n):
        if(1 & cnt>>i):
            #i番目の人の証言が正しいと仮定する
            for x,y in mp[i]:
                if(y == 1):
                    if(1 & cnt>>(x-1)):
                        continue
                else:
                    if(not (0 | (cnt>>(x-1) & 1) )):
                        continue
                #print(bin(cnt),x,y,' ',bin(cnt>>(x-1)))
                isOK = False
    
    if isOK:
        num = str(bin(cnt)).count('1')
        
        if ans < num:
            ans = num
    
    cnt += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xy = []
for _ in range(n):
  a = int(input())
  xy.append([[int(i) for i in input().split()] for __ in range(a)])

ans = 0
for i in range(2**n):
  flag = True
  for j in range(n):
    if i >> j & 1:
      for x,y in xy[j]:
        if (i >> (x-1)&1) != y:
          flag = False
          break
  if flag:
    ans = max(ans, sum(map(int, bin(i)[2:])))
print(ans)

Submission status: Accepted

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n): return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
import itertools
# import math
# import networkx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop

n=n0()
X=[]
for i in range(n):
    a=n0()
    x=n3(a)
    X.append(x)

ite=list(itertools.product([0,1],repeat=n))
ite.sort(key=lambda x:sum(x),reverse=True)

s=0
for line in ite[:-1]:
    ans=[i for i in line]
    flag=True
#     print(line)
    for i in range(n):
        if line[i]==1:
            for a,b in X[i]:
#                 print(ans[a-1],a,b)
                if ans[a-1]!=b:
                    flag=False
                    break
            if flag==False:
                break
    if flag==True:
        for j in range(n):
            if ans[j]==1:
                if line[j]!=1:
                    break
        else:
            s=sum(line)
            break
print(s)

Submission status: Accepted

Solution code:
n = int(input())
xy = []
for _ in range(n):
  a = int(input())
  xy.append([[int(i) for i in input().split()] for __ in range(a)])

ans = 0
for i in range(2**n):
  flag = True
  for j in range(n):
    if i >> j & 1:
      for x,y in xy[j]:
        if (i >> (x-1)&1) != y:
          flag = False
          break
  if flag:
    ans = max(ans, sum(map(int, bin(i)[2:])))
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2000)

def DFS(p):
    if len(p)>=N:
        pat.append(p[:])
        return
    for i in range(2):
        p.append(i)
        DFS(p)
        p.pop()

N=int(input())
xy=[]
for i in range(N):
    A=int(input())
    x=[list(map(int,input().split())) for _ in range(A)]
    xy.append(x)

ans=0
p=[]
pat=[]
DFS(p)

for p in pat:
    cond=True
    for k in range(N):
        if p[k]==1:
            for h in xy[k]:
                if p[h[0]-1]!=h[1]:
                    cond=False
    if cond:
        ans=max(ans,sum(p))

print(ans)

Submission status: Accepted

Solution code:
import sys,itertools as it
f=sys.stdin.readline
n=int(f())
ll=[]
for i in range(n):
    a=int(f())
    for _ in range(a):
        x,y=map(int,f().split())
        ll+=[(i,x-1,y)]
c=0
for p in it.product([0,1],repeat=n):
    if all(p[i]<1 or p[x]==y for i,x,y in ll):
        c=max(c,sum(p))
print(c)

Submission status: Accepted

Solution code:
N=int(input())
g=[[-1 for i in range(15)]for j in range(15)]

for i in range(N):
  m=int(input())
  for j in range(m):
    x,y=map(int,input().split())
    #人iによる人xについての証言を格納
    g[i][x-1]=y

ans=0
for i in range(1<<N):
  honests=[0 for _ in range(N)]
  for j in range(N):
    if (i>>j)&1==1:
      honests[j]=1
  judge=True
  for k in range(N):
    if honests[k]==1:
      for l in range(N):
        if g[k][l]==-1:
          continue
        if g[k][l]!=honests[l]:
          judge=False
  if judge:
    ans=max(ans,honests.count(1))

print(ans)

Submission status: Accepted

Solution code:
import itertools

N = int(input())

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

saidai = 0
for i in itertools.product(range(2), repeat=N):
    ans = list(i)
    Flag = True
    for j in range(N):
        if ans[j] == 1:
            for k in A[j]:
                if ans[k[0]] == k[1] or ans[k[0]] == -1:
                    ans[k[0]] = k[1]
                else:
                    Flag = False
                    break
    if Flag == True:
        saidai = max(ans.count(1), saidai)

print(saidai)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import product


def read_data():
    N = int(input())
    testimonies = []

    for _ in range(N):
        A = int(input())
        testimonies_i = []

        for _ in range(A):
            x, y = map(int, input().split())
            testimonies_i.append((x - 1, y))  # 0-based

        testimonies.append(testimonies_i)

    return N, testimonies


def is_honest(pattern, i):
    # i番目の人が正直者であるか (0-based)
    return pattern[i]


def contradiction_exists(pattern, testimonies_i):
    # ある人の複数の証言に矛盾があるか
    for x, y in testimonies_i:
        if is_honest(pattern, x) != y:
            return True

    return False


def is_valid_pattern(pattern, testimonies):
    for i, p in enumerate(pattern):
        if not is_honest(pattern, i):
            continue

        if contradiction_exists(pattern, testimonies[i]):
            return False

    return True


def solve():
    N, testimonies = read_data()
    max_honest = 0

    for pattern in product([0, 1], repeat=N):
        # N=3 => [(0,0,0), (0,0,1), ..., (1,1,1)]
        if is_valid_pattern(pattern, testimonies):
            count_honest = sum(pattern)
            if count_honest > max_honest:
                max_honest = count_honest

    print(max_honest)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
"""
メモ用
ビット全探索
正直な人の証言がすべて一致するかどうかという方針でやればok。
"""

N = int(input())
l = [] # 証言リスト
m = [] # 証言の個数リスト
li = [0] # 成り立った時の正直者の数リスト

# ↓入力
for _ in range(N):
  n = []
  a = int(input())
  m.append(a)

  for _ in range(a):
    b = list(map(int, input().split()))
    n.append(b)
  l.append(n)
# ↑入力
for i in range(2 ** N):
  cnt = 0 # 正直な人の数
  cnt1 = 0 # -1なら成り立たない
  for j in range(N):
    if ((i >> j) & 1):
      cnt += 1 #人jが正直だったときにcnt += 1
      for k in range(m[j]):
        if ((i >> (l[j][k][0]-1)) & 1) == l[j][k][1]:
          pass
        else:
          cnt1 = -1
  if cnt1 == 0:
    li.append(cnt)
print(max(li))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    XY = [[] for _ in range(N)]
    for n in range(N):
        A = ii()
        xy = [[] for _ in range(A)]
        for a in range(A):
            xy[a] = il()
        XY[n] = xy

    ret = 0
    for b in range(1 << N):
        tf = [0] * N
        for i in range(N):
            if b >> i & 1:
                tf[i] = 1

        flg = True
        for j in range(N):
            if tf[j] == 0:
                continue
            for x, y in XY[j]:
                if tf[x - 1] != y:
                    flg = False

        if flg:
            ret = max(ret, sum(tf))
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
T = []
for i in range(N):
    for _ in range(int(input())):
        x, y = map(int, input().split())
        T.append((i, x - 1, y))

ans = 0
for i in range(1 << N):
    is_kind = [i >> j & 1 for j in range(N)]
    if all(not is_kind[j] or is_kind[x] == y for j, x ,y in T):
        ans = max(ans, sum(is_kind))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
T = [[-1] * N for _ in range(N)]
for i in range(N):
    for _ in range(int(input())):
        x, y = map(int, input().split())
        T[i][x - 1] = y

ans = 0
for i in range(1 << N):
    is_kind = [i >> j & 1 for j in range(N)]
    found = True
    for j in range(N):
        if not is_kind[j]:
            continue
        for k in range(N):
            if j == k or T[j][k] == -1 or T[j][k] == is_kind[k]:
                continue
            found = False
        if not found:
            break
    if found:
        ans = max(ans, sum(is_kind))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
T = [[-1] * N for _ in range(N)]
for i in range(N):
    for _ in range(int(input())):
        x, y = map(int, input().split())
        T[i][x - 1] = y

ans = 0
for i in range(1 << N):
    is_kind = [i >> j & 1 for j in range(N)]
    found = True
    for j in range(N):
        if not is_kind[j]:
            continue
        for k in range(N):
            if j == k or T[j][k] == -1 or T[j][k] == is_kind[k]:
                continue
            found = False
    if found:
        ans = max(ans, sum(is_kind))
print(ans)