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:
# -*- 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
	for i in range(N):
		flg = True
		for j, val in enumerate(xyS):
			if val[i] == 0:
				flg = False
				break
		if flg == True:
			ans += 1

	if N == 2 and ans == 0:
		ans += 1
	#print(xyS)
	print(ans)



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

ans = 0
se=set()
for i in range(2**n):
    temp=0
    for idx,x,y in xy:
        if i>>(idx-1) & 1:
            if i>>(x-1) & 1:
                if y==1:
                    temp+=1
                else:
                    break
            else:
                if y==0 and idx not in se:
                    temp+=1
                    se.add(idx)
                else:
                    break
            
        else:
            if i>>(x-1) & 1:
                if y==1:
                    break
                else:
                    continue
            else:
                if y==0:
                    break
    else:
        ans=max(ans,temp)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product
n = int(input())

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

ans = 0
for l in product([0, 1], repeat=n):
    isOK = True

    for i in range(n):
        honest = l[i]
        s = say[i]
        for x, y in s:
            isHonest = l[x]
            said = honest ^ y
            if not isHonest ^ said:
                isOK = False
                break

        if not isOK:
            break
    if isOK:
        ans = max(ans, sum(l))

print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(2**N):
    flag = False
    cnt = 0
    memo2 = [None for i in range(N)]
    # print(i, ans)
    for ii, b in enumerate(bin(i)[2:].zfill(N)):
        b = int(b)
        if b:
            if memo2[ii] and memo2[ii] != b:
                flag = True
                break
            else:
                memo2[ii] = b
                cnt += b
            for x, y in memo[ii]:
                if memo2[x] and memo2[x] != y:
                    flag = True
                    break
                else:
                    memo2[x] = y
        else:
            if memo2[ii] and memo2[ii] != b:
                cnt = 0
                break
            else:
                memo2[ii] = b
            for x, y in memo[ii]:
                if memo2[x] and memo2[x] == y:
                    cnt = 0
                    flag = True
                    break
                else:
                    memo2[x] = int(not y)
        if flag:
            break
    if flag:
        continue
    ans = max(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
dic = []
ls = [[] for i in range(N)]
for i in range(N):
  a = int(input())
  dic += [a]
  for j in range(a):
    x, y = map(int, input().split())
    ls[i] += [(x-1,y)]
ans = 0
for i in range(2**N):
  inf = []
  for j in range(N):
    if i%2==0:
      inf += [1]
    else:
      inf += [0]
    i >>= 1
  m = 0
  flag = False
  for j in range(N):
    for h in range(dic[j]):
      x, y = ls[j][h]
      if inf[j]==1:
        m += 1
        if inf[x]!=y:
          flag = True
          break
      else:
        break
    if flag:
      break
  else:
    if ans<m:
      ans = m
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
people = [[] for i in range(n)]
for i in range(n):
  a = int(input())
  for j in range(a):
    say = tuple(map(int,input().split()))
    people[i].append(say)

ans = 0
for i in range(2**n):
  TF = [ 1 & i >> j for j in range(n)]
  bool = True
  for j in range(n):
    if TF[j] == 1:
      for says in people[j]:
        if TF[says[0]-1] == says[1]:
          pass
        else:
          bool = False
          break
    else:
      for says in people[j]:
        if TF[says[0]-1] == says[1]:
          bool = False
          break
        else:
          pass
  if bool:
    ans = max(ans,TF.count(1))

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = 0
mainasu = 0
L = []
for i in range(N):
    A = []
    x = int(input())
    for j in range(x):
        a,b = map(int,input().split())
        A.append((a,b))
    L.append(A)
for i,j in enumerate(L):
    for a,b in j:
        for v,w in L[a-1]:
            if (i +1 == v) and (b == w):
                if b == 0:
                    mainasu += 1
                ans += 1
print(ans-mainasu//2)

Submission status: Wrong Answer

Solution code:
N=int(input())
N_comment=[[2]*N for _ in range(N)]

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

true_count=0
for i in range(N):
    for j in range(i+1,N):
        if N_comment[i][j]==N_comment[j][i]:
            true_count+=1

print(true_count)

Submission status: Wrong Answer

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

import sys

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

def bit_count(i):

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

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

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

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

    for i, a in enumerate(xys):
        #print("---")
        #print(hantei)
        #print(flag)
        #print(a)
        for k, b in enumerate(a):
            #print(b)
            if hantei[b[0]] == 0:
                hantei[b[0]] = b[1]
            else:
                if hantei[b[0]] == b[1]:
                    if hantei[i] == -1:
                        flag = -1
                else:
                    if hantei[i] == 1:
                        flag = -1
                        #print(i)
                        #print("bad")

    if flag == 0:
        if best < np.sum(np.array(hantei) == 1):
            best = np.sum(np.array(hantei) == 1)


print(best)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
xy = [[] for i in range(n)]
for i in range(n):
    ai = int(input())
    a.append(ai)
    for j in range(ai):
        xyi = list(map(int, input().split()))
        xy[i].append(xyi)
res = 0
for i in range(n ** 2):
    flag = [(1 if i & 2 ** b == 2 ** b else 0) for b in range(n)]
    outs = 0
    for j in range(n):
        if flag[j] == 1:
            for k in range(a[j]):
                x, y = xy[j][k]
                x -= 1
                if flag[x] != y:
                    outs = 1
                    break
    if outs == 0:
        res = max(sum(flag), res)

print(res)

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)

num = list(range(1,N+1))
flag = [[] for _ in range(N)]
dic = dict(zip(num,flag))
for i in mat:
    for j in range(len(i)):
        dic[i[j][0]].append(i[j][1])
tmp = list(dic.values())
ans = N
for i in range(len(tmp)):
    if 0 in tmp[i] and 1 in tmp[i]:
        ans += -1
for i in range(len(tmp)):
    if 0 in tmp[i]:
        ans += -1
        break
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
B = [[] for i in range(N)]
for i in range(N):
    A = int(input())
    for j in range(A):
        x,y = map(int,input().split())
        B[i].append([x,y])
M = 2**N
max = 0
for i in range(M):
    s = [0] * N
    k = bin(i)[2:]
    for i in range(len(k)):
        s[i] = k[i]
    c = 0
    state = 1
    for i in range(N):
        if int(s[i]) == 0:
            continue
        for b in B[i]:
            if int(s[b[0]-1]) != b[1]:
                state = 0
    if state == 1:
        for t in s:
            c += int(t)
    if max <= c:
        max = c
print(max)

Submission status: Wrong Answer

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

ans = 0
for i in range(1 << N):
    a = set()
    for j in range(N):
        if i & 1 << j:
            a.add(j)

    a = list(a)
    b = set()
    flag = True
    for k in a:
        for p, q in X[k]:
            if q == 1:
                b.add(p)
            else:
                if p in a:
                    flag = False
                    break

    if flag and set(a) == b:
        ans = max(ans, len(a))

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    ans = N
    from collections import defaultdict
    d = defaultdict(set)
    liar = defaultdict(set)
    for i in range(N):
        a = int(input())
        for j in range(a):
            x, y = (int(i) for i in input().split())
            d[x].add(y)
            if y == 0:
                liar[i+1].add(x)
    for k, v in d.items():
        if len(v) == 2:
            ans -= 1
    m = 0
    for k, v in liar.copy().items():
        for vv in v:
            if k in liar[vv]:
                m += 1
    ans -= m//2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

for i in range(n):
    m = int(input())
    for j in range(m):
        x, y = map(int, input().split())
        x -= 1
        a[i].append((x, y))
    
ans = 0
for i in range(2 ** n):
    honests = [(i >> j) & 1 for j in range(n)]
    nodes = [-1] * n
    conf = False
    for v in range(n):
        for nv, h in a[v]:
            if not honests[v]: h = not h
            if h != honests[nv]:
                conf = True
                break
        if conf == True: break
    else: 
        ans = max(ans, sum(honests))

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
B = [[] for i in range(N)]
for i in range(N):
    A = int(input())
    for j in range(A):
        x,y = map(int,input().split())
        B[i].append([x,y])
M = 2**N
max = 0
for i in range(M):
    s = [0] * N
    k = bin(i)[2:]
    for i in range(len(k)):
        s[i] = k[i]
    c = 0
    state = 1
    for i in range(N):
        if int(s[i]) == 0:
            continue
        for b in B[i]:
            if int(s[b[0]-1]) != b[1]:
                state = 0
    if state == 1:
        print(s)
        for t in s:
            c += int(t)
    if max <= c:
        max = c
print(max)

Submission status: Wrong Answer

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

import sys

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

def bit_count(i):

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

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

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())

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

result = 0
for i in range(1, 2 ** N - 1):
  t = [-1] * N
  for j in range(N):
    t[j] = (i >> j) & 1
  m = False
  for j in range(N):
    if (i >> j) & 1 == 0:
      continue
    for x, y in s[j]:
      if t[x] == -1:
        t[x] = y
      else:
        if t[x] != y:
          m = True
          break
    if m:
      break
  if not m:
    result = max(result, bin(i)[2:].count('1'))
print(result)

Submission status: Wrong Answer

Solution code:
n = int(input())
key = [[0]*n for i in range(n)]
ans = [True]*n
for i in range(n):
    a = int(input())
    k = 0
    for j in range(a):
        p, q = map(int, input().split())
        key[i][p-1] = q+1
        s = key[p-1][i]
        t = q+1
        if s==0:
            continue
        if s==1 and t==1:
            if ans[p-1] == True:
                ans[p-1] = False
            elif k == 1:
                ans[i] = False
            else:
                k = 1
        elif s==1:
            ans[p-1] = False
        else:
            ans[i] = False
print(sum(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
l = list()
for n in range(N):
    a = int(input())
    tmp = list()
    for m in range(a):
        tmp.append([int(x) for x in input().split()])
    l.append(tmp)
honest = [1]*(N+1)
honest[0] = 0
for n in range(N-1):
    for m in l[n]:
        for k in range(n+1,N):
            for s in l[k]:
                if m[0] == s[0]:
                    if m[1] != s[1]:
                        honest[m[0]] = 0
                if m[0] == k+1 and s[0] == n+1:
                    if m[1] == 0 and s[1] == 0:
                        if honest[s[0]] == 1:
                            honest[s[0]] = 0
                            continue
                        if honest[m[0]] == 1:
                            honest[m[0]] = 0
                            continue
print(np.sum(honest))

Submission status: Wrong Answer

Solution code:
import sys
import math
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
data = [[] for i in range(N+1)]

for i in range(N):
  a = I()
  for j in range(a):
    data[i].append(IL())

ans = 0
for i in range(1 << N):
  TF = [-1]*N
  cnt = 0
  for j in range(N):
    if ((i >> j) & 1) == 1: #j人目が正しい
      TF[j] = True
      cnt += 1
    else:
      TF[j] = False
  
  for k in range(N):
    f = TF[k]
    for x,y in data[k]:
      if TF[x-1] == y ^ f ^ 1:
        continue
      else:
        break
    else:
      continue
    break
  else:
    ans = max(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
k = []
s = ["Uso"]*(N)
for i in range(N):
    A = int(input())
    for j in range(A):
        x,y = map(int,input().split())
        k.append([i+1,x,y])
for i in range(len(k)-1):
  for j in range(N+1):
    if k[i][1] == j:
      if k[i][2] == 1:
        if s[j-1] == "Honto":
          s[j-1] = "Uso"
        else:
          s[j-1] = "Honto"
if s.count("Honto") == len(s):
  print(0)
elif s.count("Uso") == len(s):
  print(1)
else:
  print(s.count("Honto"))

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[]
for i in range(n):
  x=[]
  a=int(input())
  x=[list(map(int,input().split())) for j in range(a)]
  l.append(x)

b=[]
for k in range(2**n):
  b.append(format(k,'0'+str(n)+'b'))
ans=[0]
for i in range(2**n):
  ct1=0
  ct2=0
  for j in range(n):
    if b[i][j]=='1':
      ct1+=1
    ct=0
    for k in range(len(l[j])):
      if b[i][j]=='1':
        if int(b[i][l[j][k][0]-1])!=l[j][k][1]:
          ct+=1
      elif b[i][j]=='0':
        if int(b[i][l[j][k][0]-1])==l[j][k][1]:
          ct+=1
    if ct==0:
      ct2+=1
  if ct2==n:
    ans.append(ct1)
print(max(ans))

Submission status: Wrong Answer

Solution code:

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


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


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


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


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


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


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


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


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


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


# show_flg = False
show_flg = True


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

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

    flag = True
    for i in range(1, len(p)):
        if len(p[i]) == 1 and p[i][0] == 0:
            flag = flag and True
        else:
            flag = flag and False

    if flag:
        print(1)
        return

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict 

n=int(input())
yes=defaultdict(list)
no=defaultdict(list)
for i in range(1,n+1):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        if y==0:
            no[i].append(x)
        else:
            yes[i].append(x)

maxi=0 
tot=(1<<n)
def ok(curr):
    for a  in range(1,n+1):
        if a in curr:
            for z in range(n+1):
                if z in curr:
                    #honest 
                    if z in no[a] or a in no[z]:
                        return 0 
                else: 
                    if z in yes[a] or a in yes[z]:
                        return 0 
    return 1 
#print(no)

for i in range(tot):
    curr=[]
    for j in range(n):
        if i&(1<<j):
            curr.append(j)
    curr=[i+1 for i in curr]
    if ok(curr):
       # print(curr)
        maxi=max(maxi,len(curr))
print(maxi)

Submission status: Wrong Answer

Solution code:
n = int(input())
mat = [[-1]*n for i in range(n)]
count = 0
for i in range(n):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        mat[i][x-1] = y
for i in range(n):
    for j in range(n):
        if mat[i][j] == mat[j][i] == 1:
            count += 2
        elif mat[i][j] == mat[j][i] == 0:
            count += 1
print(count//2)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import product

n = int(stdin.readline().rstrip())
ma = 0
#1が正直者0が嘘つきとする
lin = [0,1]
lin = list(product(lin, repeat=n))
a = []
li = []
ma = 0
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)]
    li.append(lis)
for i in lin:
    frag = 0
    genzai = list(i)
    for j in range(len(genzai)):
        if genzai[j] == 1:
            for k in range(a[j]):
                if li[j][k][1] == 0 and genzai[li[j][k][0]-1] == 1:
                    frag = 1
                elif li[j][k][1] == 1 and genzai[li[j][k][0]-1] == 0:
                    frag = 1
        else:
            for k in range(a[j]):
                if li[j][k][1] == 1 and genzai[li[j][k][0]-1] == 1:
                    frag = 1
                elif li[j][k][1] == 0 and genzai[li[j][k][0]-1] == 0:
                    frag = 1
    if frag == 0:
        ma = max(ma,sum(genzai))
print(ma)

Submission status: Wrong Answer

Solution code:
n = int(input())
xy = [[] for _ in range(n)]
for i in range(n):
  a = int(input())
  for j in range(a):
    x, y = map(int, input().split())
    x -= 1
    xy[i] += [[x, y]]
result = 0
for i in range(2**n):
  dic = {i:-1 for i in range(n)}
  flag = True 
  ans = 0
  for j in range(n):
    if (i>>j)&1:
      if dic[j] != -1 and dic[j] != 1:
        flag = False
        break
      dic[j] = 1
      for x, y in xy[j]:
        if dic[x] == -1:
          dic[x] = y 
        elif dic[x] != -1 and dic[x] != y:
          flag = False
          break
      ans += 1
    else:
      for x, y in xy[j]:
        if dic[x] == -1:
          dic[x] = 1-y 
        elif dic[x] != -1 and dic[x] == y:
          flag = False
          break

  if flag:
    result = max(result, ans)

print(result)

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
	for i in range(N):
		flg = True
		for j, val in enumerate(xyS):
			if val[i] == 0:
				flg = False
				break
		if flg == True:
			ans += 1

	#print(xyS)
	print(ans)



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

    for i, a in enumerate(xys):
        #print("---")
        #print(hantei)
        #print(flag)
        #print(a)
        for k, b in enumerate(a):
            #print(b)
            if hantei[b[0]] == 0:
                hantei[b[0]] = b[1]
            else:
                if hantei[b[0]] == b[1]:
                    pass
                else:
                    if hantei[i] == 1:
                        flag = -1
                        #print(i)
                        #print("bad")

    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:

def main():
    n = int(input())
    bs = []
    xyss = []
    ans = 0
    for _ in range(n):
        bs.append(int(input()))
        xys = [[int(i) for i in input().split()] for __ in range(bs[-1])]
        xs = set(x-1 for x, y in xys if y == 1)
        ys = set(x-1 for x, y in xys if y == 0)
        # print(list(xs), list(ys))
        xyss.append((xs, ys))
    
    for i in range(n**2-1):
        #print("=== {0:b} ===".format(i))
        f = True
        for j in range(n):
            if i & (1 << j) > 0:
                xs, ys = xyss[j]
                for x in xs:
                    if (~i) & (1<<x) > 0:
                        f = False
                        # print(x)
                        break
                for y in ys:
                    if i & (1<<y) > 0:
                        f = False
                        # print(y)
                        break
            if not f:
                break
        # print("{0}".format(f))
        if f:
            ans = max(ans, sum(1 for c in "{0:b}".format(i) if c == '1'))
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappush, heappop
from itertools import product
from math import sqrt
from collections import defaultdict
input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))
N = int(input())
D = [[-1]*N for i in range(N)]

for i in range(N):
    a = int(input())
    for _ in range(a):
        x, y = inpl()
        D[i][x-1] = y

ans = 0
for X in product(range(2), repeat=N):
    OK = True
    for i in range(N):
        if i == 0:
            continue
        for j in range(N):
            if D[i][j] == -1:
                continue
            if D[i][j] != X[j]:
                OK = False
                break
    if OK:
        ans = max(ans, sum(X))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
count = 0
for i in range(n):
    a = int(input())
    good_man = True
    for j in range(a):
        xy = list(map(int, input().split()))
        if xy[1] == 0:
            good_man = False
    if good_man:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())

one = 0
zero = 0

for i in range(N):
    A = int(input())
    for i in range(A):
        x, y = map(int, input().split())
        if y == 0:
            zero += 1
        elif y == 1:
            one += 1

if one == zero:
    print(0)

elif one < zero:
    print(zero//2)

else:
    print(one)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[]
for _ in range(n):
    a=int(input())
    ll=[]
    for i in range(a):
        x,y=map(int,input().split())
        x-=1
        ll.append((x,y))

    l.append(ll)
ans=0
for i in range(n):
    h={}
    h[i]=1
    ans1=1
    hh={}
    for x,y in l[i]:
        h[x]=y
        if y==1:
            hh[x]=1

    for j in range(n):
        if i==j:
            continue
        f=1
        for x,y in l[j]:
            if x in h and h[x]!=y:
                f=0
        if f:
            ans1+=1
        if j in hh and f==0:
            ans1=0
    ans=max(ans,ans1)

print(ans)