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:
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
import heapq

sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD


def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD


def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret

def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid

    def pos(self, x, y):
        return y * (self.w + 2) + x + 1

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]

        ans = 0
        for i in range(1, self.h + 1):
            for j in range(1, self.w + 1):
                pass # ここから何か書いてね
def bc(bi):
    # bit-count
    ret = 0
    while(bi > 0):
        if bi & 1 == 1:
            ret += 1
        bi //= 2
    return ret

def judge(bi, shogen, n):
    hito = []

    for i in range(n):
        hito.append(bi & 1)
        bi //= 2
    # print(hito)
    for i, sho in enumerate(shogen):
        for sh in sho:
            tgt, bo = sh
            tgt -= 1
            if hito[tgt] == hito[i] ^ bo:
                return -1

    return sum(hito)

def solve():
    n = getN()
    shogen = []
    for i in range(n):
        a = getN()
        tmp = []
        for j in range(a):
            tmp.append(getList())
        shogen.append(tmp)
    ans = 0
    print(shogen)
    for bi in range(1 << n):
        ans = max(ans, judge(bi, shogen, n))
        # print(ans)

    print(ans)


def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    # main()
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
import heapq

sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD


def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD


def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret

def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid

    def pos(self, x, y):
        return y * (self.w + 2) + x + 1

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]

        ans = 0
        for i in range(1, self.h + 1):
            for j in range(1, self.w + 1):
                pass # ここから何か書いてね
def bc(bi):
    # bit-count
    ret = 0
    while(bi > 0):
        if bi & 1 == 1:
            ret += 1
        bi //= 2
    return ret

def judge(bi, shogen, n):
    hito = []

    for i in range(n):
        hito.append(bi & 1)
        bi //= 2
    # print(hito)
    for i, sho in enumerate(shogen):
        for sh in sho:
            tgt, bo = sh
            tgt -= 1
            if hito[tgt] == hito[i]^bo:
                return 0

    return sum(hito)

def solve():
    n = getN()
    shogen = []
    for i in range(n):
        a = getN()
        tmp = []
        for j in range(a):
            tmp.append(getList())
        shogen.append(tmp)
    ans = 0
    # print(shogen)
    for bi in range(1 << n):
        ans = max(ans, judge(bi, shogen, n))
        # print(ans)

    print(ans)


def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    # main()
    solve()

Submission status: Wrong Answer

Solution code:
import itertools

N = int(input())
bit = list(itertools.product([0,1], repeat=N))
li = []

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

bit.reverse()

for i in bit:#bit演算で正直者と嘘つき者を01で
    flag = True
    for t,j in enumerate(li):#証言者とその内容
        t += 1
        for k in j:#各証言
            if i[t-1]==1:#証言してる人が正直者の場合
                if i[k[0]-1] != k[1]:#矛盾が発生した場合
                    flag = False
                    break
            else:
                if i[k[0]-1] == k[1]:#矛盾が発生した場合
                    flag = False
                    break
    if flag == True:
        print(sum(i))
        exit()
print(0)

Submission status: Wrong Answer

Solution code:
import itertools

N = int(input())
bit = list(itertools.product([0,1], repeat=N))
li = []

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

bit.reverse()

for i in bit:#bit演算で正直者と嘘つき者を01で
    flag = True
    for t,j in enumerate(li):#証言者とその内容
        t += 1
        for k in j:#各証言
            if i[t-1]==1:#証言してる人が正直者の場合
                if i[k[0]-1] != k[1]:#矛盾が発生した場合
                    flag = False
                    break
            else:
                if i[k[0]-1] == k[1]:#矛盾が発生した場合
                    flag = False
                    break
    if flag == True:
        print(sum(i))
        break

Submission status: Wrong Answer

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

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

for i in range(2**n):
    f=0
    m=0
    rel=[0 for _ in range(n)]
    for j in range(n):
        if (i>>j)&1:
            rel[j]=1
            m+=1
            
    for j in range(n):
        for q in range(len(tes[j])//2):
            if rel[j]==1 and tes[j][2*q+1]==1 and rel[tes[j][2*q]-1]==0:
                rel[tes[j][2*q]-1]=1
                m+=1
    for j in range(n):
        
        for q in range(len(tes[j])//2):
            if rel[j]==1 and tes[j][2*q+1]==0 and rel[tes[j][2*q]-1]==1:
                f=1
    if f==0:
        ans.append(m)
print(max(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
L = []
for _ in range(N):
  L.append([list(map(int, input().split())) for _ in range(int(input()))])
M = 0
for i in range(2**N):
  A = []
  for j in range(N):
    if (i>>j)&1:
      A.append(j)
  for a in A:
    for l in L[a]:
      if l[0]-1 in A and l[1]==0:
        break
    else:
      continue
    break
  else:
    M = max(M, len(A))
print(M)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
xy = []
for i in range(n):
    a.append(int(input()))
    xy.append([list(map(int, input().split())) for i in range(a[-1])])
ans = 0
for i in range(2**n):
    x = [1] * n
    for j in range(n):
        if (i>>j)&1:
            x[j] = 0
    flag = False
    for j in range(n):
        for k in range(a[j]):
            if x[j] == 0:
                if x[xy[j][k][0]-1] == xy[j][k][1]:
                    flag = True
                    break
            else:
                if x[xy[j][k][0]-1] != xy[j][k][1]:
                    flag = True
                    break
        if flag:
            break
    if flag:
        continue
    ans = max(ans, x.count(1))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product

N=int(input())
datas=[]
for i in range(N):
    A=int(input())
    for j in range(A):
        x,y=map(int,input().split())
        datas.append((i,x-1,y)) #誰が　誰に　どう判断した？

#print(datas)

ans=0
for i in product([0,1],repeat=N):
    ok=True
    for j in datas:
        if i[j[0]]==1 and i[j[1]]!=j[2]:
            ok=False
            break
    if ok:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product

def max2(x,y):
    return x if x > y else y

N = int(input())
data = [[] for _ in range(N)]
res = 0
for i in range(N):
    for _ in range(int(input())):
        data[i].append(tuple(map(int, input().split())))
for a in product((0,1), repeat=N):
    flg = False
    for i in range(N):
        for x, y in data[i]:
            x -= 1
            if a[x] == (y - a[i] - 1)%2:
                continue
            else:
                flg = True
                break
        if flg:
            break
        if i == N-1:
            res = max2(res, sum(a))
print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = []
for i in range(n): # 初期リストの作成
    k = [i+1]
    speak = int(input())
    for m in range(speak):
        k.append(list(map(int, input().split())))
    l.append(k)

def bc(x):
    return bin(x).count("1")

ans = 0
for i in range(1<<n): # ビット全探索
    flag = True
    for k in range(n):
        if (i>>k) & 1: #桁ごとの解釈
            for m in l[k]:
                if type(m) == int:
                    pass
                elif i>>(m[0]-1) & 1:
                    if m[1] != 1:
                        flag = False
    if flag == True:
        ans = max(ans,bc(i))
print(ans)

Submission status: Wrong Answer

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    ans=0
    n=INT()
    xyall=[]
    for i in range(n):
        xyall.append([])
        a=INT()
        for j in range(a):
            x,y=INTM()
            xyall[i].append([x,y])
    
    for i in range(2**n):
        flg=True
        ct=0
        for j in range(n):
            if ((i >> j) & 1):
                #print('bb')
                ct+=1
                xys=xyall[j]
                for xy in xys:
                    #print(xy)
                    if ((i >> xy[0]-1) == xy[1]):
                        #print('cc')
                        pass
                    else:
                        flg=False
                        break
            else:
                pass
        if flg:
            #print('aa')
            ans=max(ans,ct)
    print(ans)



if __name__=='__main__':
    do()

Submission status: Wrong Answer

Solution code:
n = int(input())
g = [[-1 for _ in range(15)] for _ in range(15)]
for i in range(n) :
    m = int(input())
    for j in range(m) :
        x,y = map(int, input().split())
        #人iが「人xはyである」と証言している
        g[i][x-1] = y

ans = 0
for i in range(1<<n) :
    honests = [0] * n
    for j in range(n) :
        if (i>>j) & 1 :
            honests[j] = 1
    ok = True
    for j in range(n) :
        if honests[j] : #正直者の証言だけ検証する
            for k in range(n) :
                if g[j][k] == -1 :
                    continue
                if g[j][k] != honests[k] :
                    ok = False
            if ok :
                ans = max(ans, honests.count(1))

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
g = [[-1] * 15 for _ in range(15)]
for i in range(n) :
    m = int(input())
    for j in range(m) :
        x,y = map(int, input().split())
        #人iが「人xはyである」と証言している
        g[i][x-1] = y

ans = 0
for i in range(1<<n) :
    honests = [0] * n
    for j in range(n) :
        if (i>>j) & 1 :
            honests[j] = 1
    ok = True
    for j in range(n) :
        if honests[j] : #正直者の証言だけ検証する
            for k in range(n) :
                if g[j][k] == -1 :
                    continue
                if g[j][k] != honests[k] :
                    ok = False
            if ok :
                ans = max(ans, honests.count(1))

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

n = int(input())
lst = []
for _ in range(n):
  m = int(input())
  lst_s = []
  for _ in range(m):
    evidence = list(map(int, input().split()))
    lst_s.append(evidence)
  lst.append(lst_s)
#print(lst)

truth = [0, 1]
all_lists = list(itertools.product(truth, repeat=n))
#print(all_lists)
max_count = 0
for each in all_lists:
  flag = True
  count = 0
  #print(each)
  for i in range(n):
    trust = each[i]
    #print(trust)
    evis = lst[i]
    for evid in evis:
      #print(evid)
      person_ind = evid[0] - 1
      person_trust = evid[1]
      if trust == 0:
        if person_trust == 0:
          person_trust = 1
        else:
          person_trust = 0
      if person_trust != each[person_ind]:
        flag = False
        break
    if not flag:
      break
    if trust == 1:
      count += 1
  if (count > max_count) and flag:
    max_count = count
print(max_count)

Submission status: Wrong Answer

Solution code:
import itertools

n = int(input())
lst = []
for _ in range(n):
  m = int(input())
  lst_s = []
  for _ in range(m):
    evi = list(map(int, input().split()))
    lst_s.append(evi)
  lst.append(lst_s)
#print(lst)

truth = [0, 1]
all = list(itertools.product(truth, repeat=n))
#print(all)
max_count = 0
for each in all:
  flag = True
  count = 0
  #print(each)
  for i in range(n):
    trust = each[i]
    #print(trust)
    evis = lst[i]
    for evid in evis:
      #print(evid)
      person = evid[0] - 1
      person_trust = evid[1]
      if trust == 0:
        if person_trust == 0:
          person_trust = 1
        else:
          person_trust = 0
      if person_trust != each[person]:
        flag = False
        break
    if not flag:
      break
    if trust == 1:
      count += 1
  if (count > max_count) and flag:
    max_count = count
print(max_count)

Submission status: Wrong Answer

Solution code:
n=int(input())
syo=[]
mx=0
for i in range(n):
  a=int(input())
  gen=[]
  for j in range(a):
    x,y=map(int,input().split())
    gen.append([x-1,bool(y)])
  syo.append(gen)
brk=False
for i in range(2**n):
  table=[False]*n
  for j in range(n):
    if((i>>j)&1):
      table[j]=True
  for j in range(n):
    if table[j]==False:
      continue
    for syogen in syo[j]:
      if table[syogen[0]]!=syogen[1]:
        brk=True
        break
    if brk:
      break
  if brk:
    continue
  cnt=table.count(True)
  if cnt>mx:
    mx=cnt
print(mx)

Submission status: Wrong Answer

Solution code:
n=int(input())
syo=[]
mx=0
for i in range(n):
  a=int(input())
  gen=[]
  for j in range(a):
    x,y=map(int,input().split())
    gen.append([x-1,bool(y)])
  syo.append(gen)
brk=False
for i in range(2**n):
  table=[False]*n
  for j in range(n):
    if((i>>j)&1):
      table[j]=True
  for j in range(n):
    if table[j]==False:
      brk=True
      break
    brk=False
    for syogen in syo[j]:
      if table[syogen[0]]!=syogen[1]:
        brk=True
        break
    if brk:
      break
  if brk:
    continue
  cnt=table.count(True)
  if cnt>mx:
    mx=cnt
print(mx)

Submission status: Wrong Answer

Solution code:
n=int(input())
syo=[]
mx=0
for i in range(n):
  a=int(input())
  gen=[]
  brk=False
  for j in range(a):
    x,y=map(int,input().split())
    gen.append([x-1,y])
  syo.append(gen)
for i in range(2**n):
  table=[False]*n
  for j in range(n):
    if((i>>j)&1):
      table[j]=True
  for j in range(n):
    if not table[j]:
      break
    brk=False
    for syogen in syo[j]:
      if table[syogen[0]]!=syogen[1]:
        brk=True
        break
    if brk:
      break
  if brk:
    continue
  cnt=table.count(True)
  if cnt>mx:
    mx=cnt
print(mx)

Submission status: Wrong Answer

Solution code:
n=int(input())
syo=[]
mx=0
for i in range(n):
  a=int(input())
  gen=[]
  brk=False
  for j in range(a):
    x,y=map(int,input().split())
    gen.append([x,y])
  syo.append(gen)
for i in range(2**n):
  table=[False]*n
  for j in range(n):
    if((i>>j)&1):
      table[j]=True
  for j in range(n):
    if not table[j]:
      break
    brk=False
    for syogen in syo[j]:
      if table[syogen[0]-1]!=syogen[1]:
        brk=True
        break
    if brk:
      break
  if brk:
    continue
  cnt=table.count(True)
  if cnt>mx:
    mx=cnt
print(mx)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
x = []
for i in range(N):
    tmp = ii()
    x.append(li2(tmp))

if N == 1:
    if x != [[[1, 0]]]:
        print(1)
        exit()
    else:
        print(0)
        exit()

B = 2 ** N
ans = 0
no = [0] * N
rel = []

def dfs(i):
    global visited
    global table
    visited[i] = 1
    for a, b in x[i]:
        if table[a-1] == 1 and b == 1:
            global flag_ok
            flag_ok = 1
            break
        if b == 1:
            table[a-1] = b
            if not visited[a-1]:
                dfs(a-1)

for i in range(N):
    visited = [0] * N
    table = [-1] * N
    flag_ok = 0

    dfs(i)

    if not flag_ok:
        rel.append(table)
    else:
        rel.append([0] * N)
        no[i] = 1

for i in range(B):
    sin = [-1] * N
    cnt = 0
    for j in range(N):
        if i & (1 << j):
            if no[j]:
                break
            cnt += 1
            for k in range(N):
                if sin[k] == 1 and rel[j][k] == 0:
                    break
                sin[k] = rel[j][k]
            else:
                continue
            break
    else:
        ans = max(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
x = []
for i in range(N):
    tmp = ii()
    x.append(li2(tmp))

if N == 1:
    if x != [[[1, 0]]]:
        print(1)
        exit()
    else:
        print(0)
        exit()

B = 2 ** N
ans = 0
no = [0] * N
rel = []

def dfs(i):
    global visited
    global table
    visited[i] = 1
    for a, b in x[i]:
        if table[i] != -1 and table[i] != b:
            global flag_ok
            flag_ok = 1
            break
        table[i] = b
        if not visited[a-1] and b == 1:
            dfs(a-1)

for i in range(N):
    visited = [0] * N
    table = [-1] * N
    flag_ok = 0

    dfs(i)

    if not flag_ok:
        rel.append(table)
    else:
        rel.append([0] * N)
        no[i] = 1

for i in range(B):
    sin = [-1] * N
    cnt = 0
    for j in range(N):
        if i & (1 << j):
            if no[j]:
                break
            cnt += 1
            for k in range(N):
                if sin[k] != -1 and sin[k] != rel[j][k]:
                    break
                sin[k] = rel[j][k]
            else:
                continue
            break
    else:
        ans = max(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
x = []
for i in range(N):
    tmp = ii()
    x.append(li2(tmp))

if N == 1 and x != [[[1, 0]]]:
    print(1)
    exit()

B = 2 ** N
ans = 0

table = dp2(-1, N, N)
no = [0] * N

def dfs(i, j):
    global visited
    visited[j] = 1
    for a, b in x[j]:
        if table[i][a-1] != -1 and table[i][a-1] != b:
            global flag_ok
            flag_ok = 1
            break
        table[i][a-1] = b
        if not visited[a-1] and b == 1:
            dfs(i, a-1)

for i in range(N):
    visited = [0]*N
    flag_ok = 0
    table[i][i] = 1
    dfs(i, i)
    if flag_ok == 1:
        no[i] = 1

for i in range(B):
    sin = [-1] * N
    cnt = 0
    for j in range(min(B+1, N)):
        if i & (1 << j):
            if no[j]:
                break
            cnt += 1
            for k in range(N):
                if sin[k] != -1 and sin[k] != table[j][k]:
                    break
                sin[k] = table[j][k]
            else:
                continue
            break
    else:
        ans = max(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
x = []
for i in range(N):
    tmp = ii()
    x.append(li2(tmp))

if N == 1:
    print(1)
    exit()

B = 2 ** N
ans = 0

table = dp2(-1, N, N)
no = [0] * N

def dfs(i, j):
    global visited
    visited[j] = 1
    for a, b in x[j]:
        if table[i][a-1] != -1 and table[i][a-1] != b:
            global flag_ok
            flag_ok = 1
            break
        table[i][a-1] = b
        if not visited[a-1]:
            dfs(i, a-1)

for i in range(N):
    visited = [0]*N
    flag_ok = 0
    dfs(i, i)
    if flag_ok == 1:
        no[i] = 1

#print(no)

for i in range(B):
    sin = [-1] * N
    cnt = 0
    for j in range(N):
        if not no[j] and i & (1 << j):
            cnt += 1
            for k in range(N):
                if sin[k] != -1 and sin[k] != table[j][k]:
                    break
                sin[k] = table[j][k]
        else:
            ans = max(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
    import itertools
    N = int(input())
    A = []
    X = []
    ans = [0]
    for _ in range(N):
        a = int(input())
        xx = []
        for __ in range(a):
            x = list(map(int, input().split()))
            xx.append(x)
        X.append(xx)
        A.append(a)
    for i in itertools.product([0, 1], repeat=N):
        flag = 0
        for p in range(N):
            for q in range(A[p]):
                if (i[p] == 1 and X[p][q][1] == i[X[p][q][0]-1]) or (i[p] == 0 and X[p][q][1] != i[X[p][q][0]-1]):
                    flag += 1
                else:
                    flag = -100000
        if flag == sum(A):
            ans.append(i.count(1))
    print(max(ans))
resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    import itertools
    N = int(input())
    A = []
    X = []
    ans = [0]
    for _ in range(N):
        a = int(input())
        xx = []
        for __ in range(a):
            x = list(map(int, input().split()))
            xx.append(x)
        X.append(xx)
        A.append(a)
    for i in itertools.product([0, 1], repeat=N):
        flag = 0
        for p in range(N):
            for q in range(A[p]):
                if (i[p] == 1 and X[p][q][1] == i[X[p][q][0]-1]) or (i[p] == 0 and X[p][q][1] != i[X[p][q][0]-1]):
                    continue
                else:
                    flag = 1
        if flag == 0:
            ans.append(i.count(1))
    print(max(ans))
resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    import itertools
    N = int(input())
    A = []
    X = []
    ans = [0]
    for _ in range(N):
        a = int(input())
        xx = []
        for __ in range(a):
            x = list(map(int, input().split()))
            xx.append(x)
        X.append(xx)
        A.append(a)
    for i in itertools.product([0, 1], repeat=N):
        flag = 0
        for p in range(N):
            for q in range(A[p]):
                if (i[p] == 1 and X[p][q][1] == i[X[p][q][0]-1]) or (i[p] == 0 and X[p][q][1] != i[X[p][q][0]-1]):
                    flag += 1
        if flag == sum(A):
            ans.append(i.count(1))
    print(max(ans))
resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    import itertools
    N = int(input())
    A = []
    X = []
    ans = [0]
    for _ in range(N):
        a = int(input())
        xx = []
        for __ in range(a):
            x = list(map(int, input().split()))
            xx.append(x)
        X.append(xx)
        A.append(a)
    for i in itertools.product([0, 1], repeat=N):
        flag = 0
        for p in range(N):
            for q in range(A[p]):
                if i[p] == 1 and X[p][q][1] == i[X[p][q][0]-1] or i[p] == 0 and X[p][q][1] != i[X[p][q][0]-1]:
                    flag += 1
        if flag == sum(A):
            ans.append(i.count(1))
    print(max(ans))
resolve()

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): # 部分和の計算　i=2は"0b10" 
	result = 0
	for j in range(n): # 各桁を確認 jは桁数を表す
		if i & (1 << (j)): #trueだった場合はj桁目は1である(後ろからj番目は正直者)
			for k in range(list_a[-j]):
				if i & testimonies[-j][k][1] << (testimonies[-j][k][0]-1):
					flag = False
					break
			if flag == True:
				result += 1
			else:
				flag = True
	if answer < result:
		answer = result

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XY = []
for _ in range(N):
    A = int(input())
    xy = [list(mapint()) for _ in range(A)]
    XY.append(xy)

ans = 0
for i in range(1<<N):
    honest = [-1]*N
    cnt = 0
    for j in range(N):
        if (i>>j)&1:
            cnt += 1
            if honest[j]==0:
                break
            honest[j] = 1
            flg = False
            for x, y in XY[j]:
                if y==0:
                    if honest[x-1]==1:
                        break
                    else:
                        honest[x-1] = 0
                if y==1:
                    if honest[x-1]==0:
                        break
                    else:
                        honest[x-1] = 1
            else:
                flg = True
            if not flg:
                break
        else:
            if honest[j]==1:
                break
    else:
        ans = max(ans, cnt)

print(ans)