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: Wrong Answer

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]
            if (j in honest and value < 0) or (j not in honest and value > 0 and value % INF != 0):
                flag = False
                break
        if flag:
            ans = max(ans, len(honest))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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):
            if (j in honest and pick[j] < 0) or (j not in honest and pick[j] > 0):
                flag = False
                break
        if flag:
            ans = max(ans, len(honest))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    N = int(input())
    testimony = np.zeros((N, N), dtype=np.int32)
    for i in range(N):
        A = int(input())
        INF = 10 ** 2
        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):
        member = set()
        pick = np.zeros(N, dtype=np.int32)
        for i in range(N):
            if bit & (1 << i):
                member.add(i)
                pick += testimony[i, :]
        flag = True
        for j in range(N):
            if j in member and pick[j] < 0:
                flag = False
                break
            if j not in member and pick[j] > 0:
                flag = False
                break
        if flag:
            ans = max(ans, len(member))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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[1] 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: Wrong Answer

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: Wrong Answer

Solution code:
n = int(input())
xy = []
for i in range(n):
    a = int(input())
    for j in range(a):
        x_,y_ = map(int,input().split())
        xy.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:
                if x==j and y!=1:
                    flag = 1 
                    break
    if flag ==0:
        ans = max(ans, bin(i)[2:].count("1"))
print(ans)

Submission status: Wrong Answer

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] == 1:
                is_ok = False
                break
    if is_ok:
        rst = max(rst, len(honest_ls))
print(rst)

Submission status: Wrong Answer

Solution code:
import numpy as np

n = int(input())
li = [np.full(n, -1, dtype=np.int)]*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: Wrong Answer

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 = 1
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:
            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
    if c == d.count(1):
        num = c
    ans = max(num, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

ans = 0
for i in range(2**n):
    f = 0
    t = [1,0,0]
    s = 0
    for j in range(n):
        if i>>j & 1:
            if f==0:
                t = li[j]
                c = li[j]
                f = 1
            else:
                t = t ^ li[j]
                if sum(t)!=0:
                    break
    b = str(bin(i))
    for c in b:
        if c=="1":
            s += 1
    if sum(t)==0:
        ans = max(ans, s)
print(ans)

Submission status: Wrong Answer

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:
            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
    if c == d.count(1):
        num = c
    ans = max(num, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def read(): return sys.stdin.readline() # 標準入力

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) ^ 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: Wrong Answer

Solution code:
N = int(input())
ls1 = []
for i in range(N):
    A = int(input())
    ls2 = []
    for i in range(A):
        x, y = map(int,input().split())
        ls2.append([x,y])
    ls1.append(ls2)
ans = 0
f = True
for i in range(2**N):
    for j in range(N):
        if (i>>j&1):
            for k in ls1[j]:
                f = True
                if (i >>(k[0] - 1) &1) == (k[1]&1):
                    continue
                else:
                    f = False
                    break
            if f == False:
                break
    if f:
        ans = max(ans,bin(i).count('1'))    
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
ls1 = []
for i in range(N):
    A = int(input())
    ls2 = []
    for i in range(A):
        x, y = map(int,input().split())
        ls2.append([x,y])
    ls1.append(ls2)
ans = 0
f = True
for i in range(2**N):
    for j in range(N):
        if (i>>j&1):
            for k in ls1[j]:
                if (i >>(k[0] - 1) &1) == (k[1]&1):
                    f = True
                    continue
                else:
                    f = False
                    break
            if f == False:
                break
    if f:
        ans = max(ans,bin(i).count('1'))    
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
ll = [] #リストのリスト
for i in range(N):
    l = [None]*N
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        l[x-1] = y
    ll.append(l)
ans = 0
for i in range(1, 2**N):
    temp = [None]*N
    b = 1
    use = [0]*N
    for j in range(N):
        if i>>j&1:
            use[j] = 1
            for k in range(N):
                if temp[k]==None:
                    temp[k] = ll[j][k]
                elif ll[j][k]==None:
                    continue
                else:
                    b = 0
    if not b:
        continue
    c = 1
    for j in range(N):
        if temp[j]==1 and use[j]==0:
            c = 0
        elif temp[j]==0 and use[j]==1:
            c = 0
    if c:
        p = use.count(1)
        ans = max(p, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
ans = 0
A = []
dic = defaultdict(list) 
for i in range(N):
    a = int(input())
    A.append(a)
    for j in range(a):
        x, y = map(int, input().split())
        dic[i+1].append([x, y+1])

        

for i in range(1, N+1):# iが正直者のとき
    b = 1
    temp = 0
    l = [-1]*N
    l[i-1] = 1
    for t in dic[i]:
        l[t[0]-1] = t[1]-1
    for j, val in enumerate(l):
        if val==1:
            for s in dic[j+1]:
                if l[s[0]-1]==-1:
                    l[s[0]-1] = s[1]-1
                if l[s[0]-1] != s[1]-1:
                    b = 0
                    break
                
    if b:
        for j in l:
            if j==1:
                temp+=1
        ans = max(ans, temp)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
X = []
Y = []
for i in range(n):
    a.append(int(input()))
    x = []
    y = []
    for j in range(a[i]):
        xj, yj = map(int, input().split(' '))
        x.append(xj)
        y.append(yj)
    X.append(x)
    Y.append(y)
ans = 0
for k in range(2**n):
    cnt_truth = 0
    cnt_proover = 0
    for i in range(n):
        cnt_proof = 0
        if (k >> i)&1:
            cnt_truth += 1
            for j in range(a[i]):
                if ((k >> (X[i][j]-1))&1) == Y[i][j]:
                    cnt_proof += 1
                if cnt_proof == a[i]:
                    cnt_proover += 1

    if (cnt_proover == cnt_truth) and (ans < cnt_truth):
        ans = cnt_truth
print(ans)

Submission status: Wrong Answer

Solution code:
# author:  Taichicchi
# created: 16.09.2020 23:28:44

import sys
N = int(input())
A = []
ls = []
for i in range(N):
    A.append(int(input()))
    l = []
    for a in range(A[-1]):
        l.append(list(map(int, input().split())))
    ls.append(l)

ans = 0

for i in range(2 ** N):
    tf = [0 for _ in range(N)]
    for j in range(N):
        if i >> j & 1:
            tf[j] = 1

    for j in range(N):
        for a in range(A[j]):
            if (tf[j] & (tf[ls[j][a][0] - 1] != ls[j][a][1])) | ((1 - tf[j]) & (tf[ls[j][a][0] - 1] == ls[j][a][1])):
                break
        else:
            continue
        break
    else:
        ans = max(ans, sum(tf))


print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

n=int(input())

lst=[[] for i in range(n)] 

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

ans=0


for xxx in itertools.product(range(2),repeat=n):
    table=[[] for i in range(n)]
    for j in range(n):
        if xxx[j]==1:
            for k in lst[j]:
                table[k[0]].append(k[1])
    
    flag=True

    for j in range(n):
        if xxx[j]==1:
            if 0 in table[j]:
                flag=False
        
        else:
            if 1 in table[j]:
                flag=False
    
    if not flag:
        continue

    ans=max(ans,xxx.count(1))



print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())

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

ans=0

for h in range(2**N):
	flag=0
	cnt=0
	l=[0]*N
	for g in range(N):
		if h>>g &1:
			l[g]=1
	#print(l)
	for gg in range(N):
		if l[gg]==1:
			temp_=syogen[g]
			for n in range(temp_[0]):
				if l[temp_[1][n][0]]==temp_[1][n][1]:
					continue
				else:
					flag=1
					break
		if flag==1:
			break
		elif flag==0 and gg==N-1:
			#print(bin(h))
			ans=max(ans,sum(l))

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
x=[]
for _ in range(n):
    A=int(input())
    X=[list(map(int,input().split())) for _ in range(A)]
    a.append(A)
    x.append(X)
ans=0

for i in range(2**n):
    tmp=[0]*n
    for j in range(n):
        if (i>>j)&1:
            tmp[j]=1
    for k in range(n):
        if a[k]==0:
            continue
        for h in range(a[k]):
            hito=x[k][h][0]-1
            singi=x[k][h][1]
            if tmp[k]==1:
                if tmp[hito]!=singi:
                    break
            else:
                if tmp[hito]==singi:
                    break
        else:
            continue
        break
    else:
        if a[k]!=0:
            ans=max(ans,sum(tmp))

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
x=[]
for _ in range(n):
    A=int(input())
    X=[list(map(int,input().split())) for _ in range(A)]
    a.append(A)
    x.append(X)
ans=0

for i in range(2**n):
    tmp=[0]*n
    for j in range(n):
        if (i>>j)&1:
            tmp[j]=1
    for k in range(n):
        for h in range(a[k]):
            if a[k]==0:
                continue
            hito=x[k][h][0]-1
            singi=x[k][h][1]
            if tmp[k]==1:
                if tmp[hito]!=singi:
                    break
            else:
                if tmp[hito]==singi:
                    break
        else:
            continue
        break
    else:
        ans=max(ans,sum(tmp))

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
x=[]
for _ in range(n):
    A=int(input())
    X=[list(map(int,input().split())) for _ in range(A)]
    a.append(A)
    x.append(X)
ans=0

for i in range(2**n):
    tmp=[0]*n
    for j in range(n):
        if (i>>j)&1:
            tmp[j]=1
    for k in range(n):
        if a[k]==0:
            continue
        for h in range(a[k]):
            hito=x[k][h][0]-1
            singi=x[k][h][1]
            if tmp[k]==1:
                if tmp[hito]!=singi:
                    break
            else:
                if tmp[hito]==singi:
                    break
        else:
            continue
        break
    else:
        ans=max(ans,sum(tmp))

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
x=[]
for _ in range(n):
    A=int(input())
    X=[list(map(int,input().split())) for _ in range(A)]
    a.append(A)
    x.append(X)
ans=0

for i in range(2**n):
    tmp=[0]*n
    for j in range(n):
        if (i>>j)&1:
            tmp[j]=1
    for k in range(n):
        for h in range(a[k]):
            hito=x[k][h][0]-1
            singi=x[k][h][1]
            if tmp[k]==1:
                if tmp[hito]!=singi:
                    break
            else:
                if tmp[hito]==singi:
                    break
        else:
            continue
        break
    else:
        ans=max(ans,sum(tmp))

print(ans)

Submission status: Wrong Answer

Solution code:
# 証言テーブルを初期化する
# 最大15人なので 15x15 のテーブルを準備する
# 1人が証言できる最大は15
# -1 は証言なし
# x軸: 人、y軸: 証言
testimonys = [[-1]*15]*15

n = int(input())
for i in range(n):
    for _ in range(int(input())):
        man, testimony = map(int, input().split())
        testimonys[i][man-1] = testimony

# N人が正直者または正直者でないというすべての状態を調べる（bit全探索) 
ans = 0
for i in range(2**n):
    # どこがonかを判定するための領域
    # 1011 の時
    # d = [1, 1, 0, 1]
    d = [0]*n
    for j in range(n):
        if (i>>j)&1: 
            d[j] = 1

    ok = True
    for j in range(n):
        if d[j]:    
            for k in range(n):
                if testimonys[j][k] == -1: continue
                if testimonys[j][k] == d[k]: ok = False
    # バイナリーにして 1 をカウントする
    # >>> bin(3)
    # '0b11'
    # >>> bin(3)[2:]
    # '11'
    # >>> bin(3)[2:].count('1')
    # 2
    if ok:
        ans = max(ans, bin(i)[2:].count('1')) 
print(ans)

Submission status: Wrong Answer

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


for i in range(n):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split())
        if y == 1:
            statement[i].append([x-1, True])
        if y == 0:
            statement[i].append([x-1, False])

cnt = 0
for bit in range(2**n):
    honest = []
    for i in range(n):
        if (bit >> i) & 1:
            honest.append(i)
    flag = True
    for j in range(len(statement)):
        if j in honest:
            for k, TF in statement[j]:
                if k in honest:
                    if not TF:
                        flag = False
                        break
                else:
                    if TF:
                        flag = False
                        break
        else:
            for k, TF in statement[j]:
                if k in honest:
                    if TF:
                        flag = False
                        break
                else:
                    if not TF:
                        flag = False
                        break
    if flag:
        cnt = max(cnt, len(honest))
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())

list_a = []
testimonies = []
answer = 0
flag = True

for i in range(n):
	testimony = []
	a = int(input())
	list_a.append(a)
	for j in range(a):
		testimony.append(list(map(int,input().split())))
	testimonies.append(testimony)

for i in range(1 << (n-1)): # 部分和の計算　i=2は"0b10"  正直者の組み合わせ
	result = 0
	for j in range(n): # 各組み合わせを確認
		if i & (1 << (j)): #trueだった場合はj番目は正直者
			result += 1
			for k in range(list_a[j]): #正直者の証言を確認
				if not i & testimonies[j][k][1] << (testimonies[j][k][0]-1): # 虚偽の証言をしている時
					flag = False
					break
	if flag == True:
		if answer < result:
			answer = result
	else:
		flag = True


print(answer)

Submission status: Wrong Answer

Solution code:
N = int(input())
XY_list = [[] for _ in range(N)]
for i in range(N):
    num = int(input())
    for j in range(num):
        person, state = map(int, input().split())
        XY_list[i].append([person - 1, state])
ans = 0
for i in range(1 << N):
    bool = True
    for j in range(N):
        if (i >> j) & 1 == 1:
            for person, state in XY_list[j]:
                if (i >> person) & 1 != state:
                    bool = False
                    break
        else:
            for person, state in XY_list[j]:
                if (i >> person) & 1 == state:
                    bool = False
                    break
    if bool:
        ans = max(ans, bin(i)[2:].count("1"))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

S_list = [[] for _ in range(N)]
for i in range(N):
    A = int(input())
    if A == 0:
        S_list.append([])
    else:
        for a in range(A):
            S_list[i].append(list(map(int, input().split())))
ans = 0
for i in range(1 << N):
    A_list = [0 for _ in range(N)]
    for j in range(N):
        if (i >> j) & 1 == 1:
            A_list[j] = 1

    bool = True
    for a in range(len(A_list)):
        if S_list[a] == []:
            continue
        for s in range(len(S_list[a])):
            if A_list[a] == 0:
                if A_list[S_list[a][s][0]-1] == S_list[a][s][1]:
                    bool = False
                    break
            else:
                if A_list[S_list[a][s][0]-1] != S_list[a][s][1]:
                    bool = False
                    break
    if bool:
        ans = max(ans, sum(A_list))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

S_list = [[] for _ in range(N)]
for i in range(N):
    A = int(input())
    if A == 0:
        S_list.append([])
    else:
        for a in range(A):
            S_list[i].append(list(map(int, input().split())))
ans = 0
for i in range(1 << N):
    A_list = [0 for _ in range(N)]
    for j in range(N):
        if (i >> j) & 1 == 1:
            A_list[j] = 1

    bool = True
    for a in range(len(A_list)):
        for s in range(len(S_list[a])):
            if A_list[a] == 0:
                if A_list[S_list[a][s][0]-1] == S_list[a][s][1]:
                    bool = False
                    break
            else:
                if A_list[S_list[a][s][0]-1] != S_list[a][s][1]:
                    bool = False
                    break
    if bool:
        ans = max(ans, sum(A_list))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

ans = 0
for i in range(1 << N):
    A_list = [0 for _ in range(N)]
    for j in range(N):
        if (i >> j) & 1 == 1:
            A_list[j] = 1

    bool = True
    for a in range(len(A_list)):
        for s in range(len(S_list[a])):
            if A_list[a] == 0:
                if A_list[S_list[a][s][0]-1] == S_list[a][s][1]:
                    bool = False
                    break
            else:
                if A_list[S_list[a][s][0]-1] != S_list[a][s][1]:
                    bool = False
                    break
    if bool:
        ans = max(ans, sum(A_list))
print(ans)

Submission status: Wrong Answer

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

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

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

        if x == y:
            return

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

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

    # 指定要素を含むグループのサイズ
    def size(self, x):
        return -self.parents[self.find(x)]

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

    # 指定要素を含むグループの全要素リスト
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

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

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

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

n = int(input())

lis = [[-1 for _ in range(n)] for _ in range(n)]

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

flg = False
uf  = UnionFind(n)

seen = [-1]*n

for i in range(n):
    for j in range(i+1,n):
        if seen[j]==1:
            continue
        for k in range(n):
            if lis[i][k]==-1 or lis[j][k]==-1:
                continue
            elif lis[i][k] != lis[j][k]:
                flg = True
                seen[j] = 1
                break
            else:
                continue
        if flg == False and seen[j]:
            uf.union(i,j)
        else:
            flg = False

print(max(uf.size(0), n-uf.size(0)))

Submission status: Wrong Answer

Solution code:
N=int(input())
testimonies=[]

for i in range(N):
  A=int(input())
  testimony=[]
  for j in range(A):
    testimony.append(list(map(int,input().split())))
    testimony[-1][0]-=1
  testimonies.append(testimony)

ans=0
for i in range(2**N):
  isContradiction=False
  for j in range(N):
    if not i&1<<j:continue
    for x,y in testimonies[j]:
      if i&1<<x:x=1
      if not x==y:
        isContradiction=True
        break
  if not isContradiction:
    ans=max(ans,bin(i).count("1"))
print(ans)

Submission status: Wrong Answer

Solution code:
def digitSum(n):
    s = str(bin(n))
    s = s[2:]
    array = list(map(int, s))
    return sum(array)
N = int(input())
A = []
X = []
Y = []
res = 0
for i in range(N):
    a = int(input())
    A.append(a)
    X_temp = []
    Y_temp = []
    for j in range(a):
        x,y = map(int,input().split())
        X_temp.append(x)
        Y_temp.append(y)
    X.append(X_temp)
    Y.append(Y_temp)
for i in range(1 << N):
    judge = True
    for j in range(N):
        if (i >> j) & 1:#もしAjが正直者だったら
            for k in range(A[j]):
                if (i >> X[j][k]-1) & 1 != Y[j][k]:
                    judge = False
        else:
            for k in range(A[j]):
                if (i >> X[j][k]-1) & 1 == Y[j][k]:
                    judge = False
    if judge:
        res = max(res,digitSum(i))
print(res)

Submission status: Wrong Answer

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

maxH=0
for mask_i in range(1<<N):
  
  H=[0]*(N+1)
  for n in range(N):
    if mask_i>>n&1:
      H[n+1]=1
  #print(H[1:])
  
  for n in range(1,N+1):
    ok=True
    if H[n]==1:
      for x,y in XY[n]:
        if H[x]!=y:
          ok=False
          break
  if ok:
    maxH=max(maxH,sum(H))

print(maxH)

Submission status: Wrong Answer

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

maxH=0
for mask_i in range(2<<(N-1)):
  H=[0]*(N+1)
  for n in range(N):
    if mask_i>>n&1:
      H[n+1]=1
  #print(H[1:])
 
  for idx,(xy) in enumerate(XY,start=1):
    for x,y in xy:
      if y==1:
        if H[idx]==1 and H[x]==1:
          continue
        else:
          break
      else:
        if H[idx]==1 and H[x]==1:
          break
    else:
      continue
    break
  else:
    maxH=max(maxH,sum(H))

print(maxH)

Submission status: Wrong Answer

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

maxH=0
for mask_i in range(2<<(N-1)):
  H=[0]*(N+1)
  for n in range(N):
    if mask_i>>n&1:
      H[n+1]=1
  #print(H[1:])
 
  for idx,(xy) in enumerate(XY,start=1):
    for x,y in xy:
      if y==1:
        if H[idx]==1 and H[x]==1:
          continue
        else:
          break
      else:
        if H[idx]==1 and H[x]==1:
          break
    else:
      continue
    break
  else:
    maxH=max(maxH,sum(H))

print(maxH)

Submission status: Wrong Answer

Solution code:
# 全探索

n=int(input())

class People:
    def __init__(self):
        self.type=None

peoples=[People() for i in range(n+1)]

def change_10to2(i):
    return format(i, '#0' + str(n + 3) + 'b')[2:]

def set_people_type(binary_list,peoples):
    for i,people in enumerate(peoples):
        if i!=0:
            people.type=binary_list[i]

def get_statement():
    shougen={}
    for i in range(1,n+1):
        ai=int(input())
        ans=[]
        for j in range(ai):
            kumi=[int(k) for k in input().split()]
            ans.append(kumi)
        shougen[str(i)]=ans
    return shougen

shougens=get_statement()

def shougen_dicide(peoples,shougens):
    for i in range(1,n+1):
        shougen=shougens[str(i)]
        for shou in shougen:
            people,type=shou
            people=int(people)
            type=str(type)
            # 正直者のとき
            if peoples[i].type=="1":
                if peoples[people].type!=type:
                    return False

            #嘘つきのとき
            else:
                if peoples[people].type==type:
                    return False
    return True



ans=0
for i in range(2**n):
    binary_list=change_10to2(i)
    set_people_type(binary_list,peoples)
    if shougen_dicide(peoples,shougens):
        ans=max(ans,binary_list.count("1"))
print(ans)