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:
# 全探索
# 証言が矛盾していないかどうかをチェックする
# 証言の妥当性のみを見れば良い感じ？
N = int(input())
X = []
Y = []
A = []
for i in range(N):
    a = int(input())
    A.append(a)
    b = []
    X_ = []
    Y_ = []

    for j in range(a):
        x, y = list(map(int, input().split()))
        X_.append(x)
        Y_.append(y)
        
    X.append(X_)
    Y.append(Y_)

# bit探索
ans = []
for i in range(2**N):
    a = [0] * N
    cnt = 0
    for j in range(N):
        if i & (1 << j):
            a[j] = 1

    for j in range(N):
        flag = False
        if a[j] == 1:
            for k in range(A[j]):
                if a[X[j][k]-1] != Y[j][k]:
                    flag = True
                    break
        if flag:
            break
    
    if flag == False:
        ans.append(a.count(1))

print(max(ans))

Submission status: Accepted

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

ans = 0

for S in range(1<<N):
    cnt = 0
    flag = True
    for j in range(N):
        if (S >> j) & 1 == 0:
            continue
        cnt += 1
        res = info[j]
        for x, y in res:
            if (S >> x) & 1 != y:
                flag = False
                break
    if flag:
        ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

A = []
x = []
y = []
x_dash = []
y_dash = []
ans = []
for i in range(n):
	A.append(int(input()))
	x_dash = []
	y_dash = []
	for j in range(A[i]):
		x_dash_dash,y_dash_dash = map(int,input().split())
		x_dash.append(x_dash_dash)
		y_dash.append(y_dash_dash)
	tmp = x_dash
	x.append(tmp)
	tmp = y_dash
	y.append(tmp)

for i in range(2**n):
	a = [0]*n
	count = 0
	for j in range(n):
		if i & (1<<j):
			a[j] = 1

	for j in range(n):
		flag = False
		if a[j] == 1:
			for k in range(A[j]):
				if a[x[j][k]-1] != y[j][k]:
					flag = True
					break
		if flag:
			break
	if not flag:
		ans.append(a.count(1))
		ans.append(count)

print(max(ans))

Submission status: Accepted

Solution code:
N = int(input())

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

result = 0
for i in range(1, 2 ** N):
    consistent = True
    for j in range(N):
        if (i >> j) & 1 == 0:
            continue
        for x, y in evidences[j]:
            if (i >> x) & 1 != y:
                consistent = False
                break
        if not consistent:
            break
    if consistent:
        result = max(result, bin(i)[2:].count('1'))
print(result)

Submission status: Accepted

Solution code:
#%%
import itertools

n = int(input())
l = list(itertools.product(range(2), repeat=n))
s = [[] for _ in range(n)]

for i in range(n):
    tmp = int(input())
    for j in range(tmp):
        tmp_list = list(map(int, input().split()))
        s[i].append(tmp_list)

#print(s)

ans = 0
for i in range(len(l)):
    #print(' ', l[i])
    tmp = 0
    tmp_list = l[i]
    flag = True
    for j in range(n):
        if tmp_list[j] == 0:
            pass
        else:
            tmp += 1
            for k in range(len(s[j])):
                #print(tmp_list[s[j][k][0]-1], s[j][k][1])
                if tmp_list[s[j][k][0]-1] == s[j][k][1]:
                    pass
                else:
                    flag = False
                    break
    if flag:
        ans = max(ans, tmp)
    #print('ans', ans)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

n = int(input())

p = []

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

# print(p)

a = np.array(list(itertools.product([0, 1], repeat=n)), dtype="bool")

# print(a)

for i, x, y in p:
    cond = (~a[:, i]) | (a[:, x] == bool(y))
    a = a[cond]
# print(a)

ans = a.sum(axis=1).max()
print(ans)

Submission status: Accepted

Solution code:
N= int(input())
Harray = []
for i in range(N):
    Aarray = []
    A = int(input())
    for j in range(A):
        xy = list(map(int,input().split()))
        Aarray.append(xy)
    Harray.append(Aarray)


count = []
for i in range(2**N):
    honest = [0 for i in range(N)]
    c = 0
    for j in range(N):
        if (i >> j) & 1 == 1:
            honest[j] = 1
    for k in range(N):
        if honest[k] == 1:
            ar = Harray[k]
            for l in ar:
                if honest[l[0]-1] != l[1]:
                    c = 1
    if c == 0:
        count.append(honest.count(1))
print(max(count))

Submission status: Accepted

Solution code:
n=int(input())
ans=0
g=[[-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())
    g[i][x-1]=y
for i in range(2**n):
  ok=True
  for j in range(n):
    if (i>>j)&1:
      for k in range(n):
        if g[j][k]==-1:
          continue
        if (i>>k)&1!=g[j][k]:
          ok=False
  if ok:
    d=i
    t=str(bin(d)).count('1')
    ans=max(t,ans)
print(ans)

Submission status: Accepted

Solution code:
def read_valus():
    return map(int, input().split())


def read_list():
    return list(read_valus())


def read_lists(N):
    return [read_list() for n in range(N)]


def get_bit(n, i):
    return n >> i & 1


def f(T, n):
    # for i in range(len(T)):
    #     if get_bit(n, i):
    #         for x, y in T[i]:
    #             if get_bit(n, x) != y:
    #                 return False
    # return True
    return all(all(get_bit(n, x) == y for x, y in T[i]) for i in range(len(T)) if get_bit(n, i))


def main():
    N = int(input())
    T = [[] for n in range(N)]
    for n in range(N):
        A = int(input())
        for _ in range(A):
            x, y = read_valus()
            x -= 1
            T[n].append((x, y))

    res = 0
    for n in range(2 ** N):
        if f(T, n):
            res = max(res, bin(n).count("1"))

    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import combinations, count
 
n = int(input())
r = range(n)
a = [(set(), set()) for _ in r]
for i in r:
    for _ in range(int(input())):
        x, y = map(int, input().split())
        a[i][y].add(x - 1)
ans = next(i for i in count(n, -1) for x in map(set, combinations(r, i))
           if all(a[j][0].isdisjoint(x) and a[j][1] < x for j in x))
print(ans)

Submission status: Accepted

Solution code:
#147c
N = int(input())

xy_list = [["*"]]

for i in range(N):
    A = int(input())
    i_xy = [("*","*")] #A=0に備えて、無効なのを追加
    for j in range(A):
        x,y = map(int, input().split())
        i_xy.append((x,y))
    xy_list.append(i_xy)
    
#N<=15　なので、2**15 = 32768　間に合う。

#正直・不親切をbitで仮定。正直者の証言で矛盾しているものないかを調べる。
ans = [0]

for i in range(2**(N)):
    bit_array = str(bin(i)[2:]).zfill((N))
    #print("#############")
    #print(bit_array)
    
    break_flag = 0
    honest = 0
    
    for j in range(len(bit_array)): #生成したbit_aray内で正直者を探す。    
        #print(bit_array[j])
        
        if bit_array[j] == "1":
            #print("person ",j+1," said,")
            for xy in xy_list[j+1]:
                x = xy[0]
                y = xy[1]
                if x != "*" and y != "*":
                    x = int(x)
                    y = int(y)
                    #print("person ",x," is ",y)
                    
                    if int(bit_array[x-1]) != y:
                        #print("Contradiction!")
                        honest = 0
                        break_flag = 1
                        break
            else:
                honest += 1
                
        if break_flag == 1:
            break
            
    #print("honest:",honest) 
    ans.append(honest)
    
print(max(ans))

Submission status: Accepted

Solution code:
n=int(input())
XYS=[]
for _ in range(n):
  a=int(input())
  XY=[list(map(int,input().split())) for _ in range(a)]
  XYS.append(XY)

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

Submission status: Accepted

Solution code:
def inputlist():
	n=int(input())
	A=list()
	for i in range(n):
		Ai = int(input())
		s=list()
		for i in range(Ai):
			s += input().split()
		s = [int(i) for i in s]
		A.append(s)
	return A
A=inputlist()
n=len(A)
ans=0
for i in range(2**n):
	p = 1
	bit_str = str(format(i,'015b'))
	for j in range(n):
		if ((i >> j) & 1):
			for k in range(0,len(A[j]),2):
				if not(A[j][k+1] == int(bit_str[-1*A[j][k]])):
					p = 0
	if (p):
		ans = max(ans,bit_str.count('1'))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = []
x = [[] for i in range(N)]
y = [[] for i in range(N)]
for i in range(N):
    A.append(int(input()))
    for j in range(A[i]):
        tmpX, tmpY = map(int, input().split())
        x[i].append(tmpX-1)
        y[i].append(tmpY)
ans = 0

for case in range(2**N):
    flag = True
    honest = 0
    for i in range(N):
        if (case >> i)&1 == False:  continue
        for j in range(A[i]):
            if (case >> x[i][j])&1 != y[i][j]:
                flag = False
        honest += (case >> i)&1

    if flag:
        ans = max(ans, honest)

print(ans)

Submission status: Accepted

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

for i in range(n):
    for _ in range(int(input())):
        x,y = map(int,input().split())
        g[i][x-1] = y

ans = 0
for s in range(2**n):
    ok = True
    for i in range(n):
        if (s>>i&1) == 1:
            for j in range(n):
                if g[i][j] == -1:continue
                if (s>>j&1) != g[i][j]:ok = False
    if ok:
        t = str(bin(s)).count("1")
        ans = max(ans,t)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
A = [0]*N
X = np.zeros([N,N],dtype=int)
Y = np.zeros([N,N],dtype=int)

for n in range(N):
    A[n] = int(input())
    for a in range(A[n]):
        X[n][a], Y[n][a] = list(map(int,input().split()))

ans = 0

for bits in range( 1, 1<<N ):
    ok = True
    for i in range( 0, N ):
        if not ok:
            break
        if not ( bits & (1 << i) ):
            continue
        for j in range( 0, A[i] ):
            if (( bits >> (X[i][j]-1) ) & 1) ^ Y[i][j]:
                ok = False
                break
    if ok:
        ans = max( ans, (str(bin(bits))[2:]).count('1'))
        
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = []
x = [[] for i in range(N)]
y = [[] for i in range(N)]
for i in range(N):
    A.append(int(input()))
    for j in range(A[i]):
        tmpX, tmpY = map(int, input().split())
        x[i].append(tmpX-1)
        y[i].append(tmpY)
ans = 0

for case in range(2**N):
    flag = True
    case = str(format(case, '016b'))[-N:]
    honest = [i for i, x in enumerate(case) if x == '1']
    #print(honest)
    for hon in honest:
        for j, other in enumerate(x[hon]):
            #print(other in honest)
            if (other in honest) and (y[hon][j] == 0):
                flag = False

            elif (not(other in honest)) and (y[hon][j] == 1):
                flag = False

            else:
                continue
    #print(flag)
    if flag:
        ans = max(ans, len(honest))

print(ans)

Submission status: Accepted

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

def main():
    n = int(input())
    remarks = [[]] * n
    max_v = 0

    for i in range(n):
        a = int(input())
        remarks[i] = [tuple(map(int, input().split())) for _ in range(a)]

    for i in range(2 ** n):
        i_bin = format(i, 'b').zfill(n)
        if i_bin.count('1') <= max_v:
            continue

        is_true = True
        for j in range(n):
            if i_bin[j] == '1':
                for k in remarks[j]:
                    if int(i_bin[k[0]-1]) != k[1]:
                        is_true = False
                        break
                if is_true == False:
                    break
        if is_true:
            max_v = max(max_v, i_bin.count('1'))
    print(max_v)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [0] * N
XY = []

for i in range(N):
    tmp = []
    a = int(input())
    A[i] = a
    for j in range(a):
        tmp.append(list(map(int, input().split())))
    XY.append(tmp)

def counter(x):
    if x == 0:
        return 0
    else:
        return counter(x >> 1) + (x & 1)

ans = 0
for bits in range(1, 1 << N):
    ok = True
    for i in range(N):
        if not (bits & (1 << i)):
            continue
            
        for x, y in XY[i]:
            if ((bits >> (x - 1)) & 1) ^ y:
                ok = False
                
    if ok:
        ans = max(ans, counter(bits))
            
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [list() for _ in range(n)]

for i in range(n):
    m = int(input())
    for j in range(m):
        x, y = map(int, input().split())
        a[i].append((x-1, y))
    
ans = 0
for i in range(2 ** n):
    honests = [(i >> j) & 1 for j in range(n)]
    for v in range(n):
        if not honests[v]: continue
        for nv, h in a[v]:
            if h != honests[nv]: break
        else: continue
        break
    else:
        ans = max(ans, sum(honests))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
 
g = [[-1 for j in range(n)] for i in range(n)]
 
for i in range(n):
	a = int(input())
	for _ in range(a):
		x, y = map(int, input().split())
		g[i][x-1] = y
 
ans = 0
for s in range(2**n):
    ok = True
    for i in range(n):
        if (s>>i&1) == 1:
            for j in range(n):
                if g[i][j] == -1: continue
                if (s>>j&1) != g[i][j]: ok = False
    if ok:#あっているなら、ビット内に何個1があるかを数える
        #print("s = ", s)
        t = 0
        x = s#xを変えてもsは変化しない
        t = str(bin(x)).count("1")
        ans = max(ans, t)
print(ans)

Submission status: Accepted

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()
        a -= 1
        xy[i].append([a,b])

def check(h):
    t = [0] * n
    for i,j in enumerate(h):
        t[i] = j
    for i,j in enumerate(h):
        if j:
            for k in xy[i]:
                if t[k[0]] != k[1]:
                    return False
    return True

def dfs(h):
    if len(h) == n:
        if check(h):
            return sum(h)
        else:
            return 0
    return max(dfs(h + [True]), dfs(h + [False]))
print(dfs([]))

Submission status: Accepted

Solution code:
N=int(input())
syougen=[]
for i in range(N):
  A=int(input())
  X=[list(map(int,input().split())) for i in range(A)]
  syougen.append(X)

def chk(l,X):
  for x,y in l:
    if X[x-1]!=str(y):
      return True
    else:
      continue
  return False

ans=0
for i in range(2**N):
  flg=True
  X=format(i,'b').zfill(N)
  for j,x in enumerate(X):
    if x=='0':
      continue
    elif chk(syougen[j],X):
      flg=False
      break
  if flg:
    _ans=sum(list(map(int,''.join(X))))
    if _ans>ans:
      ans=_ans
  
print(ans)

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True, end="")

N = _I()
X=[]
for i in range(N):
	x=[]

	for j in range(_I()):
		x.append(LI())
	X.append(x)
	
#print(X)
ans=[]

#2の15乗通りしかないので、全部見る
def dfs(idx, ls):
	if idx == N:
		# あってるか確認
		ok = True
		#print("ls",ls)
		for lidx, l in enumerate(ls):
			#print(lidx , l)
		
			if l != 1: continue
			for x in X[lidx]:
				#print("x",x)
			
				if ls[x[0]-1] != x[1]:
					ok=False
					break
		if ok:
			#print("ok", ls)
		
			ans.append(sum(ls))
		
			
		
		
		return
	# 通りを作る
	dfs(idx+1, ls+[0])
	dfs(idx+1, ls+[1])

dfs(0, [])
print(max(ans))

Submission status: Accepted

Solution code:
# インプット情報を格納
member_num = int(input())
ans_table = []
for i in range(member_num):
    ans_num = int(input())
    ans = {}
    for k in range(ans_num):
        a,b = input().split()
        # 人を表すIDはインデックスを0オリジンにするために-1する
        ans[int(a) - 1] = b
    ans_table.insert(i,ans)

# 取りうる全パターン(誰が正直/不親切)を作成
# member_numの配列ｘ2^member_num
bin_str = []
for i in range(2**member_num):
    bin_line = format(i,'b').zfill(member_num)
    bin_str.append(bin_line)

#矛盾検索
contradiction = 0
anser_index = []
for i in range(2**member_num):
    for k in range(member_num):
        if bin_str[i][k] == "1":
            # ans_tableのk番目の回答は信用できると仮定
            for idnum, answer in ans_table[k].items():
                if bin_str[i][idnum] != answer:
                    # 矛盾あり
                    contradiction = 1
                    break
        if contradiction == 1:
            break
    # 矛盾がなかった
    if contradiction == 0:
        anser_index.append(i)
    contradiction = 0

honest = 0
for index in anser_index:
    honest_tmp = bin_str[index].count("1")
    if honest < honest_tmp:
        honest = honest_tmp
print(honest)

Submission status: Accepted

Solution code:
n = int(input())
data = [[-1 for _ in range(n)] for _ in range(n)]
for i in range(n):
    reps = int(input())
    for _ in range(reps):
        x, y = list(map(int, input().split(' ')))
        x -= 1
        data[i][x] = y

# print(data)

ans = 0
for i in range(pow(2, n)):
    nat = [0 for _ in range(n)]
    for idx in range(n):
        bit = (i >> idx) & 1
        nat[idx] = bit

    # print(nat)

    # vertification
    ok = True
    for user, row in enumerate(data):
        if not nat[user]:
            continue
        for idx in range(n):
            if row[idx] != -1:
                if nat[idx] != row[idx]:
                    ok = False

    if ok: 
        ans = max(ans, sum(nat))

print(ans)

Submission status: Accepted

Solution code:
import copy

sw = []
N = int(input())
def create_ki(data):
    if len(data) == N:
        sw.append(data)
        return
    tmp = copy.copy(data)
    tmp.append(0)
    create_ki(tmp)
    tmp2 = copy.copy(data)
    tmp2.append(1)
    create_ki(tmp2)

create_ki([])

Speak = [{} for i in range(N)]
for i in range(N):
   A = int(input())
   for j in range(A):
       XY = input().split()
       Speak[i][XY[0]] = XY[1]

ans = 0
for peaples in sw: #0が真実で1が嘘
    true_list = [-1]*N
    isMujun = False
    for i in range(N):
         if peaples[i] == 1:
             for k,v in Speak[i].items():
                 k = int(k)
                 v = int(v)
                 if peaples[k-1] != v:
                     isMujun = True
                     break
                 elif (true_list[k-1] != -1) and (true_list[k-1] != v):
                     isMujun = True
                     break
                 else:
                     true_list[k-1] = v
    if not isMujun:
        ans = max(ans, sum(peaples))
print(ans)

Submission status: Accepted

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 = []
    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: Accepted

Solution code:
n = int(input())
l = [[] for _ in range(n)]

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

ans = 0
for i in range(1 << n):
    h = []
    for j in range(n):
        h.append(i & 1 << j != 0)
    b = True
    for j in range(n):
        if i & 1 << j:
            for k in l[j]:
                if (k[1] == 1) != h[k[0]]:
                    b = False
                    break
        if not b:
            break
    if b:
        ans = max(ans,h.count(True))

print(ans)

Submission status: Accepted

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)
 
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)

Submission status: Accepted

Solution code:
n = int(input())
l = [[] for _ in range(n)]

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

ans = 0
for i in range(1 << n):
    h = []
    for j in range(n):
        h.append(i & 1 << j != 0)
    b = True
    for j in range(n):
        if i & (1 << j) != 0:
            for k in l[j]:
                if (k[1] == 1) != h[k[0]]:
                    b = False
                    break
        if not b:
            break
    
    if b:
        x = 0
        for j in range(n):
            if i & 1 << j:
                x += 1
        ans = max(ans,x)

print(ans)

Submission status: Accepted

Solution code:
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)

estab = []
for bits in range(2 ** N):
  ok = 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 = False
        #print('矛盾', i, j, bin(bits), (x[i][j]), (bits >> (x[i][j] - 1) & 1), y[i][j])
  if ok:
    estab.append(bin(bits).count('1'))
    #print('成立', bin(bits))

print(max(estab))

Submission status: Accepted

Solution code:
N=int(input())
A=[[] for i in range(N)]
Ai = []
for i in range(N):
    Ai.append(int(input()))
    for j in range(Ai[-1]):
        A[i].append(list(map(int, input().split(' '))))

ans = 0
for i in range(2**N):
    ansp= 0
    flg = True
    binstr = format(i,"b").zfill(N)
    for j in range(N):
        if binstr[j] == "1":
            ansp += 1
            for x in A[j]:
                if binstr[x[0]-1] != str(x[1]):
                    flg = False
        elif binstr[j] == 0:
            continue
    if flg:
        ans = max(ans, ansp)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
l=[0]*n
ans=0
for i in range(n):
	a.append(int(input()))
	l[i]=[list(map(int,input().split())) for i in range(a[-1])]
#print(a,l)
for i in range(2**n):
	i=format(i,'b').zfill(n)
	c=[]
	for j in range(n):
		if i[j]=='1':
			c.append(j)
	#print(c,l)
	for j in c:
		for k in l[j]:
			#print(k)
			if k[1]==1 and (k[0]-1 not in c):
				break
			elif k[1]==0 and (k[0]-1 in c):
				break
		else:
			continue
		break
	else:
		#print(ans)
		ans=max(ans,len(c))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
arr = [ ([], []) for i in range(n+1)]
for i in range(n):
    m = int(input())
    for j in range(m):
        a, b = map(int, input().split())
        if b == 1:
            arr[i][0].append(a-1)
        else:
            arr[i][1].append(a-1)
cur = [0 for i in range(n)]
ans = 0
def solve(i):
    global ans, cur, n, arr
    if i == n:
        flag = 0
        for j in range(n):
            if cur[j] == 1:
                for honest in arr[j][0]:
                    if cur[honest] == 0:
                        flag = 1
                for no in arr[j][1]:
                    if cur[no] == 1:
                        flag = 1
        if flag == 0:
            ans = max(ans, sum(cur))
        return
    cur[i] = 1
    solve(i+1)
    cur[i] = 0
    solve(i+1)
solve(0)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = []
dict = []
for i in range(n):
    a.append(int(input()))
    dict.append([list(map(int, input().split())) for _ in [0] * a[-1]])
cnt = 0
for i in range(2 ** n):
    flag = 0
    c = ('0' * n + bin(i)[2:])[-n:]
    for i in range(n):
        if c[i] == '0':
            continue
        for j, k in dict[i]:
            if (k == 1 and c[j - 1] == '0') or (k == 0 and c[j - 1] == '1'):
                flag = 1
                break
    if flag == 1:
        continue
    cnt = max(cnt, c.count('1'))
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
a = [0]*n
x = [[0] *n for i in range(n)]
y = [[0] *n for i in range(n)]
ans = 0
for i in range(n):
    a[i] = int(input())
    for j in range(a[i]):
        x[i][j],y[i][j] = map(int,input().split())
        x[i][j]-=1
def honest(i,j):
    return (i>>j)%2 ==1
def check(m):
    for i in range(n):
        if not honest(m,i) :continue
        for j in range(a[i]):
            if y[i][j] == 1 and honest(m,x[i][j]) == 0:
                return False
            if y[i][j] == 0 and honest(m,x[i][j]) == 1:
                return False
    return True
def count(c):
    cnt = 0
    for i in range(c//2+5):
        cnt+= (c >> i)%2
    return cnt
for i in range(2**n):
    if check(i):
        ans = max(ans,count(i))
    
        
        
        
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [0]*n
x = [[0] *n for i in range(n)]
y = [[0] *n for i in range(n)]
ans = 0
for i in range(n):
    a[i] = int(input())
    for j in range(a[i]):
        x[i][j],y[i][j] = map(int,input().split())
        x[i][j]-=1
def honest(i,j):
    return (i>>j)%2 ==1
def check(m):
    for i in range(n):
        if not honest(m,i) :continue
        for j in range(a[i]):
            if y[i][j] == 1 and honest(m,x[i][j]) == 0:
                return False
            if y[i][j] == 0 and honest(m,x[i][j]) == 1:
                return False
    return True
def count(c):
    cnt = 0
    for i in range(n):
        cnt+= honest(c,i)
    return cnt      

for i in range(2**n):
    if check(i):
        ans = max(ans,count(i))
    
        
        
        
print(ans)

Submission status: Accepted

Solution code:
import sys
from pprint import pprint

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

        if flag:
            # pprint(true_info)
            ans = max(ans, sum(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)