Problem:


Score : 300 points

Problem Statement

There are N people numbered 1 to N. Each of them is either an honest person whose testimonies are always correct or an unkind person whose testimonies may be correct or not.

Person i gives A_i testimonies. The j-th testimony by Person i is represented by two integers x_{ij} and y_{ij}. If y_{ij} = 1, the testimony says Person x_{ij} is honest; if y_{ij} = 0, it says Person x_{ij} is unkind.

How many honest persons can be among those N people at most?

Constraints

All values in input are integers.

1 \leq N \leq 15

0 \leq A_i \leq N - 1

1 \leq x_{ij} \leq N

x_{ij} \neq i

x_{ij_1} \neq x_{ij_2} (j_1 \neq j_2)

y_{ij} = 0, 1

Input

Input is given from Standard Input in the following format:

N
A_1
x_{11} y_{11}
x_{12} y_{12}
:
x_{1A_1} y_{1A_1}
A_2
x_{21} y_{21}
x_{22} y_{22}
:
x_{2A_2} y_{2A_2}
:
A_N
x_{N1} y_{N1}
x_{N2} y_{N2}
:
x_{NA_N} y_{NA_N}

Output

Print the maximum possible number of honest persons among the N people.

Sample Input 1

3
1
2 1
1
1 1
1
2 0

Sample Output 1

2

If Person 1 and Person 2 are honest and Person 3 is unkind, we have two honest persons without inconsistencies, which is the maximum possible number of honest persons.

Sample Input 2

3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0

Sample Output 2

0

Assuming that one or more of them are honest immediately leads to a contradiction.

Sample Input 3

2
1
2 0
1
1 0

Sample Output 3

1



Sample input:
3
1
2 1
1
1 1
1
2 0


Sample output:
2

Submission status: Wrong Answer

Solution code:
import itertools
n = int(input())
l = []
flag = True
for i in range(n):
    a = int(input())
    tmp = []
    for j in range(a):
        a1, a2 = map(int, input().split())
        if a2 == 0:
            flag = False
        l.append([i, a1, a2])

if flag:  # 全員正直の場合
    print(n)
else:
    for i in range(1, n + 1):
        # jが嘘つきと仮定する
        for j in itertools.combinations(range(n), i):
            mujun = False
            # tmp2に真偽入っている
            tmp2 = [0 if i in j else 1 for i in range(n)]
            # print(tmp2)
            for k in l:
                # print(k)
                # 嘘つきの場合
                if tmp2[k[0]] == 0:
                    if tmp2[k[1] - 1] == k[2]:
                        mujun = True
                        break  # 破綻
                # 正直者の場合
                else:
                    if tmp2[k[1] - 1] != k[2]:
                        mujun = True
                        break
            if mujun == False:
                # print('in')
                print(n - i)
                exit()
    print(0)

    # print(l)

Submission status: Wrong Answer

Solution code:

n = int(input())

hp = 0

all_z = True

for i in range(n):
  an = int(input())
  is_h = True  
  for j in range(an):
    x, y = map(int, input().split(' '))
    if y == 0:
      is_h = False
      all_z = True
    else:
      all_z = False
  if is_h:
    hp += 1
if all_z:
  hp += 1
print(hp)

Submission status: Wrong Answer

Solution code:
import itertools

N = int(input())
honesty = [[-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())
        honesty[i][x-1] = y

#bit全探索
ans = 0 
a = itertools.product([1,0], repeat = N)

Submission status: Wrong Answer

Solution code:
from sys import stdin

n = int(stdin.readline().rstrip())
ma = 0
a = []
li = []
for i in range(n):
    an = int(stdin.readline().rstrip())
    a.append(an)
    lis = [list(map(int,stdin.readline().rstrip().split())) for _ in range(an)]
    l = [2]*n
    for j in lis:
        l[j[0]-1] = j[1]
    li.append(l)
point = 0
for i in range(n):
    flag = 0
    for j in range(n):
        if li[i][j] == 1:
            for k in range(n):
                if (li[i][k] == 0 and li[j][k] == 1) or (li[i][k] == 1 and li[j][k] == 0):
                    flag = 1
        elif li[i][j] == 0:
            for k in range(n):
                if (li[i][k] == 1 and li[j][k] == 1) or (li[i][k] == 0 and li[j][k] == 0):
                    flag = 1
    if flag == 0:
        su = li[i].count(1)+1
        ma = max(su,ma)
print(ma)

Submission status: Wrong Answer

Solution code:
import copy

sw = []
N = int(input())
def create_ki(data):
    if len(data) == N:
        sw.append(data)
        return
    tmp = copy.copy(data)
    tmp.append(0)
    create_ki(tmp)
    tmp2 = copy.copy(data)
    tmp2.append(1)
    create_ki(tmp2)

create_ki([])

Speak = [{} for i in range(N)]
for i in range(N):
   A = int(input())
   for j in range(A):
       XY = input().split()
       Speak[i][XY[0]] = XY[1]


ans = 0
for peaple in sw:
    ans_list = [-1]*N
    isFalse = False
    for i in range(N):
        if isFalse:
            break
        for k, v in Speak[i].items():
            k = int(k)
            v = int(v)
            if ans_list[k-1] == -1:
                if peaple[i] == 0:
                    if peaple[k-1] == v:
                        isFalse = True
                        break
                    ans_list[k-1] = v
                else:
                    if peaple[k-1] != v:
                        isFalse = True
                        break
                    if v == 0:
                        ans_list[k-1] = 1
                    else:
                        ans_list[k-1] = 0
            else:
                if peaple[i] == 0:
                    if peaple[k-1] == v:
                        isFalse = True
                        break
                    if ans_list[k-1] == v:
                        continue
                    else:
                        isFalse = True
                        break
                else:
                    if peaple[k-1] != v:
                        isFalse = True
                        break
                    if v == 0:
                        if ans_list[k-1] == 1:
                            continue
                        else:
                            isFalse = True
                            break
                    else:
                        if ans_list[k-1] == 0:
                            continue
                        else:
                            isFalse = True
                            break
    if not isFalse:
        ans = max(ans, N-sum(peaple))

print(ans)

Submission status: Wrong Answer

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

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):
      if flg:break
      for p in list[n]:
        if P[p[0]-1] == -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[1]:
            flg = True
          elif do[n] == 0 and P[p[0]-1] == p[1]:
            flg = True
        if flg:break
    #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())
a = []
truthTable = []
for i in range(n) :
    l = []
    for j in range(n) :
        l.append(2)
    truthTable.append(l)

#print(truthTable)
for i in range(n) :
    shogen = int(input())
    for _ in range(shogen) :
        x, y = map(int, input().split())
        #print(i)
        truthTable[i][x-1] = y
        #print(truthTable)

truthList = []
for i in range(n) :
    truthList.append(1)

for i in range(n) :
    for j in range(i+1, n) :
        if truthTable[i][j] == 1 and truthTable[j][i] == 0 :
            truthList[i] = 0
            truthList[j] = 0
        if truthTable[i][j] == 0 and truthTable[j][i] == 1 :
            truthList[j] = 0
        if truthTable[i][j] == 0 and truthTable[j][i] == 0 :
            truthList[j] = 0
        if truthTable[i][j] == 0 and truthTable[j][i] == 2 :
            truthList[j] = 0
        if truthTable[i][j] == 2 and truthTable[j][i] == 0 :
            truthList[j] = 0

print(sum(truthList))

Submission status: Wrong Answer

Solution code:
n = int(input())
Asgs = list()

def get_sgs(an):
    sgs = [list(map(int, input().split())) for i in range(an)]
    return sgs


for i in range(n):
    an = int(input())
    Asgs.append(get_sgs(an))

bits = [1] * n
end = False
# print(Asgs)
# sys.exit()
last_bits = [2] * n

cnt = 0
while cnt < 5:
    for i in range(n):
        
        # i人目の意見の個数
        for j in range(len(Asgs[i])):
            # bitsには正直者と登録されている人があるひと(正直者として登録されている)を不親切というなら
            if bits[i] == 1 and Asgs[i][j][1] == 0 and bits[Asgs[i][j][0]-1] ==1:
                
                #発言者もしくは発言対象者が偽
                bits[Asgs[i][j][0]-1] = 0
                """
                bits[i] = 0
                or
                bits[Asgs[i][j][0]-1] = 0
                """
                # print(i, j)
            # 正直者とされている人が不親切とされてる人を正直者と言っている場合,発言者は不親切である。
            if bits[i] == 1 and bits[Asgs[i][j][0]-1] == 0 and Asgs[i][j][1] == 1:
                bits[i] = 0
                # print('mj11')
            
    if last_bits == bits:
        cnt += 1
    last_bits = bits
        
# print(bits)
print(sum(bits))

Submission status: Wrong Answer

Solution code:
N = int(input())
Harray = []
for i in range(N):
    Aarray = []
    A = int(input())
    for j in range(A):
        xy = list(map(int,input().split()))
        Aarray.append(xy)
    Harray.append(Aarray)

carray = []

for Ai in Harray:
    honest = [Harray.index(Ai)]
    honestcon = [Ai]
    for ans in Ai:
        que = []
        if ans[1] == 1:
            honest.append(ans[0]-1)
            honestcon.append(Harray[ans[0]-1])
            que.append(ans[0]-1)
        while len(que) > 0:
            d = que[0]

            que.pop(0)
            
            e = 0
            for h in honestcon:
                for h2 in h:
                    if h2[1] == 1:
                        h3 = [h2[0], 0]
                    else:
                        h3 = [h2[0], 1]
                    if h3 in Harray[d]:
                        e = 1
            
            for h4 in honest:
                if [h4,0] in Harray[d]:
                    e = 1
            
            if e == 0:
                for ans2 in Harray[d]:
                    if (ans2[1] == 1) and (ans2[0] not in honest):
                        que.append(ans2[0]-1)
            else:
                honest = []
                break
                    
    carray.append(len(honest))

print(max(carray))

Submission status: Wrong Answer

Solution code:
N = int(input())

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

def solve(i):
    memo = {}
    for j, a in enumerate(A):
        for x, y in a.items():
            if (i >> j) & 1 == 1:
                if x in memo and memo[x] != y:
                    return False
                memo[x] = y
            else:
                if x in memo and memo[x] != (1 - y):
                    return False
                memo[x] = (1 - y)

    for x, y in memo.items():
        if (i >> x) & 1 != y:
            return False

    return True


ans = 0
for i in range(2 ** N):
    if solve(i):
        ans = max(ans, bin(i).count("1"))

print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
from collections import defaultdict
L = defaultdict(str)
for i in range(n):
    a = int(input())
    
    for i in range(a):
        b,c = map(int,input().split())
        
        L[str(b)] += str(c)

#print(L)
li = []
for k,v in L.items():
    li.append(v)
    #print([k,v])
    #li.append(L(value))
#print(li)
cnt = 0
for i in range(len(li)):
    if "0" not in li[i]:
        cnt +=1
if cnt == 0:
    print(n-1)
else:
    cnt += n-len(li)
    print(cnt)

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
a = 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
  if count1 * count0 == 1:
    a = 1

ans = N - count + a
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(max(N - count, 1))

Submission status: Wrong Answer

Solution code:
n = int(input())
comments = []
for _ in range(n):
    a_i = int(input())
    comments_a_i = []
    for _ in range(a_i):
        x, y = map(int, input().split())
        comments_a_i.append([x - 1, y])
    comments.append(comments_a_i)

OK = 1
NG = 0
UNKNOWN = -1
validation = [[UNKNOWN for _ in range(n)] for _ in range(n)]
for i, comments_a_i in enumerate(comments):
    for comment in comments_a_i:
        ret = UNKNOWN
        if 1 == comment[1]:
            ret = OK
        elif 0 == comment[1]:
            ret = NG
        validation[i][comment[0]] = ret

unknowns = []
for i in range(n):
    is_unknown = True
    for j in range(n):
        if OK == validation[j][i] or NG == validation[j][i]:
            is_unknown = False
            break
    if is_unknown:
        unknowns.append(i)

for unknown in unknowns:
    for j in range(n):
        validation[unknown][j] = UNKNOWN

count = 0
for i in range(n):
    for j in range(n):
        if OK == validation[i][j] and OK == validation[j][i]:
            count += 2
        elif NG == validation[i][j] and NG == validation[j][i]:
            count += 1
print(count // 2)

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
	ans3 = 0
	for i in range(N):
		if flg[i] > 0:
			ans += flg[i]
		if flg_n[i] > 0:
			ans2 += flg_n[i]

	#print(flg)
	#print(flg_n)
	#print(ans)
	#print(ans2)

	if ans == ans2:
		print(0)
	elif ans > ans2:
		print(ans)
	elif ans2 > ans:
		print(ans2 // 2)



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
n = int(input())
xy = []

for i in range(n):
    a = int(input())
    temp = {}
    for j in range(a):
        x, y = map(int, input().split())
        temp[x] = y
    xy.append(temp)

# print(xy)

def solve(idx, isHonest, hList, cnt):
    if idx == n:
        return cnt
    infoMap = xy[idx]

    if isHonest:
        # self check
        if hList[idx+1] == 0:
            return 0

        cnt += 1
        for (key, value) in infoMap.items():
            if hList[key] is None:
                hList[key] = value
            elif hList[key] != value:
                return 0
    else:
        # self check
        if hList[idx+1] == 1:
            return 0

        for (key, value) in infoMap.items():
            if hList[key] is None:
                hList[key] = abs(value - 1)
            elif hList[key] != abs(value - 1):
                return 0

    return max(solve(idx+1, isHonest, hList, cnt), solve(idx+1, not isHonest, hList, cnt))


hList1 = [None] * (n+1)
hList1[1] = 1
hList2 = [None] * (n+1)
hList2[1] = 0
# ans1 = solve(0, True, hList1, 0)
# ans2 = solve(0, False, hList2, 0)
# print(ans1, ans2)

print(max(solve(0, True, hList1, 0), solve(0, False, hList2, 0)))

#print(xy)

Submission status: Wrong Answer

Solution code:
N = int(input())
list1 = [0]*N
list2 = []
list3 = [0]*N
flag = 1
count = 0

for n in range(N):
  A = int(input())
  for a in range(A):
    shougen = input().split(" ")
    if int(shougen[1]) == 1:
      flag=0
      list1[int(shougen[0])-1] += 1
    else:
      shougen.append(n+1)
      list2.append(shougen)
      
for l2 in range(len(list2)):
  if list1[int(list2[l2][2])-1] > 0:
           list3[int(list2[l2][0])-1] += 1
      
for n in range(N):
	list1[n] -= list3[n]
if flag == 0:
  count = list1.count(1)
else:
  count = 1
print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
ans_num = []
talk = []
for i in range(N):
    num = int(input())
    ans_num.append(num)
    block = []
    for j in range(num):
        x, y = map(int,input().split())
        block.append([x,y])
    talk.append(block)

dp = [[0 for j in range(N)] for i in range(N)]
for i in range(N):
    for j in range(ans_num[i]):
        a = talk[i][j][0]
        b = talk[i][j][1]
        dp[i][a-1] = b

ans = 0
count = 0

for i in range(N):
    for j in range(N):
        if dp[i][j] == 1 and dp[j][i] == 1:
            ans += 1
    count += sum(dp[i])

if count == 0:
    ans = 1

print(ans)

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 = 0
for i in range(2**N):
    bit_s = bin(i)[2:][::-1]
    bit_s = bit_s + '0'*(N-len(bit_s))
    # print(bit_s)
    T = [int(bit_s[p]) for p in range(N)]
    t = [-1 for _ in range(N)]
    flag = True
    for p in range(N):
        if T[p]:
            for j,k in enumerate(table[p]):
                if k != -1:
                    if t[j] != (k+1)%2:
                        t[j] = k
                    else:
                        flag = False
    flag2 = True
    for p,q in zip(T,t):
        if p == 1:
            if q != 1:
                flag2 = False
        if q == 1:
            if p != 1:
                flag2 = False
    if flag and flag2:
        # print('!')       
        ans = max(ans,bit_s.count('1'))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

cnt =0
for i in range(N):
    if H[i]-L[i]>=0:
        cnt +=1
print(cnt)

Submission status: Wrong Answer

Solution code:
N=int(input())
arr_N=[]
for _ in range(N):
    A=int(input())
    arr_A=[]
    for _ in range(A):
        arr_A.append(list(map(int,input().split())))
    arr_N.append(arr_A)

import itertools
TF = (1,0)
TF_v = list(itertools.product(TF,repeat=N))

def inv01(x):
    return 0 if x==1 else 1

ans = 0
for tf_v in TF_v:
    arr_tf=[]
    for i in range(N):
        if tf_v[i]==1:
            for t in arr_N[i]:
                arr_tf.append(tf_v[t[0]-1]==t[1])
        else:
            for t in arr_N[i]:
                arr_tf.append(tf_v[t[0]-1]==inv01(t[1]))
    if all(arr_tf):
        ans=max(ans,sum(tf_v))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

testinomy = [[-1 for _ in range(N)] for _ in range(N)]

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

ans = 0

for honests in range(N ** 2 - 1):
    bit = '{:015b}'.format(honests)[::-1]
    ok_flag = True
    for i in range(N):
        if bit[i] == '1':
            for j, k in enumerate(testinomy[i]):
                str_k = str(k)
                if bit[j] == '1' and str_k != '0':
                    pass
                elif bit[j] == '0' and str_k != '1':
                    pass
                else:
                    ok_flag = False
                    break
                # if str_k != '-1':
                #     if str_k == '1' and bit[j] == '1':
                #         pass
                #     elif str_k == '0' and bit[j] == '0':
                #         pass
                #     else:
                #         ok_flag = False
                #         break
        if ok_flag == False:
            break
    if ok_flag:
        ans = max(ans, sum(map(int, bit)))

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n = int(input())
t = []
l = []
for nn in range(1, n + 1):
    for _ in range(int(input())):
        x, y = [int(n) for n in input().split()]
        if y ==  1:
            t.append([nn, x])
        else:
            l.append([nn, x])
if len(l) == 0:
    print(n)
    exit()
bs = set([x[0] for x in l])
cs = set([x[1] for x in l])
if len(bs) > len(cs):
    dn = len(cs)
    ds = cs
else:
    dn = len(bs)
    ds = bs
dl = list(set(bs) | set(cs))

for nn in range(dn - 1, dn + 1):
    for it in itertools.product(list(ds), repeat=nn):
        tt = [x[1] for x in t if not x[0] in it]
        if len(set(it) & set(tt)) != 0:
            continue
        ll = [x[1] for x in l if not x[0] in it]
        if len(set([x for x in range(1, n + 1) if not x in it]) & set(ll)) == 0:
            print(n - nn)
            exit()
# for nn in range(dn - 1, len(dl) + 1):
#     for it in itertools.product(dl, repeat=nn):
#         tt = [x[1] for x in t if not x[0] in it]
#         if len(set(it) & set(tt)) != 0:
#             continue
#         ll = [x[1] for x in l if not x[0] in it]
#         if len(set([x for x in range(1, n + 1) if not x in it]) & set(ll)) == 0:
#             print(n - nn)
#             exit()
print(0)

Submission status: Wrong Answer

Solution code:
import collections
n=int(input())
l=[[-1]*n for _ in range(n)]
ans=0
for i in range(n):
  A=int(input())
  for j in range(A):
    x,y=map(int,input().split())
    l[x-1][i]=y
for m in l:
  c=collections.Counter(m)
  ans=max(ans,c[0])
print(n-ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

a = []
xys = [[] for i in range(n)]

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

p = [1 for i in range(n)]
for i in range(n):
    for j in range(a[i]):
        if ((xys[i])[j])[1] == 0:
            p[((xys[i])[j])[0] - 1] = min(1 - p[i],0)
        else:
            p[((xys[i])[j])[0] - 1] = min(1 + p[i],1)

t = 1
for i in range(n):
    if p[i] == 1:
        for j in range(a[i]):
            if p[xys[i][j][0] - 1] != xys[i][j][1]:
                t = 0

if t == 0:
    print(0)
else:
    print(sum(p))

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])
          
    shoujiki = list(set(shoujiki))
    
    shoujikilength = len(shoujiki)
    for l in range(shoujikilength):
      length2 = len(dic[shoujiki[l]])
      for m in range(length2):
        if dic[shoujiki[l]][m][1] == 0:
          uso.append(dic[shoujiki[l]][m][0])
    
    cnt = len(shoujiki)
    
    uso = list(set(uso))
    usolength = len(uso)
    for l in range(usolength):
      if uso[l] in shoujiki:
        cnt = cnt - 1
    arr.append(cnt)
  
  shoujiki = []
  uso = []
  
print(arr) 
print(max(arr))

Submission status: Wrong Answer

Solution code:
N = int(input())

x_list = []
y_list = []
Group = []
A_list = []

for n in range(N):
    A = int(input())
    A_list.append(A)
    Group.append('none')
    x = []
    y = []
    for a in range(A):
        x_tmp, y_tmp = map(int, input().split())
        x.append(x_tmp)
        y.append(y_tmp)
    x_list.append(x)
    y_list.append(y)

ans = 0
flag = False

for i in range(N):
    for a_list in range(A_list[i]):
            if y_list[i][a_list] == 1:
                if Group[i] != 'false' and Group[x_list[i][a_list]-1] != 'false':
                    Group[i] = 'true'
                    Group[x_list[i][a_list]-1] = 'true'
                elif Group[i] != 'true' and Group[x_list[i][a_list]-1] != 'true':
                    Group[i] = 'false'
                    Group[x_list[i][a_list]-1] = 'false'
                else:
                    flag = True
                    break
            if y_list[i][a_list] == 0:
                if Group[i] != 'true' and Group[x_list[i][a_list]-1] != 'false':
                    Group[i] = 'false'
                    Group[x_list[i][a_list]-1] = 'true'
                elif Group[i] != 'false' and Group[x_list[i][a_list]-1] != 'true':
                    Group[i] = 'true'
                    Group[x_list[i][a_list]-1] = 'false'                   
                else:
                    flag = True
                    break

if flag:
    print(0)
else:
    print(max(Group.count('true'), Group.count('false')))

Submission status: Wrong Answer

Solution code:
import numpy as np

n = int(input())
ans_map = np.full((1, n), 2, dtype = int)
conflict = 0

for i in range(n):
    a = int(input())
    if i:
        ans_map = np.append(ans_map, np.full((1,n), 2), axis=0)
    for j in range(a):
        x, y = list(map(int, input().split()))
        ans_map[i][x - 1] = y

honest = np.sum(ans_map==1, axis=0)
unkind = np.sum(ans_map==0, axis=0)

for i in range(n):
    for j in range(i, n):
        if not ans_map[i][j] and not ans_map[j][i]:
            conflict += 1

print(int(n - np.sum(honest & unkind) - conflict))

Submission status: Wrong Answer

Solution code:
# C問題
import numpy

N = int(input())

witness = numpy.ones((N, N)) * (-1)

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

cnt = 0
for p in range(N):
    for q in range(N):
        if witness[p, q] == witness[q, p]:
            if not p == q:
                # print('evi:', p, q)
                cnt += 1

# print(witness)
print(cnt // 2)

Submission status: Wrong Answer

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

for i,v in enumerate(range(N)):
  l.append([])
  num = int(input())
  for j in range(num):
    a,b = map(int, input().split())
    l[i].append([a,b])

result = []
for i in range(N):
  result.append([])

for i in l:
  for j in i:
  	result[j[0]-1].append(j[1])
cnt = 0
if N != 2:
  for i in result:
    if len(set(i)) != 2:
      cnt += 1
else:
  if result[0] == 1 and result[1] == 1:
    cnt = 2
  else:
    cnt = 1
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
tf_dict = {}
for i, n in enumerate(range(N)):
    A = int(input())
    tmp_dict = {}
    for a in range(A):
        xy = input().split()
        tmp_dict[int(xy[0])] = int(xy[1])
    tf_dict[i+1] = tmp_dict

True_set = set()
False_set = set()
for key in tf_dict.keys():
    for item in tf_dict[key].items():
        if item[1] == 1:
            if (item[0] not in True_set) & (item[0] not in False_set):
                True_set.add(item[0])
                True_set.add(key)
            elif (item[0] in True_set):
                True_set.add(key)
            elif (item[0] in False_set):
                False_set.add(key)
        if item[1] == 0:
            if (item[0] not in True_set) & (item[0] not in False_set):
                False_set.add(item[0])
                True_set.add(key)
            elif (item[0] in True_set):
                False_set.add(key)
            elif (item[0] in False_set):
                True_set.add(key)
                
if len(False_set & True_set) != 0:
    print("0")
else:
    print(len(True_set))

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = []

for i in range(n):
  c = (int(input()))
  check = [0 for i in range(n)]
  for k in range(c):
    a, b = (map(int, input().split()))
    if b == 1:
      check[a-1] = 1
    elif b == 0:
      check[a-1] = -1
  ans.append(check)
  
count = 0
m = 0
for i in range(n):
  count = 0
  s = [ans[i][j] for j in range(n)]
  for j in range(i+1, n):
    flag = True
    for k in range(n):
      if(s[k]==-1 and (s[k]+ans[j][k])>= 0) or (s[k]==1 and (s[k]+ans[j][k]) <= 0):
        flag = False
        break
    if flag:
      count+=1
  if count > m:
    m = count
if m > 0:
  m+=1
print(m)

Submission status: Wrong Answer

Solution code:

n = int(input())

hp = 0
all_z = True

for i in range(n):
  an = int(input())
  is_h = True
  for j in range(an):
    x, y = map(int, input().split(' '))
    if y == 0:
      is_h = False
    else:
      all_z = False
  if is_h:
    hp += 1
if all_z:
  hp += 1

print(hp)