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:
def check(bag, mtx):
    shojiki = set()
    for i in range(len(bag)):
        if bag[i] == 1:
            shojiki.add(i)
    shojiki_list = list(shojiki)

    while True:
        if shojiki_list == []:
            break
        i = shojiki_list.pop()
        for j in range(len(mtx[i])):
            if mtx[i][j] == 0 and j in shojiki:
                return False
            if mtx[i][j] == 1:
                if j not in shojiki:
                    shojiki_list.append(j)
                    shojiki.add(j)
    return True


n = int(input())

mtx = [[-1] * n for i in range(n)]

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

ret = 0

for i in range(2 ** n):
    bag = []
    for j in range(n):
        if ((i >> j) & 1):
            bag.append(1)
        else:
            bag.append(0)
    if check(bag, mtx):
        if ret < sum(bag):
            ret = sum(bag)

print(ret)

Submission status: Wrong Answer

Solution code:
def check(bag, mtx):
    shojiki = set()
    for i in range(len(bag)):
        if bag[i] == 1:
            shojiki.add(i)
    shojiki_list = list(shojiki)

    while True:
        if shojiki_list == []:
            break
        i = shojiki_list.pop()
        for j in range(len(mtx[i])):
            if mtx[i][j] == 0 and j in shojiki:
                return False
            if mtx[i][j] == 1:
                if j not in shojiki:
                    shojiki_list.append(j)
                shojiki.add(j)
    return True


n = int(input())

mtx = [[-1] * n for i in range(n)]

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

ret = 0

for i in range(2 ** n):
    bag = []
    for j in range(n):
        if ((i >> j) & 1):
            bag.append(1)
        else:
            bag.append(0)
    if check(bag, mtx):
        if ret < sum(bag):
            ret = sum(bag)

print(ret)

Submission status: Wrong Answer

Solution code:
# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math
# mod = 10**9 + 7

n = int(input())

# s = deque(input())
tes = [[] 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:
            tes[j].append(x)
        else:
            tes[j].append(x*(-1))


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

m = 0
for i in range(2**n-1, -1, -1):
    is_break = False
    h = bin(i)[2:].zfill(n)
    for i, lis in enumerate(tes):
        if h[i] == '0':
            continue
        for j in lis:
            if (j > 0 and h[j-1] == '0') or (j < 0 and h[(-1)*j-1] == '1'):
                is_break = True

        if is_break:
            break

    if not is_break:
        m = max(sum(map(int, list(h))), m)


print(m)

Submission status: Wrong Answer

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)
print(evidences)

Submission status: Wrong Answer

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


ma = 0

for i in range(2 ** n):
    ok = True
    a = 0
    for j in range(n):
        if (2 ** j) & i != 0:
            a += 1
            for k in xy[j]:
                if (1 if (2 ** k[0]) & i != 0 else 0) != k[1]:
                    ok = False
    if ok:
        ma = max(ma, a)
print(ma)

Submission status: Wrong Answer

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

ma = 0

for i in range(2 ** n):
    ok = True
    a = 0
    for j in range(n):
        if (2 ** j) & i != 0:
            a+=1
            for k in xy[j]:
                if ((2 ** k[0]) & i != 0) != (k[1] == 1):
                    ok = False
    if ok:
        ma = max(ma, a)
print(ma)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
n = int(input())
q = []
def judge():
    state = False
    for i in range(n):
        if li[i] == 0:
            continue
        else:
            for j in range(len(q[i])):
                if li[q[i][j][0]] != q[i][j][1]:
                    return False
                else:
                    state = True
    if state == False:
        return False
    else:
        return True

for i in range(n):
    xy = []
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        xy.append([x-1,y])
    q.append(xy)
maxans = 0
for i in range(2**n):
    li = [0]*n
    for j in range(n):
        if (i>>j)&1:
            li[n-j-1] = 1
    if judge() == True:
        ans = sum(li)
        maxans = max(maxans,ans)
print(maxans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Mar 13 13:52:16 2020

@author: Kanaru Sato
"""

n = int(input())
a = []
proof = []

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


honest = 0

for state in range(2**n):   #状態stateを用意
    flag = 0
    for j in range(n):
        if flag == 1:
            break
        if state&(0b1<<j):    #状態stateにおいてj人目が正直か判定
            for k in range(a[j]):
                proofee = proof[j][k][0]-1
                if state&(0b1<<proofee) != proof[j][k][1]:   #j人目のK番目の証言について、stateと一致しなければ次のstateへ移る
                    flag = 1    #不成立フラグ
                    break
    if flag == 0:
        count = 0
        for i in range(n):
            count += (state>>i)&0b1
        if honest <= count:
            honest = count
print(honest)

Submission status: Wrong Answer

Solution code:
n=int(input())

M=[[] for _ in range(n)]

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

ans=0


for i in reversed(range(2**n)):
    flag=True
    S=format(i,'b')
    S=S.zfill(n)
    for j in range(n):
        if S[j]=='1':
            for k in range(len(M[j])):
                if str(M[j][k][1])!=S[M[j][k][0]-1]:
                    flag=False
        else:
            for k in range(len(M[j])):
                if str(M[j][k][1])==S[M[j][k][0]-1]:
                    flag=False
    if flag:
        ans=max(ans,S.count('1'))

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())

M=[[] for _ in range(n)]

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




for i in reversed(range(2**n)):
    flag=True
    S=format(i,'b')
    S=S.zfill(n)
    for j in range(n):
        if S[j]=='1':
            for k in range(len(M[j])):
                if str(M[j][k][1])!=S[M[j][k][0]-1]:
                    flag=False
        else:
            for k in range(len(M[j])):
                if str(M[j][k][1])==S[M[j][k][0]-1]:
                    flag=False
    if flag:
        print(S.count('1'))
        break
if not flag:
    print(0)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Mar 13 13:52:16 2020

@author: Kanaru Sato
"""

n = int(input())
a = []
proof = []

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

honest = 0

for state in range(2**n):   #状態stateを用意
    flag = 0
    for j in range(n):
        if flag == 1:
            break
        if state&(0b1<<j) == 1:    #状態stateにおいてj人目が正直か判定
            for k in range(a[j]):
                proofee = proof[j][k][0]-1
                if state&(0b1<<proofee) != proof[j][k][1]:   #j人目のK番目の証言について、stateと一致しなければ次のstateへ移る
                    flag = 1    #不成立フラグ
                    break
    if flag == 0:
        count = 0
        for i in range(n):
            count += (state>>i)&0b1
        if honest <= count:
            honest = count
print(honest)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Mar 13 13:52:16 2020

@author: Kanaru Sato
"""

n = int(input())
a = []
proof = []

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

honest = 0

for state in range(2**n):   #状態stateを用意
    flag = 0
    for j in range(n):
        if flag == 1:
            break
        if state&(1<<j) == 1:    #状態stateにおいてj人目が正直か判定
            for k in range(a[j]):
                proofee = proof[j][k][0]-1
                if state&(1<<proofee) != proof[j][k][1]:   #j人目のK番目の証言について、stateと一致しなければ次のstateへ移る
                    flag = 1    #不成立フラグ
                    break
    if flag == 0:
        count = 0
        for i in range(n):
            count += (state>>i)&1
        if honest <= count:
            honest = count
print(honest)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Mar 13 21:55:08 2020

@author: Kanaru Sato
"""

n = int(input())
a = []
proof = []

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

honest = 0

for state in range(2**n):   #状態stateを用意
    flag = 0
    for j in range(n):
        if int(bin(state>>j & 0b1),2) == 1:    #状態stateにおいてj人目が正直か判定
            for k in range(a[j]):
                if int(bin((state >> proof[j][k][0]) & 0b1),2) != proof[j][k][1]:   #j人目のK番目の証言について、stateと一致しなければ次のstateへ移る
                    flag = 1    #不成立フラグ
    if flag == 0:
        count = 0
        for i in range(n):
            count += int(bin((state >> i) & 0b1), 2)
        if honest <= count:
            honest = count

print(honest)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [0] * n
xy = [0] * n
for i in range(n):
     a[i] = int(input())
     xy[i] = [list(map(int,input().split())) for _ in range(a[i])]
memo = [0] *(2**n)
for i in range(2**n):
     flag = True
     ch = [0]*n  # あらかじめ ["-", "-", "-"] というリストを作っておく
     for j in range(n):
          if ((i >> j) & 1):
               ch[n - j - 1] = 1
     for k in range(n):
          if ch[k] == 1:
               for l in range(a[k]):
                    if xy[k][l][1] == ch[xy[k][l][0] - 1]:
                         continue
                    else:
                         flag = False
          else:
               for l in range(a[k]):
                    if xy[k][l][1] != ch[xy[k][l][0] - 1]:
                         continue
                    else:
                         flag = False
     if flag:
          memo[i] = sum(ch)
print(max(memo))

Submission status: Wrong Answer

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

for i in range(N):
    for _ in range(int(input())):
        x, y = map(int, input().split())
        if y == 1:
            true[x - 1].append(i)
        elif y == 0:
            lie[x - 1].append(i)

flag = False
for l in lie:
    if len(l) > 0:
        flag = True
if flag is False: # 不親切な人は一人もいない
    print(N)
    exit()

def detect_lier(j): # jを不親切な人とする
    if j in lier:
        return
    lier.append(j)
    for t in true[j]:
        detect_lier(t) # jを正直者だと言った人も不親切な人

ans = False
for i in range(N):
    lier = []
    detect_lier(i)
    honest = [m for m in range(N) if m not in lier]
    honest_prev = len(honest)
    while True:
        for h in honest:
            for l in lie[h]:
                detect_lier(l) # 正直者を不親切な人と言っている人は不親切な人
        honest = [m for m in range(N) if m not in lier]
        if honest_prev == len(honest): # もう正直者が減っていない
            break
        else:
            honest_prev = len(honest)
    if ans is not False:
        ans = max(ans, len(honest))
    else:
        ans = len(honest)

print(ans)

Submission status: Wrong Answer

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

for i in range(N):
    for _ in range(int(input())):
        x, y = map(int, input().split())
        if y == 1:
            true[x - 1].append(i)
        elif y == 0:
            lie[x - 1].append(i)
            
flag = False
for l in lie:
    if len(l) > 0:
        flag = True
if flag is False: # 不親切な人は一人もいない
    print(N)
    exit()

def detect_lier(j): # jを不親切な人とする
    if j in lier:
        return
    lier.append(j)
    for t in true[j]:
        detect_lier(t) # jを正直者だと言った人も不親切な人

ans = False
for i in range(N):
    lier = []
    detect_lier(i)
    honest = [m for m in range(N) if m not in lier]
    honest_prev = len(honest)
    while True:
        for h in honest:
            for l in lie[h]:
                detect_lier(l) # 正直者を不親切な人と言っている人は不親切な人
        honest = [m for m in range(N) if m not in lier]
        if honest_prev == len(honest): # もう正直者が減っていない
            break
        else:
            honest_prev = len(honest)
    # print(i, honest)
    if ans is not False:
        ans = max(ans, len(honest))
    else:
        ans = len(honest)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
info = [[] for _ in range(N)]
true =  [[] for _ in range(N)]
lie = [[] for _ in range(N)]

for i in range(N):
    for _ in range(int(input())):
        x, y = map(int, input().split())
        info[x - 1].append(y)
        if y == 1:
            true[x - 1].append(i)
        elif y == 0:
            lie[x - 1].append(i)
            
flag = False
for i in info:
    if i.count(0) > 0:
        flag = True
if flag is False: # 不親切な人は一人もいない
    print(N)
    exit()

def detect_lier(j): # jを不親切な人とする
    if j in lier:
        return
    lier.append(j)
    for t in true[j]:
        detect_lier(t) # jを正直者だと言った人も不親切な人

ans = False
for i in range(N):
    lier = []
    detect_lier(i)
    honest = [m for m in range(N) if m not in lier]
    honest_prev = len(honest)
    while True:
        for h in honest:
            for l in lie[h]:
                detect_lier(l) # 正直者を不親切な人と言っている人は不親切な人
        honest = [m for m in range(N) if m not in lier]
        if honest_prev == len(honest): # もう正直者が減っていない
            break
        else:
            honest_prev = len(honest)
    # print(i, honest)
    if ans is not False:
        ans = max(ans, len(honest))
    else:
        ans = len(honest)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
info = [[] for _ in range(N)]
true =  [[] for _ in range(N)]
lie = [[] for _ in range(N)]

for i in range(N):
    for _ in range(int(input())):
        x, y = map(int, input().split())
        info[x - 1].append(y)
        if y == 1:
            true[x - 1].append(i)
        elif y == 0:
            lie[x - 1].append(i)
            
flag = False
for i in info:
    if i.count(0) > 0:
        flag = True
if flag is False: # 不親切な人は一人もいない
    print(N)
    exit()

def detect_lier(j): # jを不親切な人とする
    if j in lier:
        return
    lier.append(j)
    for t in true[j]:
        detect_lier(t) # jを正直者だと言った人も不親切な人

ans = False
for i in range(N):
    lier = []
    for j in range(i, N):
        detect_lier(j)
        while True:
            honest = [m for m in range(N) if m not in lier]
            honest_prev = len(honest)
            for h in honest:
                for l in lie[h]:
                    detect_lier(l) # 正直者を不親切な人と言っている人は不親切な人
            if honest_prev == len(honest): # もう正直者が減っていない
                break
        if ans is not False:
            ans = max(ans, len(honest))
        else:
            ans = len(honest)
        break
    else:
        continue
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
info = [[] for _ in range(N)]
true =  [[] for _ in range(N)]
lie = [[] for _ in range(N)]

for i in range(N):
    for _ in range(int(input())):
        x, y = map(int, input().split())
        info[x - 1].append(y)
        if y == 1:
            true[x - 1].append(i)
        elif y == 0:
            lie[x - 1].append(i)
            
flag = False
for i in info:
    if i.count(0) > 0:
        flag = True
if flag is False: # 不親切な人は一人もいない
    print(N)
    exit()

def detect_lier(j): # jを不親切な人とする
    if j in lier:
        return
    lier.append(j)
    info[j] = [0]
    for t in true[j]:
        detect_lier(t) # jを正直者だと言った人も不親切な人
    
    return lier

def judge():
    flag = False
    for k in info:
        if len(set(k)) != 1:
            flag = True
    if flag is False: # 矛盾は生じていない
        return True
    else:
        return False

ans = False
for i in range(N):
    lier = []
    for j in range(i, N):
        detect_lier(j)
        honest = [m for m in range(N) if m not in lier]
        for h in honest:
            for l in lie[h]:
                detect_lier(l)
        if judge():
            if ans is not False:
                ans = max(ans, N - len(set(lier)))
            else:
                ans =  N - len(set(lier))
            break
        else:
            continue
     
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
info = [[] for _ in range(N)]
true =  [[] for _ in range(N)]
lie = [[] for _ in range(N)]

for i in range(N):
    for _ in range(int(input())):
        x, y = map(int, input().split())
        info[x - 1].append(y)
        if y == 1:
            true[x - 1].append(i)
        elif y == 0:
            lie[x - 1].append(i)
            

flag = False
for i in info:
    if i.count(0) > 0:
        flag = True
if flag is False: # 不親切な人は一人もいない
    print(N)
    exit()

def detect_lier(j): # jを不親切な人とする
    if j in lier:
        return
    lier.append(j)
    info[j] = [0]
    for t in true[j]:
        detect_lier(t) # jを正直者だと言った人も不親切な人
    
    return lier

def judge():
    flag = False
    for k in info:
        if len(set(k)) != 1:
            flag = True
    if flag is False: # 矛盾は生じていない
        return True
    else:
        return False

ans = False
for i in range(N):
    lier = []
    for j in range(i, N):
        detect_lier(j)
        if judge():
            honest = [m for m in range(N) if m not in lier]
            for h in honest:
                for l in lie[h]:
                    detect_lier(l)
            if judge():
                if ans is not False:
                    ans = max(ans, N - len(set(lier)))
                else:
                    ans =  N - len(set(lier))
                break
            else:
                continue
        else:
            continue
print(ans)

Submission status: Wrong Answer

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

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

flag = False
for i in info:
    if i.count(0) > 0:
        flag = True
if flag is False: # 不親切な人は一人もいない
    print(N)
    exit()

def detect_lier(j): # jを不親切な人とする
    if j in lier:
        return
    lier.append(j)
    info[j] = [0]
    for t in true[j]:
        detect_lier(t) # jを正直者だと言った人も不親切な人
    
    return lier

def judge():
    flag = False
    for k in info:
        if len(set(k)) != 1:
            flag = True
    if flag is False: # 矛盾は生じていない
        return True
    else:
        return False

ans = False
for i in range(N):
    lier = []
    for j in range(i, N):
        detect_lier(j)
        if judge():
            if ans is not False:
                ans = max(ans, N - len(set(lier)))
            else:
                ans =  N - len(set(lier))
            break
        else:
            continue
print(ans)

Submission status: Wrong Answer

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

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

flag = False
for i in info:
    if i.count(0) > 0:
        flag = True
if flag is False: # 不親切な人は一人もいない
    print(N)
    exit()

def detect_lier(j): # jを不親切な人とする
    if j in lier:
        return
    lier.append(j)
    info[j] = [0]
    for t in true[j]:
        detect_lier(t) # jを正直者だと言った人も不親切な人
    
    return lier

ans = False

for i in range(N):
    lier = []
    detect_lier(i)
    flag = False
    for k in info:
        if len(set(k)) != 1:
            flag = True
    if flag is False: # 矛盾は生じていない
        if ans is not False:
            ans = max(ans, N - len(set(lier)))
        else:
            ans = N - len(set(lier))
    else:
        continue

print(ans)

Submission status: Wrong Answer

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

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

flag = False
for i in info:
    if i.count(0) > 0:
        flag = True
if flag is False: # 不親切な人は一人もいない
    print(N)
    exit()

def detect_lier(j): # jを不親切な人とする
    if j in lier:
        return
    lier.append(j)
    for t in true[j]:
        detect_lier(t) # jを正直者だと言った人も不親切な人
    
    return lier

ans = False

for i in range(N):
    lier = []
    detect_lier(i)
    if ans is not False:
        ans = max(ans, N - len(set(lier)))
    else:
        ans = N - len(set(lier))

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

g = [[-1] * 15 for _ in range(15)]

for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        g[i][x] = y
ans = 0
for i in range(1 << n):
    d = [0] * n
    for j in range(n):
        if i >> j & 1:
            d[j] = 1

    cnt = 0
    ok = 1
    for j in range(n):
        if d[j]:
            for k in range(n):
                if g[j][k] == -1:
                    continue
                if g[j][k] == d[k]:
                    cnt += 1
                else:
                    ok = 0

    if ok:
        ans = max(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
testimony = [[] for i in range(n)]
num_of_testimony = []
for i in range(n):
    for a in range(int(input())):
        num_of_testimony.append(a)
        x,y = map(int, input().split())
        testimony[i].append([x,y])
#print(testimony)
honest = 0
for i in range(2**n):
    Flag = True
    for j in range(n):
        if (i>>j)&1:
            for x,y in testimony[j]:
                if (i>>x)&1 != y:
                    flag = False
                    break
    if Flag:
        honest = max(honest, bin(i)[2:].count('1'))
print(honest)

Submission status: Wrong Answer

Solution code:
def bitcnt(n):
  n=(n&0x55555555)+(n>>1&0x55555555)
  n=(n&0x33333333)+(n>>2&0x33333333)
  n=(n&0x0f0f0f0f)+(n>>4&0x0f0f0f0f)
  n=(n&0x00ff00ff)+(n>>8&0x00ff00ff)
  n=(n&0x0000ffff)+(n>>16&0x0000ffff)
  return n
N = int(input())
xy = [[-1 for j in range(N)] for i in range(N)]
for i in range(N):
  for j in range(int(input())):
    x, y = map(int, input().split())
    x -= 1
    xy[i][x] = y
r = 0
for i in range(1<<N):
  t = [i>>j&1 for j in range(N)]
  ok = True
  for j in range(N):
    if t[j]:
      for k in range(N):
        if xy[j][k] == -1:
          continue
        if xy[j][k] != t[j]:
          ok = False
          break
  if ok:
    r = max(r, bitcnt(i))
print(r)

Submission status: Wrong Answer

Solution code:
cmin = lambda a,b : a if a<b else b
cmax = lambda a,b : a if a>b else b
iin = lambda : int(input())
lin = lambda : list(map(int,input().split()))
rin = lambda n : [int(input()) for _ in range(n)]

n = int(input())

state = {}
for i in range(n):
    a = int(input())
    state[i+1] = []
    for j in range(a):
        x,y = map(int,input().split())
        state[i+1] += [(x,y)]

for i in reversed(range(2**n)):
    s = bin(i).count("1")
    t = list(enumerate(reversed((bin(i).split("b")[1]))))
    t = [j+1 for j,val in t if val=="1"]
    flag = True
    for j in t:
        for a,b in state[j]:
            if (a in t and b==0) or (a not in t and b==1):
                flag = False
    if flag:
        print(s)
        break

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from itertools import combinations
from operator import contains

def readlines(n):
    for _ in range(n):
        x, y = input().split()
        yield int(x)-1, y=="1"

def main():
    n = int(input())
    asserts = []

    for _ in range(n):
        a = int(input())
        asserts.append(list(readlines(a)))

    def check(comb):
        for i in comb:
            for x, y in asserts[i]:
                mujun = contains if not y else lambda a, b: b not in a
                if mujun(comb, x):
                    return -1
        
        return len(comb)

    for i in range(n):
        for comb in combinations(range(n), i):
            ans = check(set(comb))
            if ans > -1:
                yield ans
    yield 0

print(max(main()))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from operator import eq, ne
from itertools import combinations
from operator import contains

def readlines(n):
    for _ in range(n):
        x, y = input().split()
        yield int(x)-1, y=="1"

def main():
    n = int(input())
    asserts = []

    for _ in range(n):
        a = int(input())
        asserts.append(list(readlines(a)))

    def check(comb):
        for i in comb:
            for x, y in asserts[i]:
                mujun = contains if not y else lambda a, b: b not in a
                if mujun(comb, x):
                    return -1
        
        return len(comb)

    for i in range(n):
        for comb in combinations(range(n), i):
            yield check(set(comb))

    yield 0

print(max(main()))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from operator import eq, ne
def readlines(n):
    for _ in range(n):
        x, y = input().split()
        yield int(x)-1, y


def main():
    n = int(input())
    graph = []

    for _ in range(n):
        a = int(input())
        graph.append(list(readlines(a)))

    def check(bits):
        for i, asserts in enumerate(graph):
            for x, y in asserts:
                op = ne if bits[i] == "1" else eq
                if op(bits[x], y):
                    return -1
        
        return len([b for b in bits if b == "1"])

    for i in range(2**n-1, -1, -1):
        bit = format(i, "0{}b".format(n))
        ans = check(bit)
        if ans > -1:
            print(ans)
            return
    
    print(0)

main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from operator import eq, ne
def readlines(n):
    for _ in range(n):
        x, y = input().split()
        yield int(x)-1, y


def main():
    n = int(input())
    graph = []

    for _ in range(n):
        a = int(input())
        graph.append(list(readlines(a)))

    def check(bits):
        for i, asserts in enumerate(graph):
            for x, y in asserts:
                op = ne if bits[i] == "1" else eq
                if op(bits[x], y):
                    return -1
        
        return len([b for b in bits if b == "1"])

    for i in range(2**n-1, 1, -1):
        bit = format(i, "0{}b".format(n))
        ans = check(bit)
        if ans > -1:
            print(ans)
            return
    
    print(0)

main()

Submission status: Wrong Answer

Solution code:
# from fractions import gcd
# mod = 10 ** 9 + 7
# N = int(input())
# a = list(map(int,input().split()))
# a,b,c = map(int,input().split())
# ans = [0] * N
# math.ceilで切り上げ
# dp = [[0] * 4 for i in range(3)] #2次元配列初期化
# dp = [[[0] * 2 for i in range(3)] for j in range(5)]
# (ord('A'))でASCII出力 Aは65
import math
import statistics
import string
import sys
from array import array
from collections import deque

def intinput():
    return int(input())
def listintinput():
    return list(map(int, input().split()))
def splitintinput():
    return map(int, input().split())
def factorialsurplus(x, y, z):  # xからyまでの階乗をzで割ったあまりを求める
    ret = 1
    for i in range(x, y + 1):
        ret = (ret * i) % z
    return (ret)
def isprime(x):
    if x == 1:
        return False
    if x == 2:
        return True
    sq = int(math.sqrt(x))
    for i in range(2,sq+1):
        if x % i == 0:
            return False
    return True
def hcfnaive(a,b):#最大公約数 math.gcdが使えない時の手段として入れとく。pythonが更新されたらいらなくなるはず
    if(b==0):
        return a
    else:
        return hcfnaive(b,a%b)


N = intinput()
dic = {}
ans = 0
true_person = 0
true_or_false = {}
flag_contradiction = 0
for i in range(N):
    dic[i] = {}

for i in range(N):
    A = intinput()
    for j in range(A):
        x,y = splitintinput()
        dic[i][x-1] = y

for i in range(2**N):
    tmp = format(i, 'b').zfill(N)
    true_person = tmp.count('1')
    true_or_false = {}
    flag_contradiction = 0
    for j in range(N):
        for k in dic[j]:
            if (dic[j][k] ^ int(tmp[j])) ^ 1 != int(tmp[k]):
                flag_contradiction = 1
                break
    if flag_contradiction == 0:
        ans = max(ans,true_person)

print(ans)