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())
remark = [0] * N
NGlist = [0] * N
grouplist = [0]*N
ans = 0
for i in range(N):
    remark[i] = [-1] * N
    NGlist[i] = [0] * N
    grouplist[i] = [0] * N


for k in range(N):
    n = int(input())
    for j in range(n):
        x, y = map(int, input().split())
        remark[k][x-1] = y
        if y == 0:
            NGlist[k][x-1] = 1
            NGlist[x - 1][k] = 1
        else:
            grouplist[k][x-1] = 1

for num in range(2 ** N):
    # print("num=")
    # print(num)
    group = []
    for h in range(N):
        if h not in group and num % 2 == 1:
            group.append(h)
            for s in range(N):
                if grouplist[h][s] == 1:
                    group.append(s)
            num //= 2
    len_group = len(group)
    # print(group)
    if ans >= len_group:
        flag = 1
    flag = 0

    for m in range(len_group):
        for n in range(m+1, len_group):
            if NGlist[m][n] == 1:
                flag = 1
                break
        if flag == 1:
            break
    if flag == 0 and ans < len_group:
        ans = len_group

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [0] * N
XY = []

for i in range(N):
    tmp = []
    a = int(input())
    A[i] = a
    for j in range(a):
        tmp.append(list(map(int, input().split())))
    XY.append(tmp)

mat = [[None] * N for _ in range(N)]
for i in range(N):
    for x, y in XY[i]:
        mat[i][x - 1] = y

ans = 0
for i in range(N):
    cnt = 0
    for j in range(N):
        if i == j:
            continue
            
        if mat[j][i] is not None and mat[j][i] == 0:
            cnt += 1
            break
            
        flag = True
        for k in range(N):
            if mat[i][k] is None or mat[j][k] is None:
                continue
                
            flag = flag and mat[i][k] == mat[j][k]    
                
        cnt += int(flag)
        
    ans = max(ans, cnt)
    
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    As = [0 for _ in range(N)]
    for _ in range(N):
        A = int(input())
        for j in range(A):
            x, y = map(int, input().split())
            if y == 1:
                As[x-1] += 1
            else:
                As[x-1] -= 1
    if sum(As) > 0:
        print(sum(As)+1)
    elif sum(As) < 0:
        print((sum(As)+1)*-1)
    else:
        print(sum(As))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())

des = []

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

# print(des)


ans = 0
for i in range(n):
    state = [0 for i in range(n)]
    state[i] = 1
    ald = set()
    ald.add(i)

    to_search = []
    for d in des[i]:
        to_search.append(d)

    flag = True

    # print(to_search)

    while len(to_search) != 0:
        s,tf = to_search[-1]
        to_search = to_search[:-1]

        if tf == 0:
            state[s-1] = -1
            continue

        if s-1 in ald:
            if state[s - 1] != 0 or state[s - 1] != 1:
                flag = False
                break

        state[s-1] = 1

        for sen in des[s-1]:
            if sen[1] == 1:
                if state[sen[0]-1] == 0:
                    state[sen[0]-1] = 1
                else:
                    state[sen[0] - 1] = -1
                    flag = False
            else:
                if state[sen[0] - 1] == 0:
                    state[sen[0] - 1] = -1
                else:
                    state[sen[0] - 1] = -1
                    flag = False


            to_search.append(sen)

        ald.add(s-1)
    #
    # print(ald)
    # print(flag)
    # print(state)


    if flag:
        tep = len(ald)
        for s in state:
            if s == 0:
                tep += 1
        if ans < tep:
            ans = tep

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
A = []
for i in range(N):
	tmp = []
	n = INT()
	shougen = []
	for j in range(n):
		shougen = MAP()
		tmp.append(shougen)
	A.append(tmp)

cand = []
for i in range(2**N):
	shojiki = [0]*N
	for j in range(N):
		if (i>>j & 1):
			shojiki[N-j-1]=1
	cand.append(shojiki)
# print(cand)

ans = []
for c in cand:
	list = [-1]*(N+1)
	success = True
	ones = [a for idx,a in enumerate(A) if c[idx]==1]
	zeros = [a for idx,a in enumerate(A) if c[idx]==0]
	for idx,a in enumerate(zeros):
		for aa in a:
			list[aa[0]] = 0 if aa[1] == 1 else 1
	for idx,a in enumerate(ones):
		# idxの人が正直者であると仮定
		if c[idx] == 1:
			for aa in a:
				if list[aa[0]] == -1:
					list[aa[0]] = aa[1]
				else:
					if list[aa[0]]!=aa[1]:
						success=False
	for k in range(len(c)):
		if c[k]==1 and list[k+1]==0:
			success = False
		if c[k]==0 and list[k+1]==1:
			success = False
	if success:
		#print(c, list)
		ans.append(sum(c))
	
#print(ans)
if ans:
	print(max(ans))
else:
	print(0)

Submission status: Wrong Answer

Solution code:
import itertools

def change(people, L):
	ans = L.copy()
	for j in people:
		for i in range(len(L)):
			ans[i][j] = not ans[i][j]
	return ans

def check(A):
	flag = False
	for i in range(len(A)):
		value_i = None
		for j in range(len(A[0])):
			if A[i][j] is not None:
				if value_i is None:
					value_i = A[i][j]
				elif value_i != A[i][j]:
					return False
		if value_i is not None:
			flag = flag or value_i
	if not flag:
		return False
	else:
		return True


if __name__ == "__main__":
	N = int(input())
	L = [[None for _ in range(N)] for _ in range(N)]
	for i in range(N):
		A = int(input())
		for _ in range(A):
			x, y = map(int, input().split())
			if y == 1:
				L[x - 1][i] = True
			else:
				L[x - 1][i] = False
	# for item in L:
	# 	print(item)
	# print(check(change([2], L)))

	seq = [i for i in range(N)]
	if check(L):
		print(N)
	else:
		flag = False
		for i in range(1, N + 1):
			comb = list(itertools.combinations(seq, i))
			for person in comb:
				if check(change(person, L)):
					print(N - i)
					# print(person)
					flag = True
					break
		if not flag:
			print(0)

Submission status: Wrong Answer

Solution code:
N = int(input())
AT = [0 for _ in range(N)]
AF = [0 for _ in range(N)]

for i in range(N):
    A = int(input())
    for _ in range(A):    
        x, y = map(int, input().split())
        if y == 0:
            AF[x-1] = True
            AF[i] = True
        else:
            AT[x-1] = True
            AT[i] = True

ans = 0
if (1 not in AT) and (0 not in AF):
    if N == 2:
        print(1)
    else:
        print(0)
elif (0 not in AT) and (0 not in AF):
    print(0)

else:
    for i in range(N):
        if AT[i] != AF[i]:
            ans += 1
    print(max(ans, N-ans))

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[j] = [x, y]
        #temp.append({x: y})
        temp[x] = y
    xy.append(temp)

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

    if isHonest:
        cnt += 1
        for (key, value) in infoMap.items():
            if hList[key] is None:
                hList[key] = value
            elif hList[key] != value:
                return 0
    else:
        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
print(max(solve(0, True, hList1, 0), solve(0, False, hList2, 0)))

Submission status: Wrong Answer

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

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

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

	p = list(dic.values())
	#print(p)
	p = p.count(0)
	if p == 0:
		if n % 2 == 0:
			print(n//2)
		else:
			print(0)
	else:
		print(n - p)


if __name__=='__main__':
	main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
C = []
for _ in range(N):
    a = int(input())
    comment = [[int(_) for _ in input().split()] for i in range(a)]
    C.append(comment)


def bit_tbl2(length):
    _format = "{:0" + str(length) + "b}"
    for i in range(int('1' * length, 2) + 1):
        yield _format.format(i)


ans = 0
for b in bit_tbl2(N):
    # print(b)
    syo = [-1] * (N + 1)
    flg = False
    for i in range(N):
        if b[i] != '1': continue
        syo[i + 1] = 1

        for x, y in C[i]:
            if syo[x] != -1 and y != syo[x]:
                flg = True
                break
            syo[x] = y
            if y == 1 and b[x - 1] != '1':
                flg = True
                break

        if flg: break

    if not flg:

        v = 0
        for x in syo:
            if x == 1: v += 1
        # print(v)

        ans = max(ans, v)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list()
x = list()
y = list()

for i in range(N):
    A_tmp = int(input())
    A.append(A_tmp)
    x_tmp = list()
    y_tmp = list()
    for i in range(A_tmp):
        tmp = [int(i) for i in input().split()]
        x_tmp.append(tmp[0])
        y_tmp.append(tmp[1])
    x.append(x_tmp)
    y.append(y_tmp)

def DFS(acc_list, depth):
    if depth < N:
        acc_list[depth] = 0
        result1 = DFS(acc_list, depth+1)
        acc_list[depth] = 1
        result2 = DFS(acc_list, depth+1)
        return max(result1, result2)

    acc_dict = dict()
    for i in range(N):
        acc_dict[i] = 1

    for i in range(N):
        if acc_list[i] == 1:
            for j in range(A[i]):
                acc_dict[x[i][j]-1] *= y[i][j]

    flag = 1
    for i in range(N):
        if acc_dict[i] == acc_list[i]:
            pass
        else:
            flag = 0

    if flag == 1:
        return sum(acc_list)
    else:
        return 0

acc_list = [0]*N

result = DFS(acc_list, 0)
print(result)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy
from pprint import pprint

# If you use recursive call, uncomment this code
#sys.setrecursionlimit(10**6)

def main():
    N = int(input())
    aa = []
    for _ in range(N):
        aaa = []
        na = int(input())
        for _ in range(na):
            x,y = map(int,input().split())
            aaa.append((x-1,y==1))
        aa.append(aaa)
    #pprint(aa)

    # check
    ans = 0
    for i in range(N):
        result = [None]*N
        queue = list(range(N))
        queue.remove(i)  
        result[i] = True
        for x,y in aa[i]:
            result[x] = y
        #print(result)
        canceled = False
        while len(queue) != 0:
            target = queue.pop()
            skipped = False
            #print(target)
            for x,y in aa[target]:
                if result[target] is None:
                    skipped = True
                    break
                if not result[target]:
                    y = not y
                if result[x] != y:
                    canceled = True
                    break
                result[x] = y
            if skipped:
                continue
            if canceled:
                break
        if canceled:
            continue
        ans = max(ans, result.count(True))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import defaultdict
import itertools

d = defaultdict(list)
N = int(stdin.readline().rstrip())
p = [[0,1] for i in range(N)]

for i in range(N):
    A = int(stdin.readline().rstrip())
    for j in range(A):
        x,y = [int(x) for x in stdin.readline().rstrip().split()]
        d[i].append((x,y))

ans = 0
cnt = 0

for ind,i in enumerate(itertools.product(*p)):
    flag = True
    for m in range(N):
        for j,k in d[m]:
            if i[m] == 1:
                if i[j-1] == k:
                    cnt += 1
                else:
                    flag = False
    if flag:
        ans = max(ans,cnt)
    cnt = 0
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
l = [[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())
    l[i][x-1] = y
ans = 0
for i in range(N-1):
  cnt = 1
  for j in range(i+1,N):
    if len(l)==2 and l[i]!=l[j]:
      print(1)
      exit()
    if l[i] == l[j]:
      cnt += 1
  ans = max(ans, cnt)
if ans == 1:
  print(0)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    ls = [[] for _ in range(n)]
    ls_a = []
    for i in range(n):
        a = int(input())
        ls_a.append(a)
        for _ in range(a):
            x,y = map(int,input().split())
            ls[i].append([x,y])
    ans = -1
    for i in range(2**n):
        can = [0 for _ in range(n)]
        for j in range(n):
            if (i >> j)&1:
                can[j] = 1
                
        flg = True
        for j in range(n):
            for k in range(ls_a[j]):
                now = ls[j][k]
                if can[j]==1:
                    if can[now[0]-1]==now[1]:
                        pass
                    else:
                        flg = False
                else:
                    if can[now[0]-1]==now[1]:
                        flg = False
                    else:
                        pass

        if flg==True:
            ans = max(ans,sum(can))
        else:
            pass

    if ans!= -1:
        print(ans)
    else:
        print(0)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

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

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

    mujun = False
    # honest = 0
    for k, v in D.items():
        if len(v) > 1:
            mujun = True
        # honest += 1

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

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[0] = 1
    xys = xys[1:] + [xys[0]]
    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 = [0]*n
for i in range(n):
  a = int(input())
  A[i] = [ tuple(map(int, input().split())) for _ in range(a) ]
ans = 0
for i in range(2**n):
  P = [2]*n
  f = False
  for j in range(n):
    if i >> j & 1:
      P[j] = 1
      for x, y in A[j]:
        if P[x-1] != 2 and P[x-1] ^ y:
          f = True
          break
        P[x-1] = y
  if f:
    continue
  c = bin(i).count("1")
  if P.count(1) == c:
    ans = max(ans, c)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n = onem()


on = []

Ma = 0

for i in range(n):
    kkk = []
    p = onem()
    for j in range(p):
        kkk.append(l())
    on.append(kkk)

for i in range(2**n-1):
    ppp = '{:015b}'.format(i)
    ppp = list(ppp[15-n:])
    ppp.reverse()
    su = 0
    for r in range(n):
        if ppp[r] == "1":
            su += 1
    f = False
    for j in range(n):
        if ppp[j] == "1":
            for k in range(len(on[j])):
                a,b = on[j][k]
                a -= 1
                if b ^ int(ppp[a]):
                    f = True
                    break
    if not f:
        Ma = max(Ma,su)
print(Ma)

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 j in range(len(k)):
        s[j] = int(k[j])
    c = 0
    state = 1
    for l in range(N):
        if int(s[l]) == 0:
            continue
        for b in B[l]:
            if int(s[b[0]-1]) != b[1]:
                state = 0
    if state == 1:
        for t in s:
            c += t
    if max <= c:
        max = c
print(max)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = []
a = []
for i in range(n):
    aa = int(input())
    a.append(aa)
    c = []
    for j in range(aa):
        xy = list(map(int,input().split()))
        c.append(xy)
    s.append(c)
#print(s[0])
sy = []
ans = 0

def syojiki(sy,count):
    if count == n:
   #     print(sy)
        check = [[] for i in range(n)]
        for i in range(n):
            if sy[i] == 1:
                check[i].append(1)
                for j in range(a[i]):
                    if s[i][j][1] not in check[s[i][j][0]-1]:
                        check[s[i][j][0]-1].append(s[i][j][1])
  #      print(check)
        check2 = 0
        for i in range(n):
            if len(check[i]) <= 1:
                check2 += 1
   #     print(check2)
        if check2 == n:
            global ans
            ans = max(ans,check.count([1]))
  #      print(ans)
    else:
        syojiki(sy+[0],count+1)
        syojiki(sy+[1],count+1)

syojiki(sy,0)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [0] * N
XY = []

for i in range(N):
    tmp = []
    a = int(input())
    A[i] = a
    for j in range(a):
        tmp.append(list(map(int, input().split())))
    XY.append(tmp)

mat = [[None] * N for _ in range(N)]
for i in range(N):
    for x, y in XY[i]:
        mat[i][x - 1] = y

ans = 0
for i in range(N):
    cnt = 0
    for j in range(N):
        if i == j:
            continue
            
        flag = True
        for k in range(N):
            if mat[i][k] is None or mat[j][k] is None:
                continue
                
            flag = flag and mat[i][k] == mat[j][k]    
                
        cnt += int(flag)
        
    ans = max(ans, cnt)
    
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
AT = [0 for _ in range(N)]
AF = [0 for _ in range(N)]

for i in range(N):
    A = int(input())
    for _ in range(A):    
        x, y = map(int, input().split())
        if y == 0:
            AF[x-1] = True
            AF[i] = True
        else:
            AT[x-1] = True
            AT[i] = True

ans = 0
if (1 not in AT) and (0 not in AF):
    if N == 2:
        print(1)
    else:
        print(0)
else:
    for i in range(N):
        if AT[i] != AF[i]:
            ans += 1
    print(ans)

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list()
x = list()
y = list()

for i in range(N):
    A_tmp = int(input())
    A.append(A_tmp)
    x_tmp = list()
    y_tmp = list()
    for i in range(A_tmp):
        tmp = [int(i) for i in input().split()]
        x_tmp.append(tmp[0])
        y_tmp.append(tmp[1])
    x.append(x_tmp)
    y.append(y_tmp)

def DFS(acc_list, depth):
    if depth < N:
        acc_list[depth] = 0
        result1 = DFS(acc_list, depth+1)
        acc_list[depth] = 1
        result2 = DFS(acc_list, depth+1)
        return max(result1, result2)

    acc_dict = dict()
    for i in range(N):
        acc_dict[i+1] = 1

    for i in range(N):
        if acc_list[i] == 1:
            for j in range(A[i]):
                acc_dict[x[i][j]] *= y[i][j]

    flag = 1
    for i in range(N):
        if acc_dict[i+1] == acc_list[i]:
            pass
        else:
            flag = 0

    if flag == 1:
        return sum(acc_list)
    else:
        return 0

acc_list = [0]*N

result = DFS(acc_list, 0)
print(result)

Submission status: Wrong Answer

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

#print(Mat)
count = 0
for i in range(0,N):
    for j in range(0,N):
        if i != j and Mat[i][j] == Mat[j][i]:
            count = count +1

ans = count/2
print(int(ans))

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
      if flag:
        ans += 1
    else:
      if dic[j] != -1 and dic[j] == 1:
        flag = False
        break
      dic[j] = 0
      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:
N = int(input())
A = []
XY = []
for i in range(N):
    a = int(input())
    A.append(a)
    XY.append([list(map(int, input().split())) for _ in range(a)])


ans = 0
# print(singi)
for i in range(2 ** N):
    singi = [-1] * (N + 1)
    bin_ = bin(i)[2:].zfill(N)
    flag = True
    for j in range(1, N + 1):
        sin = bin_[j-1]
        person = j
        num = A[j-1]
        questions = XY[j - 1]
        singi[j] = int(sin)
        w = 0

        if sin == 0:
            continue
        else:
            w = 1

        for k in range(num):
            hito, honto = questions[k]
            # print(singi)
            # print('a', hito, honto)
            if singi[hito] == -1:
                singi[hito] = int(honto)
            else:
                if singi[hito] == honto:
                    continue
                else:
                    flag = False
    if flag is True:
        ans = max(ans, singi.count(1))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
info = [0]
for _ in range(N):
    A = int(input())
    tmp = []
    for i in range(A):
        x, y = map(int, input().split())
        tmp.append((x, y))
    info.append(tmp)

ans = 0
for i in range(2**N):
    i_bin = list(map(int, bin(i)[2:].zfill(N)))
    ok = 1
    for j in range(1, N+1):
        for x, y in info[j]:
            if i_bin[j-1] == 1:
                if i_bin[x-1] != y:
                    ok = 0
            else:
                if i_bin[x-1] == y:
                    ok = 0
    if ok:
        ans = max(ans, sum(i_bin))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

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

def main():
    def dfs(u):
        if g[u]==-1:g[u]=1
        for v,y in to[u]:
            if g[v]!=-1:
                if (g[u]==g[v] and y==0) or (g[u]!=g[v] and y==1):
                    print(0)
                    exit()
            else:
                if y:g[v]=g[u]
                else:g[v]=3-g[u]
                dfs(v)

    to=defaultdict(list)
    n=int(input())
    g=[-1]*n
    for i in range(n):
        a=int(input())
        for _ in range(a):
            x,y=MI()
            x-=1
            to[i].append([x,y])
            to[x].append([i, y])
    for u in range(n):
        if len(to[u])==0:continue
        dfs(u)
    c1=g.count(1)
    c2=g.count(2)
    print(n-min(c1,c2))
main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
import functools
import itertools
import math
INF = float('inf')
MOD = 10**9+7

N = int(input())
As = [None] * N
ts = [[] for i in range(N)]
for i in range(N):
    As[i] = int(input())
    for j in range(As[i]):
        x, y = map(int, input().split())
        ts[i].append((x-1, y))
ans = 0
for ps in itertools.product([0, 1], repeat = N):
    qs = [None] * N
    flg = 1
    for i in range(N):
        if qs[i] != None and qs[i] != ps[i]:
            flg = 0
            break
        if ps[i]:
            for j in range(As[i]):
                x, y = ts[i][j]
                if qs[x] == None:
                    qs[x] = y
                elif qs[x] != y:
                    flg = 0
                    break
        if flg == 0:
            break
    if flg:
        ans = max(ans, sum(ps))
print(ans)

Submission status: Wrong Answer

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

def search(l):
  global seigo
  for x,y in l:
    if y==1:
      seigo[x-1]=1
    else:
      seigo[x-1]=0
def chk(l,seigo):
  for x,y in l:
    if seigo[x-1] != y:
      return True
  return False

ans=0
for i in range(N):
  flg=True
  seigo=[100]*N
  _ans=0
  seigo[i]=1
  search(syougen[i])
  for j in range(N):
    if i==j:
      continue
    if seigo[j]==1:
      if chk(syougen[j],seigo):
        flg=False
        break
    if seigo[j]==100:
      continue
  if flg:
    _ans=sum(seigo)%100
    if ans<_ans:
      ans=_ans
print(ans)