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: Time Limit Exceeded

Solution code:
def popcnt(n):
    return bin(n).count("1")

n = int(input())
grid = []

for i in range(n):
    p = int(input())
    for j in range(p):
        array = [i] +list(map(int, input().strip().split(' ')))
        array[1] = array[1] - 1
        grid.append(array)


truth = 0
count = 0

for i in range(2**n):
    k = (bin(i)[2:]).zfill(n)
    count = 0
    for j in range(len(grid)):
        if int(k[grid[j][0]]) == 1:
            if (int(k[grid[j][1]]) == 1 and grid[j][2] == 0) or (int(k[grid[j][1]]) == 0 and grid[j][2] == 1):
                count = 1
    if count == 0:
        if truth < popcnt(i):
            truth = popcnt(i)

print(truth)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools

n = int(input())

ask_dict = {}
for i in range(n):
    ask_dict[i] = {}
    num = int(input())
    for j in range(num):
        x,y = map(int,input().split())
        ask_dict[i][x-1] = y


l = [i for i in range(n)]
for i in range(n):
    for v in itertools.permutations(l, i):
        pattern = [1 for _ in range(n)]
        for idx in v:
            pattern[idx] = 0

        count = 0
        for i,elem in enumerate(pattern):
            count += 1
            for k in ask_dict[i]:
                if (ask_dict[i][k] != pattern[k] and elem == 1) or (ask_dict[i][k] == pattern[k] and elem == 0):
                    count -= 1
                    break
        if count == n:
            print(sum(pattern))
            sys.exit()

print(0)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n = int(input())
l = list(itertools.combinations_with_replacement([0, 1], n))[::-1]
ll = [[-1 for i in range(n)] for j in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        ll[i][x-1] = y

for i in range(len(l)):
    l2 = list(set(itertools.permutations(l[i])))
    for lst in l2:
        flag = False
        for j in range(n):
            for k in range(n):
                if ll[j][k] == -1: continue
                if lst[j] == 1:
                    if lst[k] != ll[j][k]:
                        flag = True
                        break
                elif lst[j] == 0:
                    if lst[k] == ll[j][k]:
                        flag = True
                        break
            if flag:
                break
        if not flag:
            print(lst.count(1))
            exit()
print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools

n = int(input())
a_s = [0] * n
xss = []
yss = []
for i in range(n):
	a_s[i] = int(input())
	xss.append([])
	yss.append([])
	for _ in range(a_s[i]):
		x, y = map(int, input().split())
		xss[i].append(x)
		yss[i].append(y)

# print(xss)
# print(yss)

tmp_shojiki = [True] * n
for i in range(n):
	for shojiki in set(itertools.permutations(tmp_shojiki)):
		# print(i, shojiki)
		all_shojiki = True
		for j in range(n):
			if not shojiki[j]:
				continue
			for k in range(a_s[i]):
				x, y = xss[j][k] - 1, yss[j][k]
				if y == 1:
					if shojiki[x] == False:
						all_shojiki = False
				else:
					if shojiki[x] == True:
						all_shojiki = False
		if all_shojiki:
			print(n - i)
			sys.exit()

	tmp_shojiki[i] = False

print(0)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

n = int(input())
shogens = []

for people_index in range(n):
    this_shogens = []
    shogen_num = int(input())
    for _ in range(shogen_num):
        this_shogens.append(tuple(map(int, input().split())))

    shogens.append(this_shogens)

def make_pattern(number):
    pattern = [0 for _ in range(n)]
    index = 0
    while True:
        if number == 0:
            break
        else:
            pattern[index] = number % 2
            number //= 2
            index += 1
    return pattern


def ok(pattern):
    hantei = [None for _ in range(n)]
    seen_list = []
    q = Queue()
    ret = True
    for people_index in range(len(pattern)):
        if pattern[people_index] == 1:
            q.put(people_index)
            hantei[people_index] = 1

    while True:
        if q.empty():
            break
        else:
            people_index = q.get()
            if people_index in seen_list:
                continue
            else:
                seen_list.append(people_index)

            this_shogens = shogens[people_index]

            for this_shogen in this_shogens:
                people_sareta_index = this_shogen[0]-1
                shogen = this_shogen[1]

                if shogen == 1 and (people_sareta_index not in seen_list):
                    q.put(people_sareta_index)

                if hantei[people_sareta_index] == None:
                    hantei[people_sareta_index] = shogen

                if shogen != hantei[people_sareta_index]:
                    ret = False
                    break

    return ret

def main():
    max_num = 0
    for value in range(pow(2, n)-1, -1, -1):
        pattern = make_pattern(value)

        if ok(pattern):
            shojiki_count = 0
            for p in pattern:
                if p == 1:
                    shojiki_count += 1
            max_num = max(max_num, shojiki_count)

    print(max_num)
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())

matrix = np.zeros((n, n)) + 99
for i in range(n):
    a = int(input())
    for _ in range(a):
        j, val = list(map(int, input().split(' ')))
        matrix[i, j-1] = val

max_count = 0
for i in range(2**n):
    tmp_matrix = matrix.copy()
    bin_str = bin(i)[2:].zfill(n)
    bin_array = np.array([int(s) == 0 for s in bin_str])
    # pick back person who is judged true
    bin_array[np.any(matrix[bin_array] == 1, axis=0)] = True
    # judge if there is no lier
    if np.all(matrix[:, bin_array][bin_array] != 0):
        count = np.sum(bin_array)
        if count > max_count:
            max_count = count

print(max_count)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools

n = int(input())

ask_dict = {}
for i in range(n):
    ask_dict[i] = {}
    num = int(input())
    for j in range(num):
        x,y = map(int,input().split())
        ask_dict[i][x-1] = y

all_pattern_list = []
l = [i for i in range(n)]
for i in range(n):
    for v in itertools.permutations(l, i):
        pattern_list = [1 for _ in range(n)]
        for idx in v:
            pattern_list[idx] = 0
        all_pattern_list.append(pattern_list)

for pattern in all_pattern_list:
    count = 0
    for i,elem in enumerate(pattern):
        count += 1
        for k in ask_dict[i]:
            if (ask_dict[i][k] != pattern[k] and elem == 1) or (ask_dict[i][k] == pattern[k] and elem == 0):
                count -= 1
    if count == n:
        print(sum(pattern))
        sys.exit()

print(0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = np.zeros((N,2,N), dtype=bool) # A = {([false],[true]),,}

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

upper = 0

def hantei(mask,s):
  m2 = np.repeat([mask], s, axis=0).reshape(-1)
  aa = A[mask]
  a0 = aa[:,0].reshape(-1)
  if np.any(m2[a0]!=0): return False
  a1 = aa[:,1].reshape(-1)
  if np.any(m2[a1]!=1): return False
  return True

seed = 1 << np.arange(N)

for i in range(2**N):
  mask = (seed & i).astype(bool)
  s = np.sum(mask)
  if s <= upper: continue
  if hantei(mask,s): upper = s

print(upper)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [0]*n
x = [[] for i in range(n)]
y = [[] for i in range(n)]
for i in range(n):
    a[i] = int(input())
    for j in range(a[i]):
        tmp1,tmp2 = list(map(int,input().split()))
        x[i].append(tmp1-1)
        y[i].append(tmp2)

ans = 0
honest = [0]*n
for i in range(2**n): #bit全探索
    for j in range(n):
        if((i>>j)&1):
            honest[j] = 1
        else:
            honest[j] = 0
            
        f = True
        for k in range(n):
            for l in range(a[k]):
                if(honest[k]==1 and y[k][l]!=honest[x[k][l]]):
                    f = False
                    break
        if f:
            ans = max(ans,honest.count(1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = np.zeros((N,2,N), dtype=bool) # A = {([false],[true]),,}

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

upper = 0

def hantei(mask):
  for a in A[mask]:
    if np.any(mask[a[0]]!=0): return False
    if np.any(mask[a[1]]!=1): return False
  return True

seed = 1 << np.arange(N)

for i in range(2**N):
  mask = (seed & i).astype(bool)
  s = np.sum(mask)
  if s <= upper: continue
  if hantei(mask): upper = s

print(upper)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

L=[]
for i in range(N):
    L.append([2]*N)

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

max=0

for i in range(2**N):
    b=list(map(int,list(bin(i))[2:]))
    b=[0]*(N-len(b))+b
    s=0

    for j in range(N):
        for k in range(N):
            if b[j]==1 and b[k]==1:
                if L[j][k]==0 or L[k][j]==0:
                    s=1
            if b[j]==1 and b[k]==0:
                if L[j][k]==1:
                    s=1

    if s==0:
        max=sum(b)

print(max)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
Nloop = N + 1
A = np.zeros((Nloop, Nloop), dtype="int")

for i in range(1, Nloop):
    Acount = int(input())
    for _ in range(Acount):
        x, y = map(int,input().split())
        A[i, x] = 1 if y == 1 else -1

honest_loop = 2 ** N
is_honest = np.zeros(Nloop, dtype="bool")

ans = 0

for i in range(1, honest_loop):
    for l in range(1, Nloop):
        is_honest[l] = (i >> (l - 1) & 1 == 1)

    honest_check = True
    for l in range(1, Nloop):
        # lの人が正直者のとき
        if is_honest[l]:
            # lの人から見てjの人は正直者か？
            for j in range(1, Nloop):
                if A[l, j] == 1:
                    if not is_honest[j]:
                        honest_check = False
                elif A[l, j] == -1:
                    if is_honest[j]:
                        honest_check = False
                if not honest_check:
                    break
        if not honest_check:
            break

    if honest_check:
        ans = max(sum(is_honest), ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
LOCAL = True   and False


def dprint(*args):
  if LOCAL:
    print(*args)


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

anses = []

for x in range(2 ** n):
  flag = True
  cnt = 0
  dprint('x', x)
  for i in range(n):
    if x & (1 << i) != 0:
      dprint('i', i)
      cnt += 1
      for j in range(a[i]):
        dprint(int(x & (1 << (xy[i][j][0] - 1)) != 0) != xy[i][j][1])
        if int(x & (1 << (xy[i][j][0] - 1)) != 0) != xy[i][j][1]:
          flag = False
  if flag:
    anses.append(cnt)

dprint(anses)
print(max(anses))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    import numpy as np

    N = int(input())
    testimony = np.zeros((N, N), dtype=np.int64)
    for i in range(N):
        A = int(input())
        INF = 10 ** 10
        for _ in range(A):
            x, y = map(int, input().split())
            testimony[i, x - 1] += 1 if y else -INF

    # 正直者のパターンをbit全探索
    ans = 0
    for bit in range(1 << N):
        honest = set()
        pick = np.zeros(N, dtype=np.int64)
        for i in range(N):
            if bit & (1 << i):
                honest.add(i)
                pick += testimony[i, :]
        flag = True
        for j in range(N):
            value = pick[j]
            # 下記3つの内1つでも満たしたら，仮定が間違っていると分かる.
            if (0
                    or (j in honest and value < 0)         # 正直者なのに嘘つきと言われる
                    or (j not in honest and value > 0)     # 嘘つきなのに正直者と言われる
                    or (value < 0 and value % INF != 0)):  # 正直とも嘘つきとも言われる
                flag = False
                break
        if flag:
            ans = max(ans, len(honest))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
xy = [[] for _ in range(N)]

for i in range(N):
  A = int(input())
  for _ in range(A):
    xy[i].append(list(map(int, input().split())))
lst = [[0 for j in range(N)] for k in range(2**N)]

for l in range(2**N):
  for m in range(N):
    if (l >> m) & 1:
      lst[l][m] = 1

ans = 0
for n in lst:
  flag = True
  for f in range(N):
    if n[f] == 1:
      for g in xy[f]:
        if n[g[0]-1] != g[1]:
          flag = False
          break
    else:
      tmp = 0
      for g in xy[f]:
        if n[g[0]-1] == g[1]:
          tmp += 1
      if tmp == len(n):
        flag = False
    if not flag:
      break
  if flag:
    ans = max(ans, n.count(1))
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

N = int(input())

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

ans = 0
for i in range(1<<N):
    bit = [0] * N
    cnt = 0
    for j in range(N):
        div = 1 << j
        bit[j] = (i // div) % 2
        if bit[j] == 1:
            cnt += 1

    flag = True
    for j in range(N):
        if bit[j] == 0:
            continue
        for a in range(A[j]):
            x = data[j][a]
            if bit[x[0]-1] != x[1]:
                flag = False
                break
        if not flag:
            break
    
    if flag:
        ans = max(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
testimony = [[-1]*N for i in range(N)]
count = 0
for i in range(N):
  A = int(input())
  for j in range(A):
    x,y = map(int,input().split())
    testimony[i][x-1]=y
for i in range(2**N):
  honest = [0]*N
  for j in range(N):
    if(i>>j)&1:
      honest[j]=1
  flag=True
  for j in range(N):
    if honest[j]==1:
      for k in range(N):
        if testimony[j][k]==-1:
          continue
        if testimony[j][k]!=honest[k]:
          flag=False
  if flag==True:
    count=max(count,honest.count(1))
print(count)

Submission status: Accepted

Solution code:
N = int(input())
testimo_ls = [ [] for i in range(N) ]
rst = 0
for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split(' '))
        testimo_ls[i].append([x - 1, y])
for i in range(1 << N):
    honest_ls = []
    for j in range(N):
        if i >> j & 1:
            honest_ls.append(j)
    is_ok = True
    for s in honest_ls:
        for t in testimo_ls[s]:
            if t[0] in honest_ls and t[1] == 0:
                is_ok = False
                break
            if t[0] not in honest_ls and t[1] == 1:
                is_ok = False
                break
    if is_ok:
        rst = max(rst, len(honest_ls))
print(rst)

Submission status: Accepted

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

ans=0
for bit_state in range(2**N):
  flag=True
  for i in range(N):
    if (bit_state>>i)&1:
      for x, y in XY[i]:
        if (bit_state >>x)&1 != y:
          flag=False
  if flag:
    ans=max(ans, bin(bit_state).count("1"))
    
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
testimo_ls = [ [] for i in range(N) ]
rst = 0
for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split(' '))
        testimo_ls[i].append([x - 1, y])
for i in range(1 << N):
    honest_ls = []
    for j in range(N):
        if i >> j & 1:
            honest_ls.append(j)
    is_ok = True
    for s in honest_ls:
        for t in testimo_ls[s]:
            if t[1] == 0 and t[0] in honest_ls:
                is_ok = False
                break
            if t[1] == 1 and t[0] not in honest_ls:
                is_ok = False
                break
    if is_ok:
        rst = max(rst, len(honest_ls))
print(rst)

Submission status: Accepted

Solution code:
from itertools import product

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

ans = 0
for bit_pattern in product(range(2), repeat=n):
    for p,bit in enumerate(bit_pattern):
        if bit:
            if not all([bit_pattern[x] == y for x,y in info[p]]):
                break
    else:
        ans = max(ans, sum(bit_pattern))

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

n = int(input())
data = {}
for p in range(1, n+1):
    a = int(input())
    # 人p=1～の証言
    data[p] = [list(map(int, input().split())) for _ in range(a)]
    
# パターン生成
ans = 0
for honest in product(range(2), repeat=n):
    for p,hk in enumerate(honest, 1):
        if hk == 1:
            # 証言の矛盾をチェック
            if not all([honest[x-1] == y for x,y in data[p]]):
                break
    else:
        ans = max(ans, sum(honest))

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    s = bin(i)[2:].zfill(n)
    f = True
    for j,k in enumerate(a):
        for x,y in k:
            #仮定で正直者なのに証言に矛盾が生じている場合
            if s[x-1] != str(y) and s[j] == '1': f = False
    if f: ans = max(ans, s.count('1'))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

l = []
aas = []

for i in range(n):
    a = int(input())
    aas.append(a)
    s = [list(map(int,input().split())) for i in range(a)]
    l.append(s)

for i in range(2**n):
    flag_n = [1]*n
    for j in range(n):
        if ((i >> j)&1):
            flag_n[n-1-j] = 0
    cnt = 0
    for k in range(n):
        if flag_n[k] == 1:
            if all(l[k][m][1] == flag_n[l[k][m][0]-1] for m in range(aas[k])):
                cnt += 1
        if cnt == sum(flag_n):
            print(sum(flag_n))
            exit()

print(0)

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())
        xy[i].append((x_-1,y_))
ans = 0
for i in range(1,2**n):
    flag = 0
    for j in range(n):
        if i>>j&1:
            for x,y in xy[j]:
                if i>>x&1 != y:
                    flag = 1 
                    break
    if flag==0:
        ans = max(ans, bin(i)[2:].count("1"))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
testimo_ls = [ [] for i in range(N) ]
rst = 0
for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split(' '))
        testimo_ls[i].append([x - 1, y])
for i in range(1 << N):
    honest_ls = []
    for j in range(N):
        if i >> j & 1:
            honest_ls.append(j)
    is_ok = True
    for s in honest_ls:
        for t in testimo_ls[s]:
            if t[0] not in honest_ls and t[1] == 1:
                is_ok = False
                break
            if t[0] in honest_ls and t[1] == 0:
                is_ok = False
                break
    if is_ok:
        rst = max(rst, len(honest_ls))
print(rst)

Submission status: Accepted

Solution code:
N = int(input())

mastar_list = []
for i in range(2 ** N):
    x = "{:0" + str(N) + "b}"
    mastar_list.append(list(map(int,x.format(i))))


current = 1
ans = []
judge = [True for i in range(2 ** N)]
while current <= N:
    now = current -1
    loop_num = int(input())
    for i in range(loop_num):
        a,b = map(int,input().split())
        c = a - 1
        for index, situation in enumerate(mastar_list):
            if situation[now] == 1:
                if situation[c] == b:
                    pass
                else:
                    judge[index] = False
            else:
                pass
    current += 1

ans = []
for index, content in enumerate(judge):
    if content:
        ans.append(sum(mastar_list[index]))
        
print(max(ans))

Submission status: Accepted

Solution code:
from sys import stdin, stdout # only need for big input

max_honest = 0
testomonies = []
state = []

def dfs(person):
    global max_honest
    if person >= len(state):
        correctState = True
        for p in range(len(state)):
            if state[p] == 1:
                for t in testomonies[p]:
                    x, y = t
                    if state[x] != y:
                        correctState = False
                        break
        if correctState:
            sum = 0
            for s in state:
                sum += s
            max_honest = max(max_honest, sum)
        return

    state[person] = 0
    dfs(person + 1)

    state[person] = 1 
    dfs(person + 1)
    

def solve():
    global state
    n = int(stdin.readline())
    for _ in range(n):
        a = int(stdin.readline())
        t = []
        for _ in range(a):
            x, y = [int(inp) for inp in stdin.readline().split()]
            t.append((x - 1,y))
        testomonies.append(t)
    # print(testomonies)
    state = [-1] * n
    dfs(0)
    print(max_honest)


def main():
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin, stdout # only need for big input

max_honest = 0
testomonies = []
state = []

def dfs(person):
    global max_honest
    if person >= len(state):
        correctState = True
        for p in range(len(state)):
            if state[p] == 1:
                for t in testomonies[p]:
                    x, y = t
                    if state[x] != y:
                        correctState = False
                        break
        if correctState:
            sum = 0
            for s in state:
                sum += s
            max_honest = max(max_honest, sum)
        return

    state[person] = 0
    dfs(person + 1)

    state[person] = 1 
    dfs(person + 1)
    

def solve():
    global state
    n = int(input())
    for _ in range(n):
        a = int(input())
        t = []
        for _ in range(a):
            x, y = [int(inp) for inp in input().split()]
            t.append((x - 1,y))
        testomonies.append(t)
    # print(testomonies)
    state = [-1] * n
    dfs(0)
    print(max_honest)


def main():
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
tests = []
for n in range(N):
  A = int(input())
  tests_i = {}
  for a in range(A):
    x,y = map(int, input().split())
    tests_i[x-1] = y
  tests.append(tests_i)
# N人の人
# 正直者か真偽不明の発言者
# 人iがAi個の証言
# xijは正直物 if yij else 真偽不明の発言者

maximum = 0
import itertools
for Z in itertools.product(range(2), repeat=N):
  Z = list(Z)
#  print(Z)
  for i in range(N): # 人iの証言を検証
    honest = Z[i] # 正直ものか？
    for j,y in tests[i].items():
      if honest: #正直ものなら正しいはず
        if Z[j] != y:
#          print('NO')
          break
    else:
      # 証言が全て正しい
      continue
    break # 明らかに誤った証言をしたものがいる
  else:
#    print("ok")
    maximum = max(maximum, sum(Z))
print(maximum)

Submission status: Accepted

Solution code:
N = int(input())
testimo_ls = [ [] for i in range(N) ]
rst = 0
for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split(' '))
        testimo_ls[i].append([x - 1, y])
for i in range(1 << N):
    honest_ls = []
    for j in range(N):
        if i >> j & 1:
            honest_ls.append(j)
    is_ok = True
    for s in honest_ls:
        for t in testimo_ls[s]:
            if t[0] in honest_ls and t[1] == 0:
                is_ok = False
            if t[0] not in honest_ls and t[1] == 1:
                is_ok = False
    if is_ok:
        rst = max(rst, len(honest_ls))
print(rst)

Submission status: Accepted

Solution code:
n=int(input())
p=2
from itertools import product
iterator=product(range(p),repeat=n)
#for idxs in iterator:
#    print(idxs)

L=[[] for i in range(n)]
for i in range(n):
    a=int(input())
    for _ in range(a):
        L[i].append(list(map(int,input().split())))
ans=0
for idxs in iterator:
    cnt_honest=0
    for i in range(n):
        cnt=0
        if idxs[i]==1:
            for j in L[i]:
                if idxs[j[0]-1]==j[1]:
                    cnt+=1
            if cnt==len(L[i]):
                cnt_honest+=1
    if cnt_honest==sum(idxs):
        ans=max(sum(idxs),ans)
print(ans)

Submission status: Accepted

Solution code:

N = int(input())
testimo_ls = [ [] for i in range(N) ]
rst = 0
for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split(' '))
        testimo_ls[i].append([x - 1, y])
for i in range(1 << N):
    honest_ls = []
    for j in range(N):
        if i >> j & 1:
            honest_ls.append(j)
    is_ok = True
    for s in honest_ls:
        for t in testimo_ls[s]:
            if t[1] == 0 and t[0] in honest_ls:
                is_ok = False
                break
            if t[1] == 1 and not t[0] in honest_ls:
                is_ok = False
                break
    if is_ok:
        rst = max(rst, len(honest_ls))
print(rst)

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    s = 0
    t = [0]*n
    for j in range(n):
        if i>>j & 1:
            t[j]=1
    is_contradict = 0
    for j in range(n):
        if t[j]:
            for k in range(n):
                if li[j][k]==-1:
                    continue
                if li[j][k] != t[k]:
                    is_contradict = 1
    if not is_contradict:
        ans = max(ans, sum(t))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
lista = []
xy = []
for i in range(n):
    a = int(input())
    lista.append(a)
    s = [list(map(int, input().split())) for _ in range(a)]
    xy.append(s)
ans = 0
for j in range(2**n):
    num = 0
    d = []
    for k in range(n):
        if((j >> k) & 1) == 1:
            d.append(1)
        else:
            d.append(0)
    c = 0
    for l in range(n):
        cnt = 0
        if d[l] == 1:
            if lista[l] != 0:
                for m in range(lista[l]):
                    if xy[l][m][1] == d[xy[l][m][0] - 1]:
                        cnt += 1
                        if cnt == lista[l]:
                            c += 1
                    else:
                        break
            else:
                c += 1
    if c == d.count(1):
        num = c
    ans = max(num, ans)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
g = [[-1 for _ in range(15)] for _ in range(15)]
for i in range(n):
  a = int(input())
  for j in range(a):
    x, y = map(int, input().split())
    g[i][x-1] = y
    
ans = 0
for bit in range(1<<n):
  honests = [0]*n
  for i in range(n):
    if bit & 1<<i: honests[i] = 1
  flg = True
  for i in range(n):
    if honests[i]:
      for j in range(n):
        if g[i][j] == -1: continue
        if g[i][j] != honests[j]: flg = False
  if flg:
    ans = max(ans, honests.count(1))
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
def read(): return sys.stdin.readline() # 標準入力
def fbit(i, j=-1): return format(i, 'b').zfill(j) # bit 表示
def popcount(x): # ビットカウント
    x=x-((x>>1)&0x5555555555555555)
    x=(x&0x3333333333333333)+((x>>2)&0x3333333333333333)
    x=(x+(x>>4))&0x0f0f0f0f0f0f0f0f;x=x+(x>>8);x=x+(x>>16);x=x+(x>>32)
    return x&0x0000007f


def solv(N:int, A, x, y):
    ans = 0
    for bits in range(1<<N):
        ok = True
        count = 0
        for i in range(N):
            if not (bits & 1<<i): continue
            count+=1
            for j in range(A[i]):
                if (bits >> (int(x[i][j])-1) & 1) ^ int(y[i][j]): ok = False
        if ok: ans = max(ans, count);


    print(ans)
def main():
    N = int(read())
    A = []
    x = []
    y = []
    for i in range(N):
        A.append(int(read()))
        _x=[]
        _y=[]
        for j in range(A[-1]):
            [a,b] = list(read().rsplit())
            _x.append(a)
            _y.append(b)
        x.append(_x)
        y.append(_y)


    solv(N, A, x, y)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import itertools

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline
    n=int(readline())
    dat = [[-1 for i in range(n)] for j in range(n)]
    for i in range(n):
        m=int(readline())
        for j in range(m):
            x,y=map(int, readline().rstrip().split())
            x-=1
            dat[i][x] = y
    
    ans=0
    for ptn in itertools.product([False,True], repeat=n):
        ok=True
        for i in range(n):
            if ptn[i]==False:
                continue
            for j in range(n):
                if dat[i][j] == -1:
                    continue
                if dat[i][j] == 1 and ptn[j]==False:
                    ok=False
                    break
                if dat[i][j] == 0 and ptn[j]==True:
                    ok=False
                    break
            if ok==False:
                break
        if ok==True:
            ans=max(ans,ptn.count(True))
    print(ans)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()