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

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

ans = 0
for i in range(2 ** N):
    check = [-1] * N #1:正直者、0:不親切
    count = 0 #カウント用
    flag = True
    for j in range(N):
        if (i >> j) & 1: #正直者のとき
            if check[j] == 0:
                flag = False
                break
            else:
                check[j] == 1
            count += 1
            for x, y in lst[j]:
                if y == 1:
                    if check[x] != 0:
                        check[x] = 1
                    else:
                        flag = False
                        break
                else:
                    if check[x] != 1:
                        check[x] = 0
                    else:
                        flag = False
                        break
        else:
            if check[j] == 1:
                flag = False
                break
            else:
                check[j] = 0

        if flag == False:
            break
    if flag:
        # print (i)
        # print (check, flag)
        ans = max(ans, count)

print (ans)
# print (lst)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = int(input())
data_dict = {}
for i in range(1, n + 1):
    temp = int(input())
    temp_list = []
    for j in range(0, temp):
        x, y = map(int, input().split())
        temp_list.append(x)
        temp_list.append(y)
    data_dict[i] = temp_list
max_o_man = 0
for i in range(1, n + 1):
    check_dict = {}
    check_list = [-100] * n
    check_list[i-1] = 1
    check_dict[i] = 1
    count = 1
    for j in range(0, len(data_dict[i]), 2):
        check_dict[data_dict[i][j]] = data_dict[i][j+1]
        check_list[i-1] = 0
        if data_dict[i][j+1] == 1:
            count += 1
    flag = 1
    for k in range(0, n - 1):
        x = -1
        if 0 not in check_list:
            x = check_list.index(-100)
        else:
            x = check_list.index(0)
        check_list[x] = 1
        for j in range(0, len(data_dict[x + 1]), 2):
            if data_dict[x + 1][j] in check_dict:
                if check_dict[data_dict[x + 1][j]] != data_dict[x + 1][j+1]:
                    flag = 0
                    break
            else:
                check_dict[data_dict[x + 1][j]] = data_dict[x + 1][j+1]
                check_list[x] = 0
                if data_dict[x + 1][j+1] == 1:
                    count += 1
        if flag == 0:
            break
    if flag == 1:
        if max_o_man < count:
            max_o_man = count
        if max_o_man == n:
            break
print(max_o_man)

Submission status: Wrong Answer

Solution code:
n = int(input())

l = [[-1]*n for _ in range(n)]

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

#print(l)
ans = 0
for i in range(2 ** n):
  #ans_ = 0
  flag = 0
  for j in range(n):
    if ((i >> j) & 1):
      #ans_ += 1
      for k in range(n):
        if l[j][k] == 1 and ((i >> k) & 1)==1:
          continue
        elif l[j][k] == 0 and ((i >> k) & 1)==0:
          continue
        elif l[j][k] == -1:
          continue
        else:
          #print(l[j][k], (i >> k))
          flag = 1
    else:
      for k in range(n):
        if l[j][k] == 0 and ((i >> k) & 1) == 1:
          continue
        elif l[j][k] == 1 and ((i >> k) & 1) == 0:
          continue
        elif l[j][k] == -1:
          continue
        else:
          #print(l[j][k], (i >> k))
          flag = 1
  if flag == 0:
    ans_ = 0
    for p in range(n):
      if ((i >> p) & 1):
        ans_ += 1
    ans = max(ans, ans_)

print(ans)

Submission status: Wrong Answer

Solution code:
num = int(input())


temp2_list = []

for i in range(num):
    A = int(input())

    temp1_list = []
    for j in range(A):
        temp1_list.append([int(k) for k in input().split()])

    temp2_list.append(temp1_list)

right_agree = 0
ng_agree = 0
un_agree = 0
unknown = 0


temp4_list = []
for i in range(num):
    temp3_list = [-1] * num
    for k in range(len(temp2_list[i])):
        # print(temp2_list[i][k][0])
        temp3_list[temp2_list[i][k][0]-1] = temp2_list[i][k][1]
    temp4_list.append(temp3_list)

for i in range(num):
    for k in range(num):
        if i !=k:
            if temp4_list[i][k] == temp4_list[k][i] and temp4_list[i][k] == 1:
                right_agree += 1
            elif temp4_list[i][k] == temp4_list[k][i] and temp4_list[i][k] == 0:
                ng_agree += 1
            elif temp4_list[i][k] != temp4_list[k][i]:
                un_agree += 1
            else:
                unknown += 0

# print(right_agree, ng_agree, un_agree, unknown)
# print(temp4_list)

res1 = (right_agree - un_agree)//2
res2 = num - ng_agree//2 - un_agree//2

print(max(res1,res2))

Submission status: Wrong Answer

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

for i in honest1:
    if honest1[i].count(1) > honest1[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
    else:
        f = 0
        for j in dic[i]:
            if j[1] != honest[j[0]]:
                f = 1
                break
        if f == 0:
            honest[i] = True

c = 0
for i in honest:
    if honest[i]:
        c += 1
print(c)

Submission status: Wrong Answer

Solution code:
n=int(input())
La=[]
L=[]
for i in range(n):
    a=int(input())
    La.append(a)
    LL=[]
    for j in range(a):
        x,y=map(int,input().split())
        LL.append((x,y))
    L.append(LL)
J={}
c=0
for i in range(n):
    for j in range(La[i]):
        if L[i][j][0] not in J:
            J[L[i][j][0]]=L[i][j][1]
        else:
            if J[L[i][j][0]] != L[i][j][0]:
                c+=1

if sum(J.values())==0:
    print(1)
else:
    print(n-c)

Submission status: Wrong Answer

Solution code:
# coding:utf-8

N = int(input())
statements = [[] for _ in range(N)]
for i in range(N):
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split(' '))
        statements[i].append((x, y))

ans = 0
for i in range(2**N):
    assumption = [int(num) for num in bin(i)[2:].rjust(N, '0')]
    appropriate = True
    for j, p in enumerate(assumption):
        for s in statements[j]:
            if (p == 1 and assumption[s[0] - 1] != s[1]) or (p == 0 and assumption[s[0] - 1] != abs(s[1]-1)):
                appropriate = False
                break

    if appropriate and ans < assumption.count(1):
        ans = assumption.count(1)

print(ans)

Submission status: Wrong Answer

Solution code:
import math

# 人の数(整数)の入力
N = int(input())

i = 1
q = 1
j = 0

ans = []

while i <= N:

    a = int(input())
    while q  <= a:
        
        # スペース区切りの整数の入力
        x, y = map(int, input().split())
        
        if a >1:
            if y == 1:
                j = 1
            elif y == 0:
                j = 0
        else:
            if y == 1:
                j = 1
                
        q += 1

    ans.append(j)
    
    q = 1
    j = 0
    i += 1
    
print(sum(ans))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
xy=[]
for i in range(n):
    ai=int(input())
    a.append(ai)
    xyi=[]
    for j in range(ai):
        xyj=list(map(int,input().split()))
        xyi.append(xyj)
    xy.append(xyi)
#print(xy)

ans=0
for i in range(2**n):
    person=[-1 for _ in range(n)]
    bit_i=format(i,'b').zfill(n)
    clear=True
    for j in range(n):

        if(person[j] == -1):
            person[j] = int(bit_i[j])
            if(int(bit_i[j]) == 0):
                continue
        elif(person[j] != int(bit_i[j])):
#            print("{0} {1} a".format(bit_i,person))
            clear=False
            break

        xyj=xy[j]
        for k in range(len(xyj)):
            if(person[xyj[k][0]-1] == -1):
                person[xyj[k][0]-1] = xyj[k][1]
            elif(person[xyj[k][0]-1] != xyj[k][1]):
#                print("{0} {1} b".format(bit_i,person))
                clear=False
                break

        if(not clear):
            break

    if(clear and (ans < list(bit_i).count("1"))):
#        print(bit_i)
#        print(person)
        ans = list(bit_i).count("1")

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import zip_longest as zi
n=int(input())
hil=[ [ [],[] ] for i in range(n)]
for i in range(n):
  hint=int(input())
  if hint:
    for j in range(hint):
      a,s=map(int,input().split())   
      hil[a-1][s]+=[i]

ans=0
for i in range(2**n)[::-1]:
  ss=bin(i)[2:]
  s="0"*(n-len(ss))+ss
  sset=set([fg for fg in range(n) if s[fg]=="1"])
  for kk in sset:
    j,k=hil[kk]
    j,k=set(j),set(k)
    if len(j&sset) or len(k-sset):
      break
  else:
    ans=max(ans,len(ss.replace("0","")))
print(ans)

Submission status: Wrong Answer

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

for i in range(N):
  a = int(input())
  for j in range(a):
    x,y = map(int,input().split())
    list[i].append([x,y])
#print(list)

ans = 0
for i in range(2**N):
    flg = False
    do = [0] * N
    for j in range(N):
      if ((i >> j) & 1):
        do[j] = 1#ショウジキモノ＝１
    #print("do",do)
    P = [-1] * N
    for n in range(N):
      for p in list[n]:
        if P[p[0]-1] == -1:
          #print(P[n])
          #print(p[0][1])
          if do[n] == 1:
            P[p[0]-1] = p[1]
          else:
            if p[1] == 1:
              P[p[0]-1] = 0
            else:
              P[p[0]-1] = 1
          if P[p[0]-1] != do[p[0]-1]:
            flg = True
        else:
          if P[p[0]-1] != do[p[0]-1]:
            flg = True
          #elif do[n] != P[p[0]-1]:
          #  flg = True
          elif do[n] == 1 and P[p[0]-1] != P[n]:
            flg = True
          elif do[n] == 0 and P[p[0]-1] == P[n]:
            flg = True
    #print("P",P)
    if flg:
      continue
    #print("this")
    ans = max(ans,sum(do))
    #print(ans)
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
    for j in range(N):
        if i >> j & 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] != _y:
                    flag = False
                if tmp[j] == -1:
                    tmp[j] = 1
                elif tmp[j] != 1:
                    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:
                    if _y == tmp[_x]:
                        flag = False
                if tmp[j] == -1:
                    tmp[j] = 0
                elif tmp[j] != 0:
                    flag = False

    if flag:
        ans = max(ans, sum(tmp))
print(ans)

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[j].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:
# -*- 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 range(N):
		if flg[i] == 0 and flg_n[i] == 0:
			ans += 1
		elif flg[i] >= 1 and flg_n[i] == 0:
			ans += 1
		elif flg[i] == 0 and flg_n[i] >= 1:
			ans2 += 1

	#print(flg)
	#print(flg_n)
	print(ans + int(ans2 // 2))



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import itertools

def check(x, t_user):
    for a, user_data in enumerate(x):
        flag = a in t_user
        for check_data in user_data:
            if not flag:
                check_data[1] = 0 if check_data[1] == 1 else 1
            if bool(check_data[1]) == bool(check_data[0] in user_data):
                return 0
    return 1

def main():
    N = int(input())
    x = []
    for _ in range(N):
        x.append([])
        M = int(input())
        for _ in range(M):
            x[-1].append([int(x) for x in input().split()])

    user = list([x for x in range(N)])
    for t_num in reversed([(x+1) for x in range(N)]):
        for t_user in itertools.combinations(user, t_num):
            ans = check(x, t_user)
            if ans == 1:
                print(t_num)
                return
    print(0)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
total = list()
good = 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()
    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:
            try:
                good_person.remove(a)
            except(Exception):
                pass
        print("check 1",good_person)
    print("check 2",good_person)
    good.append(good_person)

print(len(good)-1)

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

Submission status: Wrong Answer

Solution code:
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:
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(1, 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:
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:
# -*- 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 range(N):
		if flg[i] == 0 and flg_n[i] == 0:
			ans += 1
		elif flg[i] == 1 and flg_n[i] == 0:
			ans += 1
		elif flg[i] == 0 and flg_n[i] == 1:
			ans2 += 1

	#print(flg)
	#print(flg_n)
	print(ans + int(ans2 // 2))



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import sys
import itertools

input = sys.stdin.readline

n = int(input())
a_s = [0] * n
xss = []
yss = []
for i in range(n):
	a_s[i] = int(input())
	xss.append([])
	yss.append([])
	for _ in range(a_s[i]):
		x, y = map(int, input().split())
		xss[i].append(x)
		yss[i].append(y)

print(xss)
print(yss)

tmp_shojiki = [True] * n
for i in range(n):
	for shojiki in set(itertools.permutations(tmp_shojiki)):
		# print(i, shojiki)
		all_shojiki = True
		for j in range(n):
			if not shojiki[j]:
				continue
			for k in range(a_s[i]):
				x, y = xss[j][k] - 1, yss[j][k]
				if y == 1:
					if shojiki[x] == False:
						all_shojiki = False
				else:
					if shojiki[x] == True:
						all_shojiki = False
		if all_shojiki:
			print(n - i)
			sys.exit()

	tmp_shojiki[i] = False

print(0)

Submission status: Wrong Answer

Solution code:
import bisect
from itertools import chain, combinations
from math import ceil, floor, sqrt

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1, 0, -1))

N = int(input())
lN = [n for n in range(N)]
lA = []
lxy = [[] for _ in range(N)]
for i in range(N):
    ai = int(input())
    lA.append(ai)
    for _ in range(ai):
        xij, yij = list(map(int, input().split()))
        xij -= 1
        lxy[i].append((xij, yij))

# iter all of powersets inverse
ans = 0
for s in powerset(lN):
    # print(s) # assumed polite
    allflag = True
    range = [None] * N
    for elem in s:
        range[elem] = True
    for elem in s:
        ai = lA[elem]
        lxyi = lxy[elem]
        flag = True
        for xi, yi in lxyi:
            if yi == 0:
                if xi in s:
                    flag = False
                    break
            if yi == 1:
                # print(xi, yi, lxy[xi])
                for xii, yii in lxy[xi]:
                    if xii == elem and yii != 1:
                        flag = False
                        break
        # print("  ", flag, lxy[elem])
        if not flag:
            allflag = False
            break
    if allflag:
        ans = len(s)
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())

L = [[-1 for j in range(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



ans = 0
for i in range(2**(N)):
    if len(str(bin(i))[2:]) < N:
        K = ["0"] * (N-len(str(bin(i))[2:])) + list(str(bin(i))[2:])
    else:
        K = list(str(bin(i))[2:])
    for j in range(N):
        flag = 1
        if K[j] == "0":
            continue
        for l in range(N):

            
            if L[j][l] == -1:
                continue
            elif L[j][l] == 0:
                if K[l] == "1":
                    flag = 0
                    break
            elif L[j][l] == 1:
                if K[l] == "0":
                    flag = 0
                    break
        if flag == 0:
            break
        if j == N-1:
            ans = max(ans, K.count("1"))

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
dic = defaultdict(list)
A = []
for i in range(N):
    a = int(input())
    A.append(a)
    for j in range(a):
        x,y = map(int,input().split())
        dic[i].append((x-1,y))
# print(dic)

ans = []
for i in range(N):
    p = [-1] * N
    p[i] = 1
    for x,y in dic[i]:
        p[x] = y
    flg = True
    # print(p,i)
    for j in range(N):
        if j == i: continue
        for xj,yj in dic[j]:
            if p[j] == 0:
                if yj == 1: yj = 0
                elif yj == 0: yj = 1
            if p[xj] != yj:
                if p[xj] == -1: p[xj] = yj
                elif p[j] == -1: p[j] = 0
                else:
                    flg = False
                    break
        if not flg:
            p = [0]
            break
    # print(p)
    ans.append(p.count(1)+p.count(-1))
print(max(ans))

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]+list(range(n))
    done = []
    while len(que) > 0:
        i = que[0]
        que = que[1:]    
        if i in done:
            continue
        a = xys[i]
        done.append(i)

#     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]
                if b[1] == -1:
                    done.append(b[0])
                #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:
import sys
input = sys.stdin.readline
 
N=int(input())
box = [1]*N

chk=0
for i in range(N):
  Ai = int(input())
  for j in range(Ai):
    x,y=map(int,input().split())
    if y==0:
      box[x-1]=y
    else:
      chk=1

total=sum(box)
if total == 0 and chk == 0:
  print(1)
elif total == 0 and chk==1:
  print(0)
else:
  print(max(total,N-total))

Submission status: Wrong Answer

Solution code:
import sys

N = int(sys.stdin.readline())
H = [[0 for _ in range(N)] for _ in range(N)]
L = [[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]:
                cnt +=1
print(cnt//2)

Submission status: Wrong Answer

Solution code:
n=int(input())

sei={}
uso={}

ninzu=0
for j in range(1,n+1):
    i=int(input())
    sei[j]=set([j])
    uso[j]=set([])
    for _ in range(i):
        x,y=map(int,input().split())
        if y==1:
            sei[j].add(x)
        else:
            uso[j].add(x)

#print(sei)
#print(uso)

def saikiSei(k):
    temp=sei[k]
    for item in temp:
        if item not in saiki_sei:
            saiki_sei.add(item)
            saikiSei(item)
    return




cnt=0
for i in range(1,n+1):
    saiki_sei=set([])
    saiki_uso=set([])
    saikiSei(i)
    
    for item in saiki_sei:
        saiki_uso=saiki_uso|uso[item]

    if saiki_sei.isdisjoint(saiki_uso):
        cnt=max(cnt,max(1,len(saiki_sei)))

print(cnt)