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:
from collections import defaultdict

N = int(input())
L = [[] for _ in range(N)]

for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split())
        x -= 1
        L[i].append((x, y))

ans = 0
for s in range(1 << N):
    honest = 0
    D = defaultdict(list)
    for i in range(N):
        if s >> i & 1:
            honest += 1
            D[i].append(1)
            for x, y in L[i]:
                D[x].append(y)
        else:
            D[i].append(0)
            for x, y in L[i]:
                if y == 0:
                    D[x].append(1)
                else:
                    D[x].append(0)

    mujun = False
    for k, v in D.items():
        if len(set(v)) > 1:
            mujun = True

    if not mujun:
        ans = max(ans, honest)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
malz = [1]*N
bons = [0]*N
for _ in range(N):
    a = int(input())

    for i in range(a):
        x,y = map(int,input().split())

        if (y==0):
            malz[x-1] = 0
        else:
            bons[x-1] = 1

if sum(bons) == 0 and sum(malz) == 0:
    print (1)
else:
    print(sum(malz))

Submission status: Wrong Answer

Solution code:
N=int(input())
p=0
Q=[]
M=0
while p<N:
    A=int(input())
    M+=A
    for i in range(A):
        x=list(map(int,input().split()))
        x.insert(0,p+1)
        Q.append(x)
    p=p+1

K=0
for i in range(M):
    for j in range(i,M):
        if Q[i][0]==Q[j][1] and Q[i][1]==Q[j][0] and Q[i][2]!=Q[j][2]:
            K+=1
if N-K-1>0:
    print(N-K-1)
else:
    print(0)

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[i,x] = y
        print(m)
        if (m[x,i] == 1) and (m[i,x] == 1):
            c = c + 2
        elif (m[x,i] == 0) and (m[i,x] == 0):
            c = c + 1
            
print(c)

Submission status: Wrong Answer

Solution code:
n=int(input())
ans=[]
for i in range(n):
    t = int(input())
    tes=[list(map(int,input().split())) for j in range(t)]
    ans.append(tes)

td=[[1]*n for i in range(n)]
p=0
for i in ans:
    for j in i:
        td[p][j[0]-1]=j[1]
    p+=1

cnt=-n
for i in range(p):
    for j in range(p):
        if td[i][j] == td[j][i]:
            cnt+=1
print(cnt//2)

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]] = 10 if aa[1] == 1 else 20
	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 sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	n = INT()
	ans = []
	for j in range(n):
		dic = defaultdict(int)
		dic[j + 1] = 1
		a = INT()
		for i in range(a):
			x, y = MAP()
			if dic[i+1] == 0 :
				if y == 1:
					dic[x] = 1
				else:
					dic[x] = -1

		ans.append(n-len(dic))
	print(max(ans))

if __name__=='__main__':
	main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
L = [[] for _ in range(N)]

for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split())
        x -= 1
        L[i].append((x, y))

ans = 0
for s in range(1 << N):
    honest = 0
    D = defaultdict(list)
    for i in range(N):
        if s >> i & 1:
            honest += 1
            # D[i].append(1)
            for x, y in L[i]:
                D[x].append(y)
        else:
            # D[i].append(0)
            for x, y in L[i]:
                if y == 0:
                    D[x].append(1)
                else:
                    D[x].append(0)

    mujun = False
    for k, v in D.items():
        if len(set(v)) > 1:
            mujun = True
        if s >> k & 1:
            if v[0] == 0:
                mujun = True

    if not mujun:
        ans = max(ans, honest)

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=0
katei=0
#katei[2:]
shou=[]
for i in range(N):
    n=int(input())
    tmp=[]
    for _ in range(n):
        h=list(map(int,input().split()))
        tmp.append(h)
    shou.append(tmp)
#print(shou)
for i in range(N**2-1):
    flag=True
    tmp=str(bin(katei))[2:].zfill(N)
    state=[-1 for _ in range(N)]
    #print(tmp)
    #print()
    for j in range(N):
        #print(tmp[j])
        for k in shou[j]:
            #print(k)
            
            if tmp[j]=="0":
                if state[k[0]-1]!=-1 and state[k[0]-1]!=1-k[1]:
                    #print("false")
                    flag=False
                state[k[0]-1]=1-k[1]
            else:
                if state[k[0]-1]!=-1 and state[k[0]-1]!=k[1]:
                    #print("falkse")
                    flag=False
                state[k[0]-1]=k[1]
            #print(state)
    if flag:
        #print("collect:",tmp)
        ans=max(ans,tmp.count("1"))
            
            
    katei+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfs(u):
        for v,y in to[u]:
            if g[v]!=0:continue
            if y:g[v]=g[u]
            else:g[v]=-g[u]
            dfs(v)

    to=defaultdict(list)
    n=int(input())
    g=[0]*n
    uvy=[]
    for i in range(n):
        a=int(input())
        for _ in range(a):
            x,y=MI()
            x-=1
            to[i].append([x,y])
            to[x].append([i, y])
            uvy.append([i,x,y])
    gn=1
    for u in range(n):
        if g[u]!=0:continue
        g[u]=gn
        dfs(u)
        gn+=1
    for u,v,y in uvy:
        if (y==1 and g[u]!=g[v]) or (y==0 and g[u]==g[v]):
            print(0)
            exit()
    ans=g.count(0)
    for gi in range(1,gn):
        c0=g.count(-gi)
        c1 = g.count(gi)
        ans+=max(c0,c1)
    #print(g)
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
L = [[] for _ in range(N)]

for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split())
        x -= 1
        L[i].append((x, y))

ans = 0
for s in range(1 << N):
    honest = 0
    D = defaultdict(list)
    for i in range(N):
        if s >> i & 1:
            honest += 1
            # D[i].append(1)
            for x, y in L[i]:
                D[x].append(y)
        else:
            # D[i].append(0)
            for x, y in L[i]:
                if y == 0:
                    D[x].append(1)
                else:
                    D[x].append(0)

    mujun = False
    for k, v in D.items():
        if len(set(v)) > 1:
            mujun = True
        if s >> k & 1:
            if v[0] == 0:
                mujun = True
        else:
            if v[0] == 1:
                mujun = True

    if not mujun:
        ans = max(ans, honest)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [0] * N
B = []
for n in range(N):
    A[n] = int(input())
    bn = []
    for i in range(A[n]):
        x, y = map(int, input().split())
        bn.append((x-1, y))
    B.append(bn)

ans = 0
# bit & (1 << n) で n 番目の 0,1
for bit in range(1 << N):
    ok = [False] * N
    for n in range(N):
        if ((bit >> n) & 1) == 1:
            if all([((bit >> B[n][i][0]) & 1) == B[n][i][1] for i in range(A[n])]):
                ok[n] = True
        else:
            if all([((bit >> B[n][i][0]) & 1) != B[n][i][1] for i in range(A[n])]):
                ok[n] = True
    if all(ok):
        ans = max(ans, sum(list(map(int, format(bit, "b")))))

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    person_list = [i for i in range(1, N+1)]
    
    ans_per_dic = {}
    
    ans_pattern_dic = {}
    
    honest_pattern = combinations(N, person_list)
    
    for i in range(1, N+1):
        ans_per_dic[i] = 0
        A = int(input())
        ans_list = []
        for a in range(A):
            l = input().rstrip().split(" ")
            l = [int(x) for x in l]
            ans_list.append(l)
        ans_pattern_dic[i] = ans_list
    
    cnt = 0
    
    for pattern in honest_pattern:
        temp_dic = ans_per_dic.copy()
        for p in pattern:
            temp_dic[p] = 1
        flag = True
        for person, answer in ans_pattern_dic.items():
            if judge(temp_dic, person, answer) == False:
                flag = False
                break
        if (flag == False):
            continue
        if cnt < len(pattern):
            cnt = len(pattern)
    print(cnt)
            
def judge(temp_dic, person, answer):
    if temp_dic[person] == 1:
        for ans in answer:
            if temp_dic[ans[0]] != ans[1]:
                return False
    else:
      for ans in answer:
            if temp_dic[ans[0]] == ans[1]:
                return False
    return True
    
def combinations(n, guest_list):
    all_comb_list = []
    for i in range(2**n):
        num = i
        c_list = []
        for j in range(n):
            if num % 2 == 1:
                c_list = [guest_list[n - 1 - j]] + c_list
            num = num // 2
        all_comb_list.append(c_list)
    return all_comb_list
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N = inputInt()
	xyS = []
	for i in range(N):
		A = inputInt()
		hito = [3 for i in range(N)]

		for j in range(A):
			x,y = inputMap()
			hito[x-1] = y

		xyS.append(hito)

	ans = 0
	hafe = 0
	for i, val in enumerate(xyS):
		flg = True
		for j, vol in enumerate(val):
			if vol == 0:
				#print(xyS[j][i])
				if xyS[j][i] != 0:
					flg = False
					break
				else:
					hafe += 1
		if flg == True:
			if hafe == 2:
				hafe = 0
			else:
				ans += 1

	#print(xyS)
	print(ans)



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
n = int(input())
li = []
ans = n
for i in range(n):
  k = int(input())
  x = [list(map(int, input().split())) for _ in range(k)]
  li.append(x)
for i in range(n): #iが正直であるとして、矛盾が起こるか
  honest = []
  lier = []
  for k in range(len(li[i])):
    if li[i][k][1] == 1:
      honest.append(li[i][k][0])
      honest = list(set(honest))
    else:
      lier.append(li[i][k][0])
      lier = list(set(lier))
  for l in honest:
    for k in range(len(li[l-1])):
      if li[l-1][k][1] == 1:
        honest.append(li[l-1][k][0])
        honest = list(set(honest))
      else:
        lier.append(li[l-1][k][0])
        lier = list(set(lier))
  honest.append(i)
  honest = list(set(honest))
  sum = honest + lier
  if sum != list(set(sum)):
    ans = ans -1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [dict() for _ in range(N)] 
for i in range(N):
  a = int(input())
  for j in range(a):
    x, y = map(int, input().split())
    x -= 1
    A[i][x] = y

# print(A)
res = 0
for i in range(1,2 ** N):
  i_bin = bin(i)[2:]
  i_bin = i_bin.zfill(N)
  p = [0] * N
  for j in range(N):
    p[j] = int(i_bin[j])
  for j in range(N):
    x = i_bin[j]
    if x == '1':
      for k, v in A[j].items():
        p[k] = v
  # print(i_bin)
  # print(p)
  isPossible = True
  for j in range(N):
    if int(i_bin[j]) != p[j]: 
      isPossible = False
      break
  if isPossible:
    res = max(res, sum(p))

print(res)

Submission status: Wrong Answer

Solution code:
import itertools
import copy
N = int(input())
a = []
dic = {}
ans = [1 for _ in range(N)]
trueans = 0
for i in range(N):
  a.append(int(input()))
  dic[i] = []
  for j in range(a[-1]):
    x, y = input().split()
    dic[i].append((int(x),int(y)))
 
def check(dic, ans):
  for k, v in dic.items():
    for x, y in v:
      if ans[k]==1:
        if ans[x-1] != y:
          return False
      else:
        if ans[x-1] == y:
          return False
  return True
 
slist = []
for i in range(1, N+1):
  slist.append(i)
if check(dic, ans):
  print(N)
else:
  while(True):
    for i in range(1, N+1):
      tmp = list(itertools.combinations(slist,i))
      for t in tmp:
        anstmp = copy.deepcopy(ans)
        for t in t:
          anstmp[t-1] = 0
          flag = check(dic, anstmp)
          if flag:
            break
        if flag:
          break
      if flag:
        trueans = N - i
        break
    if flag:
      break
    break
  print(trueans)

Submission status: Wrong Answer

Solution code:
#import sys
MOD = 10 ** 9 + 7
#input = sys.stdin.readline
import math
import itertools

#import bisect

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


def main():
#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

    n = int(input())
    xy = [[] for i in range(n)]
    for i in range(n):
        a=int(input())
        for j in range(a):
            xy[i].append(list(map(int,input().split())))
    b=[-1 for i in range(n)]
    for k in range(n):
        temp = [b[i] for i in range(n)]
        temp[k]=1
        if b[k]==-1:
            b[k]=1
        for i in range(n):

            if b[i]==0:
                continue
            if temp[i]!=1 and b[i]!=1:
                continue
            for j in xy[i]:
                if temp[j[0]-1]==-1 and temp[j[0]-1]==b[j[0]-1]:
                    temp[j[0]-1]=j[1]
                elif temp[j[0]-1]!=j[1]:
                    b[k]=0
                    break
                elif b[j[0]-1]!=j[1] and b[j[0]-1]!=-1:
                    b[k]=0
                    break



    print(sum(b))




#  print(c)




            #    print(n,kingaku(a,b,x))

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]:
                    pass
#                     if hantei[i] == -1:
#                         flag = -1
#                         #print("bad***")
#                         break
                else:
                    if hantei[i] == 1:
                        flag = -1
                        #print("bad***")
                        break
                    else:
                        hantei[i] = -1
            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())
C=[[2 for i in range(N)] for j in range(N)]
#print(C)

for i in range(N):
    An=int(input())
    Ln=[list(map(int, input().split())) for j in range(An)]
    for k in range(len(Ln)):
        C[i][Ln[k][0]-1]=Ln[k][1]

Ans=0

for i in range(N):
    for j in range(N):
        if C[i][j]==C[j][i]==1:
            Ans+=2
        elif C[i][j]==C[j][i]==0:
            Ans+=1
    
print(Ans//2)

Submission status: Wrong Answer

Solution code:
num = int(input())
my_list = [["i"] for u in range(1,num+1)]
count = 0
for i in range(0,num):
    t = int(input())
    for j in range(t):
       
        lide = input().split()
        x = int(lide[0])
        y = int(lide[1])
       
        if y==0 :
            my_list[x-1].append("false")
        else:
            my_list[x-1].append("true")
        

for l in range(0,len(my_list)):
    if my_list[l].count("false") == len(my_list[l])-1 or my_list[l].count("true") == len(my_list[l])-1 or my_list[l] == "i":
        count+= 1
if count == num:
    count = 1
print(count)

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:
        # show(ans_list, 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

    _ans_list[cur] = 1
    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 sys


def main():
    # input = sys.stdin.readline
    N = int(input())

    test = [dict() for _ in range(N)]

    for i in range(N):
        M = int(input())
        for _ in range(M):
            j, b = map(int, input().split())
            test[i][j-1] = bool(b)

    count = 0

    for i in range(N):  # iが正直者と仮定
        honest = set()
        honest.add(i)
        lier = set()
        for j, b in test[i].items():  # 正直者の証言を作成
            if b:
                honest.add(j)
                for g, r in test[b].items():
                    if r:
                        honest.add(g)
                    else:
                        lier.add(g)
            else:
                lier.add(j)
        candidate = len(honest)
        for j in honest:  # 検証
            for g, r in test[j].items():
                if r:
                    if g in lier:
                        candidate = 0
                if not r:
                    if g in honest:
                        candidate = 0
        count = max(count, candidate)

    print(count)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools
n = int(input())
a = []
says = []
maxcnt = 0

for i in range(n):
    ai = int(input())
    says.append([])
    for j in range(ai):
        says[i].append(list(map(int, input().split())))
# print(says)
for i in range(n):
    # i を正直者と仮定
    true = []
    for say in says[i]:
        if say[1] == 1:
            true.append(say[0]-1)
    j = 0
    false = False
    cnt = 1
    while j < len(true):
        
        for say in says[true[j]]:
            if say[0]-1 not in true and say[1] == 1:
                true.append(say[0]-1)
                cnt += 1
            if say[0]-1 in  true and say[1] == 0:
                cnt = 0
                false = True
        if false:
            break
        j += 1
    maxcnt = max(maxcnt, cnt)
    # print(cnt)
print(maxcnt)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	n = INT()
	dic = defaultdict(int)
	dic[1] = 1
	for _ in range(n):
		a = INT()
		for i in range(a):
			x, y = MAP()
			if dic[i+1] == 0 :
				if y == 1:
					dic[x] = 1
				else:
					dic[x] = -1


	print(n-len(dic))

if __name__=='__main__':
	main()

Submission status: Wrong Answer

Solution code:
N = int(input())
table = [[-1 for _ in range(N)]for __ in range(N)]
for i in range(N):
    for _ in range(int(input())):
        x,y = map(int,input().split())
        table[x-1][i] = y
ans = N
flag = True
for i in range(N):
    fs = table[i].count(0)
    ts = table[i].count(1)
    if fs*ts != 0:
        flag = False
        ans = min(ans,max(ts,fs))

unkind = all(len(set(table[j][i] for j in range(N)))==3 for i in range(N))

if flag:
    print(N)
else:
    if unkind:
        print(0)
    else:
        print(ans+1)

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][1]==1:
            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())))
#print(S)   
honests=[]

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

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(unKind-1)
else:
    print(honest)

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 len(p[j]) == 0:
            cnt += 1
        elif 1 in p[j] and 0 in p[j]:
            return -1
        elif 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 t in group:
            if NGlist[m][t] == 1:
                flag = 1
                # break
        # if flag == 1:
            # break
    if flag == 0 and ans < len_group:
        ans = len_group

print(ans)