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 numpy as np
n = int(input())
xys = []
for k in range(n):
    a = int(input())
    xys.append([])
    for i in range(a):
        xy = list(map(int, input().split()))
        xy[0] -= 1
        if xy[1] == 0:
            xy[1] = -1
        xys[-1].append(xy)
        

best = 0
for l in range(n):
    hantei = [0 for _ in range(n)]
    hantei[l] = 1
#     xys = xys[1:] + [xys[0]]
    flag = 0
    que = [l]
    done = []
    while len(que) > 0:
        i = que[0]
        a = xys[i]
        done.append(i)
        que = que[1:]
#     for i, a in enumerate(xys):
        #print("---")
        #print("done", done)
        #print("que", que)
        #print("han", hantei)
        #print("flag", flag)
        #print("a", a)
        for k, b in enumerate(a):
            if b[0] not in done:
                que.append(b[0])
            #print("b", b)
            if hantei[b[0]] == 0:
                hantei[b[0]] = b[1]
                #print("hantei", hantei)
            else:
                if hantei[b[0]] == b[1]:
                    pass
#                     if hantei[i] == -1:
#                         flag = -1
#                         #print("bad***")
#                         break
                else:
                    if hantei[i] == 1:
                        flag = -1
                        #print("bad***")
                        break
            if flag == -1:
                break
        if flag == -1:
            break
        #print("que", que)
        
    if flag == 0:
        if best < np.sum(np.array(hantei) == 1):
            best = np.sum(np.array(hantei) == 1)


print(best)

Submission status: Wrong Answer

Solution code:
n = int(input())
honest = {}
for i in range(n):
    honest[i+1] = []
dic = {}
for i in range(n):
    n1 = int(input())
    for j in range(n1):
        a, b = map(int, input().split())
        honest[a].append(b)
        if i+1 in dic:
            dic[i+1].append([a, b])
        else:
            dic[i+1] = [[a, b]]

for i in honest:
    if honest[i].count(1) > honest[i].count(0):
        honest[i] = True
    else:
        honest[i] = False
for i in dic:
    if honest[i]:
        for j in dic[i]:
            honest[j[0]] = True if j[1] == 1 else False
c = 0
for i in honest:
    if honest[i]:
        c += 1
if c > 0:
    print(c)
else:
    print(1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# 1 正直者
# 0 不親切
# 特定個人に対して、矛盾する発言がなければよい
import sys

ws = int(input().rstrip())
werewolfs = {}
remarks = []
for v in range(ws):
    rs = int(input().rstrip())
    for s in range(rs):
        rs = input().rstrip().split(' ')
        remarks += [{"to": int(rs[0]), "is_w": int(rs[1])}]

for value in remarks:
    v = []
    if value["to"] in werewolfs:
        v = werewolfs[value["to"]]
        v += [value["is_w"]]
    else:
        v += [value["is_w"]]
    werewolfs[value["to"]] = v

honest_count = ws
for value in werewolfs.values():
    if(len(value) > 1 or value == [0]):
        honest_count -= 1

if(honest_count < 0):
   honest_count = 0

print(honest_count)

Submission status: Wrong Answer

Solution code:
N = int(input())
honest = 0
unKind = 0
for i in range(N):
    A = int(input())
    arr = []
    for j in range(A):
        x,y = map(int,input().split())
        arr.append(y)
    if arr.count(1) > arr.count(0):
        honest +=1
    if arr.count(0) == len(arr):
        unKind +=1

if unKind == N:
    print(1)
else:
    print(honest)

Submission status: Wrong Answer

Solution code:
def check_valid(flag):
    for i, m in mentions.items():
        if not (flag & (1 << i)):
            continue
        for j, honest in m.items():
            if honest and flag & (1 << j):
                continue
            if not honest and not (flag & (1 << j)):
                continue
            return False
    return True


n = int(input())
mentions = {}
for i in range(1, n + 1):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        if i not in mentions:
            mentions[i] = {x: y}
        else:
            mentions[i][x] = y
res = 0
for i in range(1 << n):
    if check_valid(i):
        temp = 0
        for j in range(1, n + 1):
            if i & (1 << j):
                temp += 1
            res = max(res, temp)
print(res)

Submission status: Wrong Answer

Solution code:
N=int(input())
X=[[] for i in range(N)]
ans=N
for i in range(N):
    A=int(input())
    for j in range(A):
        x,y=map(int,input().split())
        X[x-1].append(y)
for s in X:
    sx=set(s)
    if len(s)==2:
        ans-=1
    elif 0 in sx:
        ans-=0.5
print(int(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
l = [[None]*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())
    l[i][x-1] = y
    l[i][i] = 1
ans = 0
for i in range(N-1):
  cnt = 0
  for j in range(i+1,N):
    if l[i][j] == l[j][i] and l[i][j]==1:
      cnt += 2
    elif l[i][j] == l[j][i] and l[i][j]==0:
      cnt += 1
    elif l[i][j] != l[j][i]:
      continue
  ans = max(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
d = defaultdict(list)
N = int(input())
s = []
for i in range(N):
    c = int(input())
    for _ in range(c):
        a,b = map(int, input().split())
        d[i].append((a-1,b))
ans = 0

# print(d)
for i in range(2**N):
    bins = format(i,"016b")[::-1]
    cnt = 0
    for i,b in enumerate(bins):
        if b == "1": #正直者のとき
            ls = d[i]
            flg = True
            for a,b in ls:
                # print(bins,a,b,bins[a],str(b) == bins[a])
                if str(b) == bins[a]:
                    cnt+=1
                else:
                    flg = False
                    break
            if not flg:
                cnt = 0
                break
        # print(cnt)
    ans = max(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
c = 0
m = np.full((N, N), 2)
for i in range(N):
    a = int(input())
    for j in range(a):
        x,y=[int(k) for k in input().split()]
        x = x -1
        m[j,x] = y
        if (m[x,j] == 1) and (m[j,x] == 1):
            c = c + 2
        elif (m[x,j] == 0) and (m[j,x] == 0):
            c = c + 1
            
print(c)

Submission status: Wrong Answer

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

for i in range(N):
    A[i] = int(input())
    xy = [0]*A[i]
    for j in range(A[i]):
        xy[j] = [int(i) for i in input().split()]
    syogen[i] = xy

syojiki = [0]*N

truth = [7]*N

flag = True

for i in range(N):
    truth[i] = 1
    for j in range(len(syogen[i])):
        if truth[syogen[i][j][0]-1] != syogen[i][j][1] and truth[syogen[i][j][0]-1] != 7:
            flag = False
            break
        truth[syogen[i][j][0]-1] = syogen[i][j][1]
    
    for j in range(N):
        if truth[j] == 1:
            for k in range(len(syogen[j])):
                if truth[syogen[j][k][0]-1] == 7:
                    truth[syogen[j][k][0]-1] = syogen[j][k][1]
                else:
                    if truth[syogen[j][k][0]-1] != syogen[j][k][1]:
                        flag = False
                        break
    
      
    
    if flag:
        tmp = 0
        for j in range(N):
            if truth[j] == 1:
                tmp += 1
        syojiki[i] = tmp
        
    truth = [7]*N
    flag = True

print(max(syojiki))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
A = []
for i in range(N):
	tmp = []
	n = INT()
	shougen = []
	for j in range(n):
		shougen = MAP()
		tmp.append(shougen)
	A.append(tmp)

cand = []
for i in range(2**N):
	shojiki = [0]*N
	for j in range(N):
		if (i>>j & 1):
			shojiki[N-j-1]=1
	cand.append(shojiki)
# print(cand)

ans = []
for c in cand:
	list = [-1]*(N+1)
	success = True
	ones = [a for idx,a in enumerate(A) if c[idx]==1]
	zeros = [a for idx,a in enumerate(A) if c[idx]==0]
	for idx,a in enumerate(zeros):
		for aa in a:
			list[aa[0]] = 0 if aa[1] == 1 else 1
	for idx,a in enumerate(ones):
		for aa in a:
			list[aa[0]] = aa[1]
				# else:
				# 	if list[aa[0]]!=aa[1]:
				# 		success=False
	for k in range(len(c)):
		if c[k]==1 and list[k+1]==0:
			success = False
		if c[k]==0 and list[k+1]==1:
			success = False
	if success:
		#print(c, list)
		ans.append(sum(c))
	
#print(ans)
if ans:
	print(max(ans))
else:
	print(0)

Submission status: Wrong Answer

Solution code:
import itertools
n = int(input())
xy = [0 for _ in range(n)]
for i in range(n):
    ai = int(input())
    xy[i] = [list(map(int , input().split())) for _ in range(ai)]

#print(xy)
#print(xy[0])
#print(xy[0][0])
def checkp(p):
    cnt = 0
    for j in range(n):
        if 1 in p[j] and 0 in p[j]:
            return -1
        if 1 in p[j]:
            cnt += 1
    return cnt

ans = 0
for i in itertools.product([0, 1], repeat=n):
    p = [set() for _ in range(n)]
    for j in range(n):
    #for xyi in xy:
        xyj = xy[j]
        for xyk in xyj:
            #print(xyj)
            p[j].add(i[j])
            if i[j] == 0:
                p[xyk[0]-1].add(-xyk[1] + 1)
            else:
                p[xyk[0]-1].add(xyk[1])
    #print(p, checkp(p))
    ans = max(ans, checkp(p))

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
remark = [0] * N
NGlist = [0] * N
grouplist = [0]*N
ans = 0
for i in range(N):
    remark[i] = [-1] * N
    NGlist[i] = [0] * N
    grouplist[i] = [0] * N


for k in range(N):
    n = int(input())
    for j in range(n):
        x, y = map(int, input().split())
        remark[k][x-1] = y
        if y == 0:
            NGlist[k][x-1] = 1
            NGlist[x - 1][k] = 1
        else:
            grouplist[k][x-1] = 1

for num in range(2 ** N):
    # print("num=")
    # print(num)
    group = set()
    for h in range(N):
        if h not in group and num % 2 == 1:
            group.add(h)
            for s in range(h+1, N):
                if grouplist[h][s] == 1 and s not in group:
                    group.add(s)
            num //= 2
    len_group = len(group)
    # print(group)
    # if ans >= len_group:
    #    flag = 1
    flag = 0

    for m in group:
        for n in group:
            if NGlist[m][n] == 1:
                flag = 1
                # break
        # if flag == 1:
            # break
    if flag == 0 and ans < len_group:
        ans = len_group

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
honest = 0
for i in range(N):
    count = 0
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split())
        if y == 1:
            count += 1
    if count == A:
        honest += 1
print(honest)

Submission status: Wrong Answer

Solution code:
import sys


N = int(input())
A = list()
E = list()
count_E = 0
for i in range(N):
    A.append(int(input()))
    evid = list()
    for j in range(A[-1]):
        evid.append([int(i) for i in input().split()])
        count_E += 1
    E.append(evid)

if count_E > N:
    print(0)
    sys.exit(0)
else:
    count_pos = 0
    for Ei in E:
        for ej in Ei:
            if ej[1] == 1:
                count_pos += 1
    if count_pos == 0:
        print(1)
    else:
        print(count_pos)

Submission status: Wrong Answer

Solution code:
N = int(input())
k = []
s = [0]*(N)
ans = N
for i in range(N):
    A = int(input())
    for j in range(A):
        x,y = map(int,input().split())
        k.append([i+1,x,y])
for i in range(len(k)):
  for j in range(N+1):
    if k[i][1] == j:
      s[j-1] += 1
for i in range(0,len(s)):
  if s[i]>=2:
    ans = ans-1
if ans == len(s):
  ans = ans//2
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = []
ans = 0
for i in range(N):
    A = int(input())
    l = []
    for j in range(A):
        x, y = map(int, input().split())
        l.append([x, y])
    xy.append(l)
# print(xy)

#bit全探索
#bitたつ→正直者
#bitたたない→不親切もの
tmp = [-1 for _ in range(N)]
for i in range(2 ** N):
    tmp = [-1 for _ in range(N)]
    flag = True
    cnt = 0
    for j in range(N):
        if i >> j & 1:
            #正直者
            cnt += 1
            A = xy[j]
            for k in A:
                _x = k[0] - 1
                _y = k[1]
                if tmp[_x] == -1:
                    tmp[_x] = _y
                elif tmp[_x] != -1 and tmp[_x] ==_y:
                    pass
                else:
                    flag = False
        else:
            #不親切もの
            A = xy[j]
            for k in A:
                _x = k[0] - 1
                _y = k[1]
                if tmp[_x] == -1:
                    if _y == 0:
                        tmp[_x] = 1
                    elif _y == 1:
                        tmp[_x] = 0
                elif tmp[_x] != -1 and tmp[_x] !=_y:
                    pass
                else:
                    flag = False
    if flag:        
        for j in range(N):
            if i >> j & 1 and tmp[j] == 0:
                flag = False
            elif i >> j & 0 and tmp[j] == 1:
                flag = False
    if flag:
        ans = max(ans, cnt)
print(ans)

Submission status: Wrong Answer

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

t = []
l = []
ans = 1
flag = 0
for i in range(n):
  t = [i+1]
  l = []
  t_ = [i+1]
  flag = 1
  while(flag == 1):
    flag = 0
    t__ = [z for z in t_]
    t_ = []
    for m in t__:
      for j, k in zip(x[m],y[m]):
        if k == 0:
          if j in t or j in t_:
            ans = 0
            t_ = []
            break
          l.append(j)
        if k == 1:
          if j in l:
            ans = 0
            t_ = []
            break
          if j not in t and j not in t_:
            t_.append(j)
            flag = 1
      if ans == 0:
        flag = 0
        t_ = []
        break
    t.extend(t_)
  if ans != 0:
    ans = max(ans,len(t))
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())

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

max_=0
one_hot=[[] for _ in range(n)]
for i in range(n**2):
  temp=i
  count=0
  for j in range(n):
    one_hot[j]=temp%2
    temp//=2
    if one_hot[j]==1:
      count+=1
  flg=True
  for j in range(n):
    for k in range(len(s[j])):
      if one_hot[j]==1:
        if one_hot[s[j][k][0]-1]!=s[j][k][1]:
          flg=False
          break
      if not flg:
        break
  if flg and max_<count:
    max_=count
  count=0
print(max_)

Submission status: Wrong Answer

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

def main():
    N = int(input())
    # S = input().rstrip()
    mS = [[] for _ in [0,]*(N+1)]
    for i in range(N):
        Ai = int(input())
        for j in range(Ai):
            x, y = map(int, input().split())
            mS[i+1].append((x,y))

    # T1, T2 = map(int,input().split())
    # A1, A2 = map(int,input().split())
    # B1, B2 = map(int,input().split())
    # vA = list(map(int, input().split()))

    res = 0
    # print(mS)
    M = 1<<N
    for m in range(M):
        vS = []
        vH = [-1]*(N+1)
        cnt = 0
        d = 0
        while m:
            if m&1:
                vS.extend(mS[cnt+1])
                vH[cnt+1] = 1
                cnt += 1
            d += 1
            m >>= 1
        
        ok_in_xy = True
        while vS:
            x,y = vS.pop()
            if vH[x] == -1:
                vH[x] = y
                if y:
                    vS.extend(mS[x])
            elif vH[x] != y:
                ok_in_xy = False
                break

        if ok_in_xy:
            res = max(res, cnt)

    print(res)


main()

Submission status: Wrong Answer

Solution code:
def get_switch(n):
    allswitch = []
    for i in range(0,2**n):
        bin_str = format(i,'0'+str(n)+'b')
        swt = list(map(int,list(bin_str)))
        allswitch.append(swt)
    return allswitch

def test(patarn,a,x,y,n):
    ans_sub=sum(patarn)
    for i in range(n):
        if patarn[i]==1:
            for j in range(a[i]):
                if y[i][j]==1:
                    if patarn[x[i][j]]==0:
                        return 0
                else:
                    if patarn[x[i][j]]==1:
                        return 0
        #else:
            #f.append(i)
            #if i in t:
                #return 0
    #print(patarn)
    return ans_sub
    
def main():
    n=int(input())
    a=[]
    x=[]
    y=[]
    for i in range(n):
        a_sub=int(input())
        a.append(a_sub)
        x_sub=[]
        y_sub=[]
        for j in range(a_sub):
            tmp=list(map(int,input().split()))
            x_sub.append(tmp[0]-1)
            y_sub.append(tmp[1])
        x.append(x_sub)
        y.append(y_sub)
    print(x)
    print(y)
    ans=0
    for patarn in get_switch(n):
        ans=max(ans,test(patarn,a,x,y,n))
    print(ans)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = N

dict = {}

for i in range(N):
    for s in range(int(input())):
        arr = list(map(int, input().split()))
        if arr[0] not in dict:
            dict[arr[0]] = [arr[1]]
        else:
            if dict[arr[0]] != arr[1]:
                dict[arr[0]].append(arr[1])
                ans -= 1

all_same = False
for j in dict.keys():
    if len(dict[j]) != 1:
        break
    all_same = True

if all_same:
    ans -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools as it

N = int(input())
xy = []
for i in range(N):
    A_i = int(input())
    xy_i = []
    for j in range(A_i):
        tmp = [int(i) for i in input().split()]
        xy_i.append(tmp)
    xy.append(xy_i)
ans = 0
for conf in it.product(range(2), repeat=N):
    is_consist = True
    # honest 1, evil 0
    for i in range(N):
        if conf[i] == 0:
            continue
        # i is honest
        for jth_state in range(len(xy[i])):
            if xy[i][jth_state][1] != conf[xy[i][jth_state][0] - 1]:
                is_consist = False
                break
    if is_consist:
        ans = max(ans, sum(conf))
        if ans == sum(conf):
            print(conf)
print(ans)

Submission status: Wrong Answer

Solution code:
def Jud(S,n,k):#S:証言、n:人数、
  ans=True
  k2d=format(k,'b').zfill(n)
  for i in range(n):
    people=[]
    if k2d[i]=='1':
      people.append(i)
      for j in people:
        for k in range(len(S[j])):
           if S[j][k][0] not in people:
              ans=False
              break
  return ans
                
n=int(input())#読み込み
S=[[] for i in range(n)]
for i in range(n):
  s=int(input())
  for j in range(s):
    S[i].append(list(map(int,input().split())))
   
honests=[]

for i in range(2**n):
  if Jud(S,n,i)==True:
    i2d=format(i,'b')
    honests.append(i2d.count('1'))

print(max(honests))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bit_count(i):

    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    i = (i + (i >> 4)) & 0x0f0f0f0f
    i = i + (i >> 8)
    i = i + (i >> 16)
    return i & 0x3f

N = INT()
A = []
for i in range(N):
    a = []
    for j in range(INT()):
        x, y = MAP()
        a.append((x-1, y))
    A.append(a)

def check(a):
    for x, y in a:
        if honest[x] == -1:
            honest[x] = y
            if y == 1:
                if not check(A[x]):
                    return False
        elif honest[x] != y:
            return False
    return True

ans = 0
for S in range(1<<N):
    honest = [-1] * N
    valid = True
    for i in range(N):
        if S & (1<<i):
            honest[i] = 1
        if S & (1<<i):
            if not check(A[i]):
                valid = False
        if S & (1<<i):
            if not check(A[i]):
                valid = False
    if valid:
        ans = max(ans, bit_count(S))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
XY = []
ans = 0
for i in range(n):
  a = int(input())
  XY.append([])
  for j in range(a):
    XY[i].append(list(map(int,input().split())))
for i in range(n**2):
  i = format(i, 'b')
  i = i.zfill(n)
  temp = i.count("1")
  temp2 = 0
  for j in range(n):
    if i[j] == "1":
      for k in range(len(XY[j])):
        if str(XY[j][k][1]) != i[XY[j][k][0]-1]:
          temp2 = 1
          break
  if temp2 == 0:
    if ans < temp:
      ans = temp
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
def main():

    N = int(input())
    dh = collections.defaultdict(set)
    dl = collections.defaultdict(set)
    for i in range(1, N+1):
        A = int(input())
        for _ in range(A):
            x, y = map(int, input().split())
            if y == 1:
                dh[i].add(x)
            else:
                dl[i].add(x)

    case = [[0], [1]]
    for _ in range(N-1):
        temp = []
        for lv in case:
            temp.append(lv + [0])
            temp.append(lv + [1])
        case = temp

    ans = 0
    for lv in case:
        h = set()
        l = set()
        # print(h)
        # print(lv)
        for i in range(len(lv)):
            if lv[i] == 1:
                h.add(i+1)
                h |= dh[i+1]
                l |= dl[i+1]
        addh = set()
        addl = set()
        for i in h:
            addh |= dh[i]
            addl |= dl[i]
        h |= addh
        l |= addl
        # print(h.intersection(l), h, l)
        if len(h.intersection(l)) == 0:
            ans = max(ans, len(h))
    return ans



if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

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

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

ans = 0
for i in range(2 ** n):
    honests = [(i >> j) & 1 for j in range(n)]
    conf = False
    for v in range(n):
        for nv, h in a[v]:
            if (honests[v] and h != honests[nv]) or (not honests[v] and h == honests[nv]): conf = True
            
    if not conf:
        ans = max(ans, sum(honests)) 

print(ans)

Submission status: Wrong Answer

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

flg = False
for _ in range(N):
    a = int(input())
    comment = [[int(_) for _ in input().split()] for i in range(a)]
    if a:
        flg=True
    C.append(comment)
if not flg :
    print(N)
    exit()


def bit_tbl2(length):
    _format = "{:0" + str(length) + "b}"
    for i in range(int('1' * length, 2) + 1):
        yield _format.format(i)


ans = 0
for b in bit_tbl2(N):
    # print(b)
    syo = [-1] * (N + 1)
    flg = False
    for i in range(N):
        if b[i] == '1':
            syo[i+1] = 1

    for i in range(N):
        if b[i] != '1': continue

        for x, y in C[i]:
            if syo[x] != -1 and y != syo[x]:
                flg = True
                break
            syo[x] = y

        if flg: break

    if not flg:

        v = 0
        for x in syo:
            if x == 1: v += 1
        # print(v)

        ans = max(ans, v)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())

kind=[]
for x in range(N):
    kind.append(0)



for n in range(N):
    num=int(input())
    for op in range(num):
        x, y = list(map(int,input().split()))
        if y==0:
            y=-1
        kind[x-1]+=y

#print(kind)
result=max(kind)
if result>0:
    print(result+1)
elif result<0:
    print(1)
else:
    print(result)

Submission status: Wrong Answer

Solution code:

from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = False
show_flg = True

p = None
XY = None
N = None


def dfs(XY, cur, ans_list):
    if cur == N:
        # print(len([i for i in ans_list if i != 0]))
        return len([i for i in ans_list if i != 0])

    _ans_list = [i for i in ans_list]
    for xy in XY[cur]:
        if _ans_list[xy[0]-1] == -1 or _ans_list[xy[0]-1] == xy[1]:
            _ans_list[xy[0]-1] = xy[1]
        else:
            return 0

    ret0 = dfs(XY, cur+1, _ans_list)

    _f_ans_list = [i for i in ans_list]
    _f_ans_list[cur] = 0
    ret1 = dfs(XY, cur+1, _f_ans_list)

    return max(ret0, ret1)


def main():
    global p
    global XY
    global N
    N = I()
    XY = [[] for i in range(N)]
    p = [[] for i in range(N+1)]

    for i in range(N):
        a = I()
        for j in range(a):
            x, y = MI()
            XY[i].append((x, y))
            p[x].append(y)

    # print(XY)
    print(dfs(XY, 0, [-1] * N))
    # flag = True
    # for i in range(1, len(p)):
    #     if len(p[i]) == 1 and p[i][0] == 0:
    #         flag = flag and True
    #     else:
    #         flag = flag and False

    # if flag:
    #     print(1)
    #     return

    # ans = 0
    # for i in range(1, len(p)):
    #     # print(sum(p[i]), len(p[i]))
    #     if sum(p[i]) == len(p[i]):
    #         ans += 1

    # print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
xys = []
for k in range(n):
    a = int(input())
    xys.append([])
    for i in range(a):
        xy = list(map(int, input().split()))
        xy[0] -= 1
        if xy[1] == 0:
            xy[1] = -1
        xys[-1].append(xy)
        

best = 0
for l in range(n):
    hantei = [0 for _ in range(n)]
    hantei[l] = 1
#     xys = xys[1:] + [xys[0]]
    flag = 0
    que = [l]
    done = []
    while len(que) > 0:
        i = que[0]
        a = xys[i]
        done.append(i)
        que = que[1:]
#     for i, a in enumerate(xys):
        #print("---")
        #print("done", done)
        #print("que", que)
        #print("han", hantei)
        #print("flag", flag)
        #print("a", a)
        for k, b in enumerate(a):
            if b[0] not in done:
                que.append(b[0])
            #print("b", b)
            if hantei[b[0]] == 0:
                hantei[b[0]] = b[1]
                #print("hantei", hantei)
            else:
                if hantei[b[0]] == b[1]:
                    if hantei[i] == -1:
                        flag = -1
                else:
                    if hantei[i] == 1:
                        flag = -1
                        #print("i", i)
                        #print("bad")
        #print("que", que)
        
    if flag == 0:
        if best < np.sum(np.array(hantei) == 1):
            best = np.sum(np.array(hantei) == 1)


print(best)

Submission status: Wrong Answer

Solution code:
n = int(input())
ls_n = [[1]*n for i in range(n)]
# print(ls_n)
ans = n
for i in range(n):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        ls_n[i][x-1] = y

for i in range(n):
    for j in range(i+1,n):
        if ls_n[i][j] * ls_n[j][i] == 0:
            ans -= 1
print(ans)