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:
N = int(input())
ans = 0

T = []
F = []
for _ in range(N):
    T.append(0)
    F.append(0)

for n in range(N):
    A = int(input())

    for a in range(A):
        xy = list(map(int, input().split()))
        if n == 0:
            if xy[1] == 1:
                T[xy[0] - 1] = 1
                ans += 1
            else:
                F[xy[0] - 1] = 1
        
        else:
            if T[n ] == 1:
                if xy[1] == 1:
                    T[xy[0] - 1] = 1
                    ans += 1
                else:
                    F[xy[0] - 1] = 1
            
            elif F[n] == 1:
                if xy[1] == 1:
                    F[xy[0] - 1] = 1
                else:
                    T[xy[0] - 1] = 1
                    ans += 1
            else:
                if xy[1] == 1:
                    T[xy[0] - 1] = 1
                    ans += 1
                else:
                    F[xy[0] - 1] = 1

        # print(T)
        # print(F)
        # print("\t"+str(ans))


# T.sort()
# F.sort()
# print(F)
# print()

if T == F:
    print(0)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = [[-1] * N for i in range(N)]
for i in range(N):
  A = int(input())
  for j in range(A):
    x, y = map(int, input().split())
    xy[i][x-1] = y
#print(xy)
for i in range(N):
  xy[i][i] = 1

count = 0
for i in range(N):
  count0 = 0
  count1 = 0
  for j in range(N):
    if xy[j][i] == 0:
      count0 += 1
    elif xy[j][i] == 1:
      count1 += 1
  if count1 * count0 != 0:
    count += 1
print(N - count)

Submission status: Wrong Answer

Solution code:

def dfs(i, lh):
    if i > n:
        # print(lh)
        h = sum(lh) - lh[-1]
        return h
    else:
        for j in range(1, i+1):
            if lh[j] != la[i][j] and la[i][j] != 2:
                return 0

        return max(dfs(i+1, lh + [1]), dfs(i+1, lh + [0]))


n = int(input())

la = [[2]*(n+1) for i in range(n+1)]

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

# print(la)

ans = dfs(0, [0])
print(ans)

Submission status: Wrong Answer

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()

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

for i in range(n):
  for j in range(n):
    table[i].append(-1)

for i in range(n):
  a = ni()
  for j in range(a):
    x, y = nm()
    if y == 1:
      table[i][x-1] = 1
    else:
      table[i][x - 1] = -1



def check(li):
  for i in range(n):
    for j in range(n):
      if table[i][j] == -1:
        continue
      if li[j] == 1:
        if table[i][j] == 1:
          if table[j][i] == 1 or table[j][i] == -1:
            continue
          else:
            return -1

        if table[i][j] == 0:
          if table[j][i] == 1 or table[j][i] == -1:
            continue
          else:
            return -1

      else:
        if table[i][j] == 0:
          if table[j][i] == 1 or table[j][i] == -1:
            continue
          else:
            return -1

        if table[i][j] == 1:
          if table[j][i] == 1 or table[j][i] == -1:
            continue
          else:
            return -1

  return 1


def check_all(li):
  if len(li) == n + 1:
    if check(li[1:]) == 1:
      return sum(li)
    else:
      return 9999999
  else:
    return min(check_all(li + [1]), check_all(li + [0]))


res = check_all([0])
if res == 9999999:
  print(0)
  exit()

print(n-res-1)

Submission status: Wrong Answer

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

    X.append(x)

L = []
for i in range(N):
    l = []
    for j in range(N):
        l.append(1)
    L.append(l)


for i in range(N):
    for j in range(len(X[i])):

        L[i][X[i][j][0] - 1] = X[i][j][1]

count = 0
for i in range(N):
    for j in range(N):
        if i < j:
            if L[i][j] == L[j][i]:
                count += 1

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())

dic = dict()
cnt = 0

for i in range(N):
  Row=int(input())
  List=[list(map(int,input().split())) for i in range(Row)]
  cnt += 1
  dic[cnt]=List
  
shoujiki = []
uso = []
arr = []

for i in range(N):
  cnt = 0
  shoujiki.append(i+1)
  
  for j in range(N):
    a = dic[j+1]
    length = len(a)
    
    for k in range(length):
      if i > j:
        uso.append(j+1)
      elif j+1 in shoujiki:
        if dic[j+1][k][1] == 0:
          uso.append(dic[j+1][k][0])
        else:
          shoujiki.append(dic[j+1][k][0])
          
    set(shoujiki)
    set(uso)
    cnt = len(shoujiki)
    usolength = len(uso)
    for l in range(usolength):
      if uso[l] in shoujiki:
        cnt = cnt - 1
    arr.append(cnt)
  
  shoujiki = []
  uso = []
  
print(max(arr))

Submission status: Wrong Answer

Solution code:
N = int(input())
D = [[1 for i in range(N)] for j in range(N)]
A = [0] * N
for i in range(N):
	A[i] = int(input())
	for j in range(A[i]):
		X, Y = (int(i) for i in input().split())
		if Y==0:
			D[i][X-1]=0

C = [0] * N
for i in range(N):
	for j in range(N):
		C[i]+=D[j][i]

CMIN=min(C)
if CMIN==max(C):
	if CMIN!=N:
		CMIN=0
print(CMIN)
#print(C)

Submission status: Wrong Answer

Solution code:
N = int(input())
mat = []
for i in range(N):
    A = int(input())
    tmp = [list(map(int,input().split())) for _ in range(A)]
    mat.append(tmp)
ans = N
num = list(range(1,N+1))
flag = [[[] for _ in range(2)] for _ in range(N)]
dic = dict(zip(num,flag))
count = 1
for i in mat:
    for j in range(len(i)):
        dic[i[j][0]][0].append(count)
        dic[i[j][0]][1].append(i[j][1])
    count += 1
tmp = list(dic.values())
pres = []
for i in range(len(tmp)):
    if tmp[i][0] == []:
        pres.append(i+1)
for i in range(len(pres)):
    for j in range(len(tmp)):
        for k in range(len(tmp[j][0])):
            if tmp[j][0][k] == pres[i] and tmp[j][1][k] == 0:
                tmp[j][1][k] = 1
                ans += -1
for i in range(len(tmp)):
    if 0 in tmp[i][1] and 1 in tmp[i][1]:
        ans += -1
for i in range(len(tmp)):
    if 1 in tmp[i][1]:
        break
    if 0 in tmp[i][1]:
        if i == len(tmp)-1:
            ans += -1
        else:
            continue
print(ans)

Submission status: Wrong Answer

Solution code:
total_test = int(input())
res = list()
trick_p = 0
for test in range(total_test):
	pres = list()
	total_people = int(input())
	trick_p = total_people
	for person in range(total_people):
		p, r = map(int, input().split())
		pres.append(r)
	validate = pres.count(1) - pres.count(0)	
	res.append(True) if validate >= 1 else res.append(False)
print(1 if res.count(True) == 0 and trick_p == 1 else res.count(True))

Submission status: Wrong Answer

Solution code:
import itertools
import math

people = int(input())
data = []
truthfulness = [None]*people
i = 0

def contradiction(t,data):
    for i in range(len(t)):
        if t[i] == True:
            for q in data[i]:
                if q[1] == 0:
                    a = False
                else:
                    a = True
                if not t[q[0]-1] == a:
                    return False
    return True

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

num = 0
for v in itertools.combinations_with_replacement([True,False], people):
    if(v.count(True) > num):
        if contradiction(v,data):
            num = max(v.count(True),num)
print(num)

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
flag2 = True

for i in range(N):
    truth[i] = 1
    for j in range(len(syogen[i])):
        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

        for j in range(N):
            if truth[j] == 7:
                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]:
                            flag2 = False
                            break
        if flag2:
            tmp = 0
            for j in range(N):
                if truth[j] == 1:
                    tmp += 1
            syojiki[i] = tmp
        
    truth = [7]*N
    flag = True
    flag2 = True

print(max(syojiki))

Submission status: Wrong Answer

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

    X.append(x)

L = []
for i in range(N):
    l = []
    for j in range(N):
        l.append(0)
    L.append(l)


for i in range(N):
    for j in range(len(X[i])):

        L[i][X[i][j][0] - 1] = X[i][j][1]

count = 0
for i in range(N):
    for j in range(N):
        if i < j:
            if L[i][j] == L[j][i]:
                count += 1

print(count)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
import sys
sys.setrecursionlimit(10**6)

def solve(Shogen, isHonests, manId):
  ans = True
  new_honests = []
  for x, y in Shogen[manId-1]:
    if isHonests[x-1] == -1:
      isHonests[x-1] = y
      if y == 1:
        new_honests.append(x)
    elif isHonests[x-1] != y:
      return False
  if new_honests:
    for nh in new_honests:
      ans = ans and solve(Shogen, isHonests, nh)
  return ans

N = int(input())
shogens = []
for _ in range(N):
  a = int(input())
  s = [list(map(int, input().split())) for _ in range(a)]
  shogens.append(s)
ans = 0
for begin in range(1, N+1):
  ishonests = [-1] * N
  ishonests[begin-1] = 1
  if solve(shogens, ishonests, begin):
    t = 0
    for i in ishonests:
      t += 1 if i > 0 else 0
    ans = max(ans, t)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
p=[[] for z in range(N)]
A=[0 for z in range(N)]
for i in range(N):
  A[i]=int(input())
  for j in range(A[i]):
    x1,y1=map(int,input().split())
    p[i].append([x1,y1])

q=[0 for y in range(N)]
S=0
for i in range(2**N):
  i=format(i, 'b')
  i=i.zfill(N)
  t=0
  for j in range(N):
    q[j]=int(i[j])
  for j in range(N):
    if q[j]==1:
      for k in range(N):
        if p[k] != []:
          for l in range(len(p[k])):
            if (p[k][l][0]==j and p[k][l][1]==0 and q[k]==1) or (p[k][l][0]==j and p[k][l][1]==1 and q[k]==0):
              t=t+1
    
    else:
      for k in range(N):
        if p[k] != []:
          for l in range(len(p[k])):
            if (p[k][l][0]==j and p[k][l][1]==0 and q[k]==0) or (p[k][l][0]==j and p[k][l][1]==1 and q[k]==1):
              t=t+1
  
  if t==0:
    s=sum(q)
    if s>S:
      S=s
print(S)

Submission status: Wrong Answer

Solution code:
n = int(input())
xy_lis = []
for i in range(n):
    a = int(input())
    tmp_lis = []
    for j in range(a):
        x, y = map(int, input().split())
        tmp_lis.append([x, y])
    xy_lis.append(tmp_lis)
def rec(curr, a_lis, t_p, f_p, path):
    if curr not in t_p:
        t_p.append(curr)
    for i in range(len(a_lis)):
        if a_lis[i][1] == 1:
            if a_lis[i][0] - 1 in f_p:
                return 0
            if a_lis[i][0] - 1 not in t_p:
                t_p.append(a_lis[i][0] - 1)
        else:
            if a_lis[i][0] - 1 in t_p:
                return 0
            if a_lis[i][0] - 1 not in f_p:
                f_p.append(a_lis[i][0] - 1)
    ret = 1
    path.append(curr)
    for i in range(len(t_p)):
        if t_p[i] not in path:
            ret *= rec(t_p[i], xy_lis[t_p[i]], t_p, f_p, path)
    if ret == 1:
        return 1
    else:
        return 0    
max_num = 0
for i in range(n):
    t_p = []
    f_p = []
    path = []
    if rec(i, xy_lis[i], t_p, f_p, path) == 1:
        max_num = max(len(t_p), max_num)
print(max_num)

Submission status: Wrong Answer

Solution code:
n=int(input())
count=n
honest=0

for i in range(n):
  A=int(input())
  for j in range(A):
    x,y=list(map(int,input().split()))
    if y == 0:
      count -= 1
    if y == 1:
      honest += 1
    
if honest==0:
  if n%2==0:
    print(n//2)
  else:
    print(n//2+1)
else:
  print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())

a = [None for _ in range(n)]
penalty = 0
for i in range(n):
    c = int(input())
    if i == 0:
        a[0] == 1
    for j in range(c):
        x, y = map(int, input().split(' '))
        
        if i == 0:
            a[x-1] = y
        else:
            if a[x-1] != y:
                penalty += 1
            else:
                a[x-1] = y
                
if penalty > n:
    print(0)
else:
    print(penalty)

Submission status: Wrong Answer

Solution code:
import sys

N = int(sys.stdin.readline())
H = [[0 for _ in range(N)] for _ in range(N)]
for _ in range(N):
    a = int(sys.stdin.readline())
    for i in range(a):
        x, y = map(int, sys.stdin.readline().split())
        if y==1:
            H[_][x-1]+=1
        else:
            H[_][x-1]-=1

cnt =0
for i in range(N):
    for j in range(N):
        if i !=j:
            if H[i][j] *H[j][i]>=0:
                cnt +=1
print(cnt//2)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=[]
for i in range(n):
    ansnum=int(input())
    for j in range(ansnum):
        a,b = map(int,input().split())
        arr.append((i,a,b))
#print(arr)


#スキップするユーザの選定
maxcount=0
for k in range(2**n):
    A=list(bin(k))[2:]
    #print(A[2:])
    while len(A)<n:
        A.insert(0,0)
    A=[int(i) for i in A]

    #d={}
    #print(A)
    for num,j in enumerate(arr):
        if A[j[0]]==0:
            pass
        #print(j)
        #print(j[2])
        #print(A[j[1]-1])
        elif A[j[1]-1]!=j[2]:
            break
        """
        if j[1] not in d:
            d[j[1]]=j[2]
        elif d[j[1]]!=j[2]:
            break
        """
        #print(num)
        if num==len(arr)-1: 
            maxcount=max(maxcount,sum(A))
print(maxcount)

Submission status: Wrong Answer

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

hito=[True]*N
for i in range(N-1):
    for j in range(i+1,N):
        if table[i][j]==1:
            if table[j][i]==1 or table[j][i]==None:
                continue
            else:
                hito[i]=False
                break
        if table[i][j]==0:
            if table[j][i]==0 or table[j][i]==None:
                continue
            else:
                hito[j]=False
                break
for i in range(N-1):
    if hito[i]==True and table[N-1][i]==0:
        hito[N-1]=False
    if hito[i]==False and table[N-1][i]==1:
        hito[N-1]=False

cnt=0
for i in range(N):
  if hito[i]==True:
    cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()

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

for i in range(n):
  for j in range(n):
    table[i].append(-1)

for i in range(n):
  a = ni()
  for j in range(a):
    x, y = nm()
    table[i][x-1] = y



def check(li):
  for i in range(n):
    for j in range(n):
      if table[i][j] == -1:
        continue
      if li[j] == 1:
        if table[i][j] == 1:
          if table[j][i] == 1 or table[j][i] == -1:
            continue
          else:
            return -1

        if table[i][j] == 0:
          if table[j][i] == 1 or table[j][i] == -1:
            continue
          else:
            return -1

      else:
        if table[i][j] == 0:
          if table[j][i] == 1 or table[j][i] == -1:
            continue
          else:
            return -1

        if table[i][j] == 1:
          if table[j][i] == 1 or table[j][i] == -1:
            continue
          else:
            return -1

  return 1


def check_all(li):
  if len(li) == n + 1:
    if check(li[1:]) == 1:
      return sum(li)
    else:
      return 9999999
  else:
    return min(check_all(li + [1]), check_all(li + [0]))


res = check_all([0])
if res == 9999999:
  print(0)
  exit()

print(n-res-1)

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
	flg = [0 for i in range(N)]
	flg_n = [0 for i in range(N)]
	for i, val in enumerate(xyS):
		for j, vol in enumerate(val):
			if vol == 3:
				continue
			flg[j] += vol
			if vol == 0:
				flg_n[j] += 1

	ans = 0
	ans2 = 0
	for i in flg:
		if i == 0:
			ans += 1
	for i in flg_n:
		if i == 0:
			ans += 1


	#print(flg)
	#print(flg_n)
	print(-(-ans // 2))



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

T = []
F = []
for _ in range(N):
    T.append(0)
    F.append(0)

for n in range(N):
    A = int(input())

    for a in range(A):
        xy = list(map(int, input().split()))
        if n == 0:
            if xy[1] == 1:
                T[xy[0] - 1] = 1
                ans += 1
            else:
                F[xy[0] - 1] = 1
        
        else:
            if T[n ] == 1:
                if xy[1] == 1:
                    T[xy[0] - 1] = 1
                    ans += 1
                else:
                    F[xy[0] - 1] = 1
            
            elif F[n] == 1:
                if xy[1] == 1:
                    F[xy[0] - 1] = 1
                else:
                    T[xy[0] - 1] = 1
                    ans += 1

        # print(T)
        # print(F)
        # print("\t"+str(ans))


# T.sort()
# F.sort()
# print(F)
# print()

if T == F:
    print(0)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
xy_list = []
for _ in range(N):
    xy_list.append([-1 for _ in range(N)])
    for _ in range(int(input())):
        x, y = map(int, input().split())
        xy_list[-1][x-1] = y

# print(xy_list)
max_val = 0
for i in range(N):
    temp_val = 0
    break_f = False
    for j in range(N):

        if xy_list[i][j] != 1:
            continue
        if xy_list[j][i] == 0:
            break_f = True
            break

        ok_f = True
        for k in range(N):
            if k == i or k == j:
                continue
            if xy_list[i][k] != xy_list[j][k]:
                ok_f = False
                break
        if ok_f:
            temp_val += 1
        else:
            break
    if not break_f:
        max_val = max(max_val, temp_val+1)

print(max_val)

Submission status: Wrong Answer

Solution code:

n = int(input())

a = [None for _ in range(n)]
penalty = 0
for i in range(n):
    c = int(input())
    if i == 0:
        a[0] == 1
    for j in range(c):
        x, y = map(int, input().split(' '))
        
        if i == 0:
            a[x-1] = y
        else:
            if a[x-1] != y:
                penalty += 1
            else:
                a[x-1] = y
                
if penalty > n-1:
    print(0)
else:
    print(penalty)

Submission status: Wrong Answer

Solution code:
muzyun = 0
data = {}
num = int(input())
for i in range(num):
    words = int(input())
    for j in range(words):
        a, b = input().split(' ')
        if a not in data:
            data[a] = b
        elif data[a] != b:
            muzyun = muzyun + 1
            continue
        #print(str(i+1) + ' ' + str(words) + ' ' + a + ' ' + b)

uso = 0
for i in data:
    uso = uso + int(data[i])
if uso == 0:
    print(num - 1)
else:
    print(num - muzyun)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)

n = int(input())
s_dict = {}
for i in range(n):
  add_dict = {}
  a = int(input())
  for j in range(a):
    b = list(map(int, input().split()))
    add_dict[b[0]-1] = b[1]
  s_dict[i] = add_dict
max_num = 0

def rec_get_list(i, tmp_num_list, tmp_honest, tmp_unkind):
  add_dict = s_dict[i]
  tmp_num_list.add(i)
  tmp_honest.add(i)
  for k, v in add_dict.items():
      if v:
        if k not in tmp_num_list:
        	tmp_num_list, tmp_honest, tmp_unkind = rec_get_list(k, tmp_num_list, tmp_honest, tmp_unkind)
        tmp_honest.add(k)
      else:
        tmp_unkind.add(k)
  return tmp_num_list, tmp_honest, tmp_unkind

def rec_check(i, tmp_num_list, tmp_honest, tmp_unkind):
  global max_num
  global n
  for j in range(i, n):
    use_num_list = tmp_num_list.copy()
    use_honest = tmp_honest.copy()
    use_unkind = tmp_unkind.copy()
    use_num_list, use_honest, use_unkind = rec_get_list(j, use_num_list, use_honest, use_unkind)
    check_flg = len(use_honest & use_unkind)
    if check_flg:
      return
    else:
      if len(use_num_list) > max_num:
        max_num = len(use_num_list)
    if j+1 < n:
      rec_check(j+1, use_num_list, use_honest, use_unkind)
  
rec_check(0, set(), set(), set()) 
    
print(max_num)

Submission status: Wrong Answer

Solution code:
N=int(input())

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



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][n]=y

count=N
for x in kind:
    if 1 in x and -1 in x:
        count-=1
if count==2 and N==2:
    count=1
print(count)

Submission status: Wrong Answer

Solution code:
import itertools
import math

people = int(input())
data = []
truthfulness = [None]*people
i = 0

def contradiction(t,data):
    for i in range(len(t)):
        if t[i] == True:
            for q in data[i]:
                if q[1] == 0:
                    a = False
                else:
                    a = True
                if not t[1] == a:
                    return False
    return True

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

num = 0
for v in itertools.combinations_with_replacement([True,False], people):
    if(v.count(True) > num):
        if contradiction(v,data):
            num = max(v.count(True),num)
print(num)

Submission status: Wrong Answer

Solution code:
N = int(input())
mat = []
for i in range(N):
    A = int(input())
    tmp = [list(map(int,input().split())) for _ in range(A)]
    mat.append(tmp)
ans = N
num = list(range(1,N+1))
flag = [[[] for _ in range(2)] for _ in range(N)]
dic = dict(zip(num,flag))
count = 1
for i in mat:
    for j in range(len(i)):
        dic[i[j][0]][0].append(count)
        dic[i[j][0]][1].append(i[j][1])
    count += 1
tmp = list(dic.values())
pres = []
for i in range(len(tmp)):
    if tmp[i][0] == []:
        pres.append(i+1)
for i in range(len(pres)):
    for j in range(len(tmp)):
        for k in range(len(tmp[j][0])):
            if tmp[j][0][k] == pres[i] and tmp[j][1][k] == 0:
                tmp[j][1][k] = 1
                ans += -1
for i in range(len(tmp)):
    if 0 in tmp[i][1] and 1 in tmp[i][1]:
        ans += -1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
total = list()
good = list()
bad = list()
for i in range(1,n+1):
    t = int(input())
    A = list()
    for index in range(1,t+1):
        _input = input().split(" ")
        x = int(_input[0])
        y = int(_input[1])
        A.append((x, y))
    total.append(A)

for person in total:
    good_person = list()
    bad_person = list()
    x = [x[0] for x in person]
    y = [y[1] for y in person]
    for index, a in enumerate(y):
        if a == 1:
            # good
            good_person.append(x[index])
        else:
            bad_person.append(x[index])
    #     print("check good 1",good_person)
    #     print("check bad 1", bad_person)
    # print("check good 2",good_person)
    # print("check bad 2", bad_person)
    good.append(good_person)
    bad.append(bad_person)

print(len(good) - len(bad))

Submission status: Wrong Answer

Solution code:
N = int(input())
x = [[0 for i in range(N)] for j in range(N)]
for i in range(N):
  m = int(input())
  for j in range(m):
    a = list(map(int, input().split()))
    x[i][a[0] - 1] = a[1] + 1
def f(A, ans):
  flag = 0
  for i in range(N):
    if x[A[-1]][i] != 0:
      if (x[A[-1]][i] == 1 and i in A):
        flag = 1
        break
      for j in A[:-1]:
        if x[j][i] == 3 - x[A[-1]][i]:
          flag = 1
          break
  if flag == 1:
    return (ans)
  if flag == 0:
    ans = max(ans, len(A))
    for i in range(A[-1]+1, N):
      ans = max(ans, f(A+[i], ans))
    return (ans)
print(f([0], 0))

Submission status: Wrong Answer

Solution code:
N = int(input())

import sys
input = sys.stdin.readline

testimony = {}

for n in range(1, N+1):
    A = int(input())
    testimony[n] = {}
    for _ in range(A):
        x, y = map(int, input().split())
        testimony[n][x] = y
#print(testimony)        

def dfs(idx, ans):
    #print(idx, ans)
    if not idx in testimony:
        ret = 0
        #print(ans)
        for a in ans:
            if a != 0:
                ret += 1
        return ret
    
    ans_true = ans[:]
    flag_true = True
    ans_false = ans[:]
    flag_false = True
    
    if ans[idx] == 0:
        flag_true = False
    else:
        ans_true[idx] = 1
        for k, v in testimony[idx].items():
            if ans_true[k] == 2 or ans_true[k] == v:
                ans_true[k] = v
            else:
                flag_true = False
                break
    if ans[idx] == 1:
        flag_false = False
    else:
        ans_false[idx] = 0
        for k, v in testimony[idx].items():
            v = (v+1)%2
            if ans_false[k] == 2 or ans_false[k] == v:
                ans_false[k] = v
            else:
                flag_false = False
                break
            
    if flag_false and flag_true:
        a = dfs(idx+1, ans_true)
        b = dfs(idx+1, ans_false)
        return max(a, b)
    elif flag_false:
        return dfs(idx+1, ans_false)
    elif flag_true:
        return dfs(idx+1, ans_true)
    else:
        return 0
        
    
ans = dfs(1, [0]+[2]*N)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
p=[[] for z in range(N)]
A=[0 for z in range(N)]
for i in range(N):
  A[i]=int(input())
  for j in range(A[i]):
    x1,y1=map(int,input().split())
    p[i].append([x1,y1])

q=[0 for y in range(N)]
S=0
for i in range(2**N):
  i=format(i, 'b')
  i=i.zfill(N)
  t=0
  for j in range(N):
    q[j]=int(i[j])
  for j in range(N):
    if q[j]==1:
      for k in range(N):
        for l in range(len(p[k])):
          if (p[k][l][0]==j and p[k][l][1]==0 and q[k]==1) or (p[k][l][0]==j and p[k][l][1]==1 and q[k]==0):
            t=t+1
    
    else:
      for k in range(N):
        for l in range(len(p[k])):
          if (p[k][l][0]==j and p[k][l][1]==0 and q[k]==0) or (p[k][l][0]==j and p[k][l][1]==1 and q[k]==1):
            t=t+1
  
  if t==0:
    s=sum(q)
    if s>S:
      S=s
print(S)

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])): #k番目の証言を拾う
    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 len(sum) != len(list(set(sum))):
    ans = ans -1
print(ans)