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:
import itertools
N = int(input())
ans = 0
A = []
aa = []
for n in range(N):
    a = int(input())
    aa.append(a)
    xy = [list(map(int,input().split())) for i in range(a)]
    A.append(xy)
for v in itertools.product([1,0], repeat = N):
    s = 1
    for i in range(N):
        if v[i] == 1:
            t = 1
            for j in range(aa[i]):
                if v[A[i][j][0]-1] != A[i][j][1]:
                    t = 0
                    break
            if t != 1:
                s = 0
                break
    if s == 1:
        break
print(v.count(1))

Submission status: Accepted

Solution code:
import sys
from itertools import product

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n = II()
    ps = [[] for i in range(n)]
    # eva = [[] for i in range(n)]
    for i in range(n):
        a = II()
        for j in range(a):
            ps[i].append(LI())
    max_ = 0
    for c in product([0, 1], repeat=n):
        c = list(c)
        # print(c)
        for i, p in enumerate(c):
            if p == 1:
                for opp in ps[i]:
                    # print(c[opp[0] - 1], opp[1])
                    if c[opp[0] - 1] != opp[1]:
                        # print(c[opp[0] - 1], opp[1])
                        break
                else:
                    continue
                break
        else:
            # print(c)
            max_ = max(max_, sum(c))
    print(max_)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

# ビット全探索
bit = 0
ans = 0
for X in range(2 ** n):
    # 1010など
    flag = False
    count = 0
    for num in range(n):
        f = True
        if X & (2 ** num) >= 1:
            for x, y in xy[num]:
                t = 1 if X & 2 ** (x-1) >= 1 else 0
                if t != y:
                    f = False
                    break
            if f == False:
                count = 0
                break
            count += 1
    ans = max(count, ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input().strip())
datas = []
for _ in range(N):
    A = int(input().strip())
    datas.append([[int(str) for str in input().strip().split()] for _ in range(A)])

def judge(bit):
    true_man = [(bit & (1 << d)) >> d for d in range(N)]

    for i in range(N):
        if true_man[i]:
            for data in datas[i]:
                if true_man[data[0] - 1] != data[1]:
                    return 0

    return sum(true_man)

ans = 0
for bit in range(2 ** N):
    ans = max(ans, judge(bit))

print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
import itertools
N = int(input())
coms = []
for n in range(N):
    A = int(input())
    com = []
    for a in range(A):
        tmp = list(map(int,input().split()))
        com.append(tmp)
    coms.append(com)
#print (coms)
nums = [0, 1]
ans = 0
for pt in itertools.product(nums, repeat=N):
    flag = False
    
    if sum(pt) > ans:
        for idx in range(len(pt)):
            if pt[idx]==1:
                for com in coms[idx]:
                    if pt[com[0]-1] + com[1] == 1:
       
                        flag = True
        if not flag:
            ans = sum(pt)
            #print (pt)
    else:
        pass
        

print (ans)

Submission status: Accepted

Solution code:
def binp( n ):
    global N
    data = []
    for i in range(N):
        data.append( n % 2)
        n //= 2
    return data

def honest(pat):
    c = 0
    for p in pat:
        if p == 1:
            c+=1
    return c

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

ans = 0
for p in range(2**N):
    pat = binp(p)
    #print(pat)
    f = True
    for i in range(N):
        if pat[i] == 1:
            for x,y in Data[i]:
                #print('---',i,x,y)
                if (y == 0 and pat[x-1] == 0) or (y == 1 and pat[x-1] == 1):
                    pass
                    #print('OK')
                else:
                    f = False
                    break
            if f == True:
                pass
            else:
                break
    if f :
        ans = max(ans,honest(pat))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
xy_list=[]
for i in range(n):
    a=int(input())
    xy=[]
    for _ in range(a):
        xy.append(list(map(int,input().split())))
    xy_list.append(xy)
ans=0
for i in range(2**n):
    i_2=format(i,"0"+str(n)+"b")
    flag=1
    for j in range(n):
        if i_2[j]=="1":
            for x,y in xy_list[j]:
                if i_2[x-1]!=str(y):
                    flag=0
    if flag==1: 
        ans=max(ans,i_2.count("1"))
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    all_remark = []
    for i in inputs:
        all_remark.append(list(map(string_to_int, i)))
    n = len(all_remark)
    max_pattern = 2**n

    max_shojiki = 0
    for p in range(max_pattern):
        bits = list(bin(p)[2:])
        bits = ['0' for i in range(n-len(bits))] + bits
        shojiki = 0
        for b in bits:
            if b == '1':
                shojiki += 1

        for i, remarks in enumerate(all_remark):
            is_possible = True
            if bits[i] == '1':
                for r in remarks:
                    target = r[0]
                    w = r[1]
                    if bits[target - 1] != str(w):
                        is_possible = False
                        break
                if is_possible is False:
                    break
        if is_possible and max_shojiki < shojiki:
            max_shojiki = shojiki
    return max_shojiki


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    N = int(input())
    arg = []
    for i in range(N):
        A = int(input())
        arg.append(inputs(A))
    ret = solve(arg)
    print(ret)

Submission status: Accepted

Solution code:
#入力
n = int(input())
al = []
lll = []
for _ in [0]*n:
  al.append(int(input()))
  ll = [list(map(int,input().split())) for _ in [0]*al[-1]]
  lll.append(ll)
  
#正直な人の証言がすべてあっていればよい。
#ループ用リスト作成 0が不親切, 1が正直
katei = []
for i in range(2**n):
  l = []
  for j in range(n-1,-1,-1):
    if i>= 2**j:
      l.append(1)
      i -= 2**j
    else:
      l.append(0)
  katei.append(l)
#処理
ans = 0
for i in range(len(katei)):
  flag = True
  for j in range(n):
    if katei[i][j] == 1: #注目する人は正直だと仮定した人
      for l in lll[j]:#正直だと仮定した人の証言情報をループ
        if l[1] != katei[i][l[0]-1]:
          flag = False
  if flag:
    ans = max(sum(katei[i]),ans)

print(ans)

Submission status: Accepted

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

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

    ans = 0
    for i in range(1<<N):
        T = []
        F = []
        for j in range(N):
            if (i>>j) & 1:
                T.append(j)
            else:
                F.append(j)
        flag = False
        for t in T:
            for x, y in X[t]:
                if y == 1:
                    if x in F:
                        flag = True
                        break
                else:
                    if x in T:
                        flag = True
                        break
            if flag:
                break
        if not flag:
            ans = max(ans, len(T))

    print(ans)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import combinations

N = int(input())
syogens = []
for i in range(N):
    a = int(input())
    syogen = []
    for j in range(a):
        x,y= map(int,input().split())
        syogen.append((x,y))
    syogens.append(syogen)
#人Aiの証言はsyogens[i]
#j番目の証言は　syogens[i][j]
# print(syogens)

for k in reversed(range(N)): #kにんの正直者がいると仮定
    # print(k)
    comb = combinations(range(N),k+1)
    # print(*comb)
    for pattern in comb: #(0,3,5,6)
        l = [-1]*N
        b=1
        syogen = []
        for i in range(N):
            if i in pattern:
                l[i] = 1
            else:
                l[i] = 0

        # print(l)
        #発言を検証していく
        for person in pattern:
            syogen = syogens[person]
            for s in syogen:
                # print(s)
                target = s[0]
                value = s[1]
                if value != l[target-1]:
                    b = 0
        if b == 1:
            print(k+1)
            exit()

print(0)

Submission status: Accepted

Solution code:
import itertools
from collections import defaultdict

def ok_bit(bit):
    for i in range(N):
        if bit[i] == 0:
            continue
        for x, y in evidence_dict[i]:
            if y != bit[x-1]:
                return False
    return True



def solver():
    for bit in reversed(bit_list):
        if ok_bit(bit):
            return bit
    return [0]

N = int(input())
evidence_dict = defaultdict(list)
A = []
for i in range(N):
    A1 = int(input())
    for j in range(A1):
        evidence_dict[i].append(list(map(int, input().split())))

L = [0, 1]
bit_list = list(itertools.product(L, repeat=N))


if __name__ == "__main__":
    ans_bit = solver()
    res = 0
    for b in ans_bit:
        if b==1:
            res+=1
    print(res)

Submission status: Accepted

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

ans = 0

for bit in range(1 << n):
    syojiki = []
    flag = True

    for i in range(n):
        # フラグが立っていれば a に、なければ b に乗せる
        if bit & (1 << i):
            syojiki.append(1)
        else:
            syojiki.append(0)

    for i in range(n):
        for j in b[i]:  # 証言内容
            if syojiki[i] and syojiki[j[0]] != j[1]:
                flag = False
    if flag:
        ans = max(ans, sum(syojiki))

print(ans)

Submission status: Accepted

Solution code:
import itertools
def main():
    N = int(input())
    d = {}
    for i in range(N):
        a = int(input())
        d[i] = []
        for _ in range(a):
            x, y = map(int, input().split())
            d[i].append((x-1,y))
    for i in range(N+1):
        for j in itertools.combinations(range(N), i):
            for k in range(N):
                a = 0
                if k not in j:
                    for x, y in d[k]:
                        if y == 0 and x not in j:
                            a += 1
                        if y == 1 and x in j:
                            a += 1
                if a > 0:
                    break
            else:
                return N - i
print(main())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    A=[0]*N
    x=[[] for _ in range(N)]
    y=[[] for _ in range(N)]
    for i in range(N):
        A[i]=int(input())
        x[i]=[0]*A[i]
        y[i]=[0]*A[i]
        for j in range(A[i]):
            X,Y=map(int,input().split())
            x[i][j],y[i][j]=X-1,Y
    ans=0
    for i in range(2**N):
        l=[-1]*N
        f=True
        for j in range(N):
            if (i >> j) & 0b1 == 1:
                if l[j] != 0:
                    l[j]=1
                    for k in range(A[j]):
                        if l[x[j][k]] == -1:
                            if y[j][k] == 1 and (i >> x[j][k]) & 0b1 == 1:
                                l[x[j][k]] = y[j][k]
                            elif y[j][k] == 0:
                                l[x[j][k]] = y[j][k]
                            else:
                                f=False
                                break
                        else:
                            if l[x[j][k]] != y[j][k]:
                                f=False
                                break
                    if f==False:
                        break
                else:
                    f=False
                    break
        if f==True:
            c=0
            for i in l:
                c+=1 if i==1 else 0
            ans=max(ans,c)
    print(ans)
                

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
people = [[] for _ in range(N)]
for i in range(N):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        x -= 1
        people[i].append([x, y])
ans = 0  # だんだん更新されていく
for mask in range(1 << N):  # 2のd乗になる
    binary_status = []

    for i in range(N):
        binary_status.append((mask >> i) & 1)
    # 矛盾なく考えていきたい
    flag = True
    for i in range(len(binary_status)):
        if binary_status[i] == 0:
            continue
        for j in range(len(people[i])):
            # print("hoge")
            # print(people[i][j])
            # print(binary_status)

            if binary_status[people[i][j][0]] != people[i][j][1]:
                flag = False
    if flag:
        if sum(binary_status) > ans:
            ans = sum(binary_status)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
syougen = [[] for i in range(N)]
for i in range(N):
    a_tmp = int(input())
    for j in range(a_tmp):
        [x, y] = list(map(int,input().split()))
        syougen[i].append([x-1,y])
ans = 0
for i in range(2**N):
    data = [0]*N
    for j in range(N):
        if ((i >> j) & 1):
            data[j] = 1
    flag = True
    for k in range(N):
        if data[k] == 1:
            for l in range(len(syougen[k])):
                x = syougen[k][l][0]
                y = syougen[k][l][1]
                if data[x] != y:
                    flag = False
    if flag:
        ans = max(ans,sum(data))
print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N = int(input())
from itertools import product
l=list(product([1,0],repeat=N))
L=[]
for i in range(N):
    A=int(input())
    for j in range(A):
        x,y=map(int,input().split())
        L.append([x,y,i+1])
a=0
for i in l:
    t=N
    for j in L:
        if i[j[2]-1]==1 and j[1]!=i[j[0]-1]:
            break
    else:
        if a<i.count(1):
            a=i.count(1)
print(a)

Submission status: Accepted

Solution code:
N=int(input())

alist=[]
for i in range(N):
  ai=int(input())
  ailist=[]
  for j in range(ai):
    xij,yij=map(int,input().split())
    if yij==0:
      ailist.append((xij-1,False))
    else:
      ailist.append((xij-1,True))
    
  alist.append(ailist)

#print(alist)
answer=0
for i in range(2**N):
  bin_str=format(i, '0'+str(N)+'b')
  dlist=list(map(int,list(bin_str)))
  #print(dlist)
  
  contra=False
  for j in range(N):
    #j in honest
    if dlist[j]==1:
      for aj in alist[j]:
        x,y=aj
        if y and dlist[x]==0:
          contra=True
          break
        elif not y and dlist[x]==1:
          contra=True
          break
    if contra:
      break
  else:
    #print(dlist)
    answer=sum(dlist)

print(answer)

Submission status: Accepted

Solution code:
N=int(input())
X=[[] for _ in range(N)]
Y=[[] for _ in range(N)]
for i in range(N):
    m=int(input())
    for j in range(m):
        x,y=map(int,input().split())
        X[i].append(x-1)
        Y[i].append(y)
max_=0
for i in range(2 ** N):
    op = [0] * N  
    for j in range(N):
        if ((i >> j) & 1):
            op[N - 1 - j] = 1  
    #print(op)
    exit=False
    for j in range(N):
        if op[j] == 1:
            for k in range(len(X[j])):
                if Y[j][k]!=op[X[j][k]]:
                    #print("no",j,k)
                    exit=True
                    break
        if exit:
            break
    else:
        #print("yes",j,k)
        max_=max(max_,sum(op))
print(max_)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
a=[]
xy=[]
for i in range(n):
    tmp=int(input())
    a.append(tmp)
    tmp2=[list(map(int,input().split())) for i in range(tmp)]
    xy.append(tmp2)
bit=2**n
ans=0
# print(a)
for i in range(bit):
    flag=1
    for j in range(n):
        if i&(1<<j)!=0:
            for k in range(a[j]):
                if (i>>xy[j][k][0]-1)&1!=xy[j][k][1]:
                    flag=0
    # print(i,flag)
    if flag==1:
        tmp=0
        for j in range(n):
            if i&(1<<j)!=0:
                tmp+=1
        ans=max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
g = [[-1] * n for _ 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 m in range(2 ** n):
	f = 1
	for i in range(n):
		for j in range(n):
			if g[i][j] < 0:
				continue
			if (1 << i) & m:
				if g[i][j] != int((1 << j) & m > 0):
					f = 0
					break
	if f:
		ans = max(ans, bin(m).count("1"))
print(ans)

Submission status: Accepted

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

ans = 0
for p in range(2 ** n + 1):
    candidate = 0
    friends = {}
    for i in range(n):
        if p & (1 << i) > 0:
            friends[i] = 1
        else:
            friends[i] = 0

    valid = True
    for i in range(n):
        if p & (1 << i) > 0:
            friendly = True
            for x, y in xy[i]:
                if friends[x] != y:
                    friendly = False

            if friendly:
                candidate += 1
            else:
                valid = False
                break
    if valid:
        ans = max(ans, candidate)

print(ans)

Submission status: Accepted

Solution code:
#C
N = int(input())
XY = []
for i in range(N):
    a = int(input())
    kari = []
    for j in range(a):
        kari.append(list(map(int,input().split())))
    XY.append(kari)
    
N2 = 2**N
ans = 0
for i in range(N2):
    b = bin(i)
    b = b.lstrip("0b")
    while len(b) < N:
        b = "0"+b
        
    flag = 0
    boo = [-1]*N
    for j in range(N):
        if b[j] == "1":
            if boo[j] == 0:
                flag = 1
                break
            else:
                boo[j] = 1
                for xy in XY[j]:
                    x,y = xy
                    if boo[x-1] == -1:
                        boo[x-1] = y
                    else:
                        if boo[x-1] != y:
                            flag = 1
                            break
        else:
            if boo[j] == 1:
                flag = 1
                break
            else:
                boo[j] = 0
    if flag == 0:
        kari = 0
        for bo in boo:
            if bo == 1:
                kari+=1
        ans = max(ans,kari)
    
print(ans)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
An = []
for _ in range(N):
    A = int(input())
    tmp = []
    for _ in range(A):
        tmp.append(list(map(int,input().split(' '))))
    An.append(tmp)

seq = []
for i in range(N):
   seq.append(i) 
max_num = 0
for i in range(N):
    comb_list = list(itertools.combinations(seq,i))
    for comb in comb_list:
        tmp = [-1]*N
        flag = True
        for i2 in range(N):
            if i2 in comb:
                continue
            for xy in An[i2]:
                if tmp[xy[0]-1] == -1:
                    tmp[xy[0]-1] = xy[1]
                else:
                    if tmp[xy[0]-1] != xy[1]:
                        flag = False
        for i2 in range(N):
            if i2 in comb: #`usotuki`
                if tmp[i2] == 1:
                    flag = False
            else:
                if tmp[i2] == 0:
                    flag = False
        if flag:
            max_num = N - i
    if max_num > 0:
        break
print(max_num)

Submission status: Accepted

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

b=[]
for k in range(2**n):
  b.append(format(k,'0'+str(n)+'b'))
ans=[]
for i in range(2**n):
  ct1=0
  ct2=0
  for j in range(n):
    if b[i][j]=='1':
      ct1+=1
      ct=0
      for k in range(len(l[j])):
        if int(b[i][l[j][k][0]-1])!=l[j][k][1]:
          ct+=1
      if ct==0:
        ct2+=1
    else:
      ct2+=1
  if ct2==n:
    ans.append(ct1)
print(max(ans))

Submission status: Accepted

Solution code:
def c_honest_or_unkind_2():
    N = int(input())
    Answers = []
    for _ in range(N):
        a = int(input())
        Answers.append([[int(i) for i in input().split()] for j in range(a)])

    # print(Answers)
    ret = -1
    for bits in range(1 << N):
        honests = set()
        unkinds = set()
        for k in range(N):
            if (bits >> k) & 1 == 1:
                honests.add(k)
            else:
                unkinds.add(k)
        # print(honests, unkinds, end=' ')
        is_contradict = False
        for k, answer in enumerate(Answers):
            if k not in honests:
                continue

            for x, y in answer:
                x -= 1
                if (y == 1 and x in unkinds) or (y == 0 and x in honests):
                    # print(k, x, y)
                    is_contradict = True
                    break
            if is_contradict:
                break
        else:
            # print(honests)
            ret = max(ret, len(honests))
    return ret

print(c_honest_or_unkind_2())

Submission status: Accepted

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

to_bit = [1 << i for i in range(n)]
from_bit = {1 << i: i for i in range(n)}
ans = 0
for check in range(1 << n):
    b = check
    flag = True
    while b:
        bit = b & -b
        i = from_bit[bit]
        for x, y in testimonies[i]:
            if (check >> x) & 1 != y:
                flag = False
                break
        if not flag:
            break
        b ^= bit

    if flag:
        ans = max(ans, bin(check).count('1'))

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N = int(input())
A = [[] for _ in range(N)]
for i in range(N):
    na = int(input())
    for j in range(na):
        x, y = map(int, input().split())
        A[i].append((x-1, y))
ans = 0
for pat in product((0, 1), repeat=N):
    num = pat.count(1)
    mujun = False
    for i, shogen in enumerate(A):
        if pat[i] == 0:
            continue
        for s in shogen:
            x, y = s
            if pat[x] != y ^ (1 - pat[i]):
                mujun = True
                break
        if mujun:
            break
    if mujun:
        continue
    ans = max(ans, num)
print(ans)

Submission status: Accepted

Solution code:
import math

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def bitlist(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

#a = list(map(int, input().split()))

n = int(input())
ms = []
say = []
for i in range(n):
    m = int(input())
    ms.append(m)
    say.append([])
    for j in range(m):
        p,q = list(map(int, input().split()))
        say[i].append([p,q])

#print(say)
ans=0

for i in range(2**n):
    flag = 1
    nowbit = bitlist(i,n)
    total = sum(nowbit)
    for j in range(n):
        for k in range(ms[j]):
            #print(j,k)
            #print(nowbit)
            if(nowbit[j]==1):
                if(nowbit[say[j][k][0]-1]!=say[j][k][1]):
                    flag=0
    if(flag==1 and ans<total):
        ans=total
#print()

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict 

n=int(input())
yes=defaultdict(list)
no=defaultdict(list)
for i in range(1,n+1):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        if y==0:
            no[i].append(x)
        else:
            yes[i].append(x)

maxi=0 
tot=(1<<n)
def ok(curr):
    for a  in range(1,n+1):
        if a in curr:
            for z in yes[a]:
                if z not in curr:
                    return 0 
            for z in no[a]:
                if z in curr:
                    return 0
    return 1 
#print(no)

for i in range(tot):
    curr=[]
    for j in range(n):
        if i&(1<<j):
            curr.append(j)
    curr=[i+1 for i in curr]
    if ok(curr):
       # print(curr)
        maxi=max(maxi,len(curr))
print(maxi)

Submission status: Accepted

Solution code:
N = int(input())

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

ans = 0
for state in range(2 ** N):
    # print("#", '{:b}'.format(state))
    ans_tmp = 0
    state_tmp = state
    honest = [None] * N
    valid = True
    state_bin = [(state >> i) % 2 for i in range(N)]
    for i in range(N):
        if state_bin[i] > 0:
            xy_tmp = xy[i]
            for xj, yj in xy_tmp:
                if honest[xj - 1] == None:
                    honest[xj - 1] = yj
                elif honest[xj - 1] != yj:
                    valid = False
                    break
            ans_tmp += 1
        if valid == False: break
    if valid == False: continue
    #
    for i in range(N):
        if state_bin[i] == 1 and honest[i] == 0:
            valid = False
            break
        if state_bin[i] == 0 and honest[i] == 1:
            valid = False
            break
    #
    if valid:
        # print("##", honest)
        ans = max(ans, ans_tmp)

print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n = ri()
ls = []
for _ in range(n):
    a = ri()
    s0 = set()
    s1 = set()
    for _ in range(a):
        i, b = ril()
        if b == 0:
            s0.add(i - 1)
        else:
            s1.add(i - 1)
    ls.append((s0, s1))

res = 0
for b in range(1, 2**n):
    b = bin(b)[2:].rjust(n, '0')
    count = b.count('1')
    if count <= res:
        continue
    ss0 = set()
    ss1 = set()
    t0 = set()
    t1 = set()
    for i, c in enumerate(b):
        s0, s1 = ls[i]
        if c == '1':
            t1.add(i)
            ss0.update(s0)
            ss1.update(s1)
        else:
            t0.add(i)
    if ss0 & ss1 or ss0 & t1 or ss1 & t0:
        continue
    res = count
print(res)

Submission status: Accepted

Solution code:
N=int(input())
def bi(num):
  ls_bi=[0 for _ in range(N+1)]
  for bi_i in range(N):
    if (2**bi_i)&num>0:
      ls_bi[bi_i]=1
      ls_bi[N]+=1
  return ls_bi

syogen=[[-1 for _  in range(N)] for _ in range(N)]

for i in range(N):
  Ai=int(input())
  for j in range(Ai):
    x,y=[int(s) for s in input().split()]
    syogen[i][x-1]=y
#print(syogen)
ans=[]
for n in range(2**N):
  ls=bi(n)
  flag=1
  for i in range(N):
    if ls[i]==1:
      for j in range(N):
        if ls[j]==syogen[i][j] or syogen[i][j]==-1:
          continue
        else:
     #     print(ls,i,j)
          flag=0
          break
    if flag==0:
      break
  else:
    ans.append(ls[N])
print(max(ans))

Submission status: Accepted

Solution code:
import itertools

n = int(input())
tt = [[] for _ in range(n + 1)]
for i in range(n ):
	j = int(input())
	for _ in range(j):
		a, b = list(map(int, input().split()))
		tt[i].append([a - 1, b])

#print(tt)
max_ans = 0
for xx in list(itertools.product([0, 1], repeat = n)):
	flg = 1
	for i in range(n):
		x = xx[i]
		if x == 1:
			for t in tt[i]:
				if xx[t[0]] != t[1]:
					flg = 0
					break
	if flg == 1:
		#print(xx)
		max_ans = max(max_ans, sum(xx))

print(max_ans)

Submission status: Accepted

Solution code:
n = int(input())
a = []
s = []
for i in range(n):
  _a = int(input())
  a.append(_a)
  s.append([list(map(int, input().split())) for j in range(_a)])
bins = []
for i in range(2**n):
  binary = bin(i)[2:]
  binary = '0' * (n-len(binary)) + binary
  bins.append(list(map(int,list(binary))))

ans = 0
for binlist in bins:
  for i, p in enumerate(binlist):
    if p == 1:
      cnt = 0
      for state in s[i]:
        if binlist[state[0]-1] != state[1]:
          break
        else:
          cnt += 1
      if cnt < len(s[i]):
        break
  else:
    ans = max(ans, len(list(filter(lambda x: x==1, binlist))))
print(ans)