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())
A = []
x = []
y = []
xy = [[] for _ in range(N)]
for i in range(N):
    A1 = int(input())
    A.append(A1)
    for _ in range(A1):
        x, y = map(int, input().split())
        xy[i].append((x-1, y))

c_max = 0
cnt = 0
for i in range(1 << N):
    ok = True
    for j in range(N):
        if (i << j) & 1:
            continue
        for x, y in (xy[j]):
            if (i << x) & 1 != y:
                ok = False
                break
        if not ok:
            break

    if ok:
        cnt = bin(i)[2:].count('1')
        if cnt > c_max:
            c_max = cnt

print(c_max)

Submission status: Wrong Answer

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

c_max = 0
cnt = 0
for i in range(1 << N):
    ok = True
    for j in range(N):
        if (i << j) & 1:
            continue
        for x, y in (xy[j]):
            if (i >> x) & 1 != y:
                ok = False
                break
        if not ok:
            break

    if ok:
        cnt = bin(i)[2:].count('1')
        if cnt > c_max:
            c_max = cnt

print(c_max)

Submission status: Wrong Answer

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

for i in range(N):
    a = int(input())
    A.append(a)
    inter = []
    for x in range(a):
        xy = list(map(int,input().split()))
        inter.append(xy)
    XY.append(inter)
    print(XY)

for i in range(2**N):
    pt = [0]*N
    ck = 1
    for j in range(N):
        if (i>>j)&1:
            pt[N-j-1]=1
    for k in range(N):
        if pt[k] ==1:
            for l in range(A[k]):
                if XY[k][l][1] != pt[XY[k][l][0] -1]: # 正直者と仮定した人の証言に矛盾がないかをチェック。正しいと向けられた人の証言が自分に返ってこないか。
                    ck = 0
    if ck == 1:
        honest_count.append(sum(pt))
print(max(honest_count))

Submission status: Wrong Answer

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

inf=10**7
ans=0
for i in range(2**n):
    kind=0
    for j in range(n):
        if ((i >> j) & 1):
            for k in range(n):
                if arr[j][k]==1:
                    if ((i >> k) & 1)==False:
                        kind=-inf

                if arr[j][k]==0:
                    if ((i >> k) & 1):
                        kind=-inf

        else:
            for k in range(n):
                if arr[j][k]==1:
                    if ((i >> k) & 1):
                        kind=-inf
        
                if arr[j][k]==0:
                    if ((i >> k) & 1)==False:
                        kind=-inf
        
    for j in range(n):
        if ((i >> j) & 1):
            kind+=1

    if kind>ans:
        ans=kind
print(ans)

Submission status: Wrong Answer

Solution code:
N, *data = open(0).read().split('\n')
N = int(N)

XY = []

j = 0
for i in range(N):
    A = int(data[j])
    j += 1
    XY.append([])
    for a in range(A):
        XY[i].append(tuple(map(int, data[j].split())))
        j += 1
        
# True: 矛盾あり、False: 矛盾なし

def is_contradiction(mynum:int, is_honest:str, x:int, y:int):
    if is_honest[mynum]=='1':
        return is_honest[x-1]!=str(y)
    else:
        return is_honest[x-1]==str(y)
      
ans = 0

for i in range(2**N):
    is_honest = format(i, '0%db' %N)
    
    if ans >= is_honest.count('1'):
        continue
    else:
        
#         print(is_honest) # for Debug
        
        contradictions = []
        for n in range(N):    
            for xy in XY[n]:
                contradictions.append(is_contradiction(n, is_honest, *xy))
        
#         print(contradictions)  # for Debug
        
        if True not in contradictions:
            ans = is_honest.count('1')
            
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
xy=[[] for i in range(n)]
ans=0
a=[0]*n
for i in range(n):
  a[i]=int(input())
  for j in range(a[i]):
    x,y=map(int,input().split())
    xy[i].append([x,y])
for i in range(2**n):
  temp=[0]*n
  for j in range(n):
    if ((i >> j) & 1):
      temp[j]=1
  count=True
  for j in range(n):
    for k in range(a[j]):
      if temp[j]==1:
        p=xy[j][k][0]-1
        if temp[p]!=xy[j][k][1]:
          count=False
          break
      else:
        p=xy[j][k][0]-1
        if temp[p]==xy[j][k][1]:
          count=False
          break
  if count==True:
    ans=max(ans,sum(temp))
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
xy=[[] for i in range(n)]
ans=0
a=[0]*n
for i in range(n):
  a[i]=int(input())
  for j in range(a[i]):
    x,y=map(int,input().split())
    xy[i].append([x,y])
for i in range(2**n):
  temp=[0]*n
  for j in range(n):
    if ((i >> j) & 1):
      temp[j]=1
  count=True
  for j in range(n):
    for k in range(a[j]):
      if temp[j]==1:
        p=xy[j][k][0]-1
        if temp[p]!=xy[j][k][1]:
          count=False
      else:
        p=xy[j][k][0]-1
        if temp[p]==xy[j][k][1]:
          count=False     
  if count==True:
    ans=max(ans,sum(temp))
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
xy=[[] for i in range(n)]
ans=0
a=[0]*n
for i in range(n):
  a[i]=int(input())
  for j in range(a[i]):
    x,y=map(int,input().split())
    xy[i].append([x,y])
for i in range(2**n):
  temp=[0]*n
  for j in range(n):
    if ((i >> j) & 1):
      temp[j]=1
  count=True
  for j in range(n):
    for k in range(a[j]):
      if temp[j]==1:
        p=xy[j][k][0]-1
        if temp[p]!=xy[j][k][0]:
          count=False
      else:
        p=xy[j][k][0]-1
        if temp[p]==xy[j][k][0]:
          count=False     
  if count==True:
    ans=max(ans,sum(temp))
print(ans)

Submission status: Wrong Answer

Solution code:
#C
n = int(input())
a = []
testimony = [-1]*n
ans = 0
for i in range(n):
    a.append(int(input()))#証言の個数
    l = []
    for j in range(a[i]):
        l.append(list(map(int, input().split())))
    if l != []:
        testimony[i] = l#iの人のa[i]個の証言のリスト
for i in range(2**n):
    for j in range(n):
        if (i >> j) & 1 and a[n-1-j] != -1:
            for k in range(a[n-1-j]):
                if (i >> (n - testimony[n-1-j][k][0])) != testimony[n-1-j][k][1]:
                    break
            else:
                continue
            break
    else:
        ans = max(ans, str(bin(i)).count('1'))
print(ans)

Submission status: Wrong Answer

Solution code:
#C
n = int(input())
a = []
testimony = []
ans = 0
for i in range(n):
    a.append(int(input()))#証言の個数
    l = []
    for j in range(a[i]):
        l.append(list(map(int, input().split())))
    testimony.append(l)#iの人のa[i]固の証言のリスト
for i in range(2**n):
    for j in range(n):
        if (i >> j) & 1:
            for k in range(a[n-1-j]):
                if (i >> (n - testimony[n-1-j][k][0])) != testimony[n-1-j][k][1]:
                    break
            else:
                continue
            break
    else:
        ans = max(ans, str(bin(i)).count('1'))
print(ans)

Submission status: Wrong Answer

Solution code:
#C
n = int(input())
a = []
testimony = []
ans = 0
for i in range(n):
    a.append(int(input()))#証言の個数
    l = []
    for j in range(a[i]):
        l.append(list(map(int, input().split())))
    testimony.append(l)#iの人のa[i]固の証言のリスト
for i in range(2**n):
    for j in range(n):
        if (i >> j) & 1:
            for k in range(a[n-1-j]):
                if (i >> (n - testimony[n-1-j][k][0])) != testimony[n-1-j][k][0]:
                    break
            else:
                continue
            break
    else:
        ans = max(ans, str(bin(i)).count('1'))
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
n = int(raw_input())

cc = [[set(),set()] for _ in range(n)]
for i in range(n):
	t = int(raw_input())
	for _ in range(t):
		x,y = map(int, raw_input().split(' '))
		x -=1
		cc[i][y].add(x)




def f(mask, cc,n):
	X,Y = set([]), set([])

	for i in range(len(cc)):
		if (mask >> i) & 1:
			X |= cc[i][0]
			Y |= cc[i][1]




	if len(X.intersection(Y)) == 0:
		m1 = sum([1 << y for y in Y])
		m2 = sum([1 << x for x in X])
		if m1 | mask == mask and m1 + m2 <= (1 << n) -1:
			return len(Y)
		else:
			return 0
	else:
		return 0

c = 0
for mask in range(1, 2 ** n + 1):
	c = max(c,f(mask,cc,n))
print c

Submission status: Wrong Answer

Solution code:
import collections
n = int(raw_input())

cc = [[set(),set()] for _ in range(n)]
for i in range(n):
	t = int(raw_input())
	for _ in range(t):
		x,y = map(int, raw_input().split(' '))
		x -=1
		cc[i][y].add(x)




def f(mask, cc,n):
	X,Y = set([]), set([])

	for i in range(len(cc)):
		if (mask >> i) & 1:
			X |= cc[i][0]
			Y |= cc[i][1]




	if len(X.intersection(Y)) == 0:
		m1 = sum([1 << y for y in Y])
		m2 = sum([1 << x for x in X])
		if m1 == mask and m1 + m2 <= (1 << n) -1:
			return len(Y)
		else:
			return 0
	else:
		return 0

c = 0
for mask in range(1, 2 ** n + 1):
	c = max(c,f(mask,cc,n))
print c

Submission status: Wrong Answer

Solution code:
import collections
n = int(raw_input())

cc = [[set(),set()] for _ in range(n)]
for i in range(n):
	t = int(raw_input())
	for _ in range(t):
		x,y = map(int, raw_input().split(' '))
		x -=1
		cc[i][y].add(x)




def f(mask, cc,n):
	X,Y = set([]), set([])

	for i in range(len(cc)):
		if (mask >> i) & 1:
			X |= cc[i][0]
			Y |= cc[i][1]




	if len(X.intersection(Y)) == 0:
		m1 = sum([1 << y for y in Y])
		m2 = sum([1 << x for x in X])
		if m1 == mask and m1 + m2 == (1 << n) -1:
			return len(Y)
		else:
			return 0
	else:
		return 0

c = 0
for mask in range(1, 2 ** n + 1):
	c = max(c,f(mask,cc,n))
print c

Submission status: Wrong Answer

Solution code:
import collections
n = int(raw_input())

cc = [[set(),set()] for _ in range(n)]
for i in range(n):
	t = int(raw_input())
	for _ in range(t):
		x,y = map(int, raw_input().split(' '))
		x -=1
		cc[i][y].add(x)




def f(mask, cc):
	X,Y = set([]), set([])

	for i in range(len(cc)):
		if (mask >> i) & 1:
			X |= cc[i][0]
			Y |= cc[i][1]




	if len(X.intersection(Y)) == 0:
		
		if sum([1 << y for y in Y]) == mask:
			return len(Y)
		else:
			return 0
	else:
		return 0

c = 0
for mask in range(1, 2 ** n + 1):
	c = max(c,f(mask,cc))
print c

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    xy = []
    for _ in range(n):
        ai = int(input())
        xyi = [list(map(int, input().split())) for _ in range(ai)]
        xy.append(xyi)

    ans = 0
    flag = False

    for i in range(1 << n):
        for j in range(n):
            if i & (1 << (j + 1)):
                for x, y in xy[j]:
                    if y == 1:
                        if not i & (1 << x):
                            flag = True
                    if y == 0:
                        if i & (1 << x):
                            flag = True
        if not flag:
            tmp = 0
            for j in range(n):
                if i & (1 << (j + 1)):
                    tmp += 1
            if ans < tmp:
                ans = tmp
        flag = False

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

Solution code:
class Human:
    is_Honest = False
    def __init__(self,A,x,y):
        self.A = A
        self.x = x
        self.y = y

def Hcount(info, piv, count):
    if info[piv].is_Honest:
        for u in range(info[piv].A):
            if count < 0:
                return -1
            x = info[piv].x[u]-1
            y = info[piv].y[u]
            if y == 1:
                if info[x].is_Honest != True:
                    info[x].is_Honest = True
                    count += 1
                    count = Hcount(info, x, count)
            else:
                if info[x].is_Honest:
                    return -1
    return count


N = int(input())
human_info = []
for u in range(N):
    A = int(input())
    p = []
    q = []
    for v in range(A):
        tmp = list(map(int, input().split()))
        p.append(tmp.pop(0))
        q.append(tmp.pop(0))
    human = Human(A,p,q)
    human_info.append(human)

count = 0
for w in range(N):
    buff_info = human_info[:]
    buff_info[w].is_Honest = True
    tmp = Hcount(buff_info, w, 1)
    if count < tmp:
        count = tmp

print(count)

Submission status: Wrong Answer

Solution code:
class Human:
    is_Honest = False
    def __init__(self,A,x,y):
        self.A = A
        self.x = x
        self.y = y

def Hcount(info, piv, count):
    if info[piv].is_Honest:
        for u in range(info[piv].A):
            if count < 0:
                return -1
            x = info[piv].x[u]-1
            y = info[piv].y[u]
            if y == 1:
                if info[x].is_Honest != True:
                    info[x].is_Honest = True
                    count += 1
                    count = Hcount(info, x, count)
            else:
                if info[x].is_Honest:
                    return -1
    return count


N = int(input())
human_info = []
for u in range(N):
    A = int(input())
    p = []
    q = []
    for v in range(A):
        tmp = list(map(int, input().split()))
        p.append(tmp.pop(0))
        q.append(tmp.pop(0))
    human = Human(A,p,q)
    human_info.append(human)

count = 0
for w in range(N):
    buff_info = human_info
    buff_info[w].is_Honest = True
    tmp = Hcount(buff_info, w, 1)
    if count < tmp:
        count = tmp

print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())

xy=[[] for i in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        xx,yy=list(map(int,input().split()))
        xy[i].append([xx-1,yy])

def cntbin(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
            count += int(i)
    return count

ans=[0]
for ii in range(2**n): #1 is honest
    i=str(ii).zfill(n)
    ok=True
    for nin in range(n):
        nin_is=int(i[-nin])
        for x,y in xy[nin]:
            pre=nin_is^y
            x_is=int(i[-x])
            if pre == x_is:
                ok=False
                break
        if not ok:break
    if ok:
        ans.append(n - cntbin(int(i)))
print(max(ans))

Submission status: Wrong Answer

Solution code:
n=int(input())

xy=[[] for i in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        xx,yy=list(map(int,input().split()))
        xy[i].append([xx-1,yy])

def cntbin(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
            count += int(i)
    return count

ans=[0]
for i in range(2**n): # 0 is honest
    ok=True
    for nin in range(n):
        nin_is= (i>>nin) & 1
        for x,y in xy[nin]:
            x_is= nin_is ^ y
            if ((i>>x) & 1)^x_is ==0:
                ok=False
                break
        if not ok:break
    if ok:
        ans.append(n-cntbin(i))

print(max(ans))

Submission status: Wrong Answer

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

ans = 0
maxc = 2**n
cnt = 0
while(cnt < maxc):
    isOK = True
    
    for i in range(n):
        if(1 & cnt>>i):
            #i番目の人の証言が正しいと仮定する
            for x,y in mp[i]:
                if(y == 1):
                    if(1 & cnt>>(x-1)):
                        continue
                else:
                    if(not (0 | cnt>>(x-1))):
                        continue
                
                isOK = False
    
    if isOK:
        num = str(bin(cnt)).count('1')
        
        if ans < num:
            ans = num
    
    cnt += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf


n = iinput()
human = [[-1 for i in range(n)] for i in range(n)]
for i in range(n):
    a = iinput()
    for j in range(a):
        x,y = imap()
        human[i][x-1] = y #証言者がiで、y=1で正直者

anss = []
for i in range(2**n):
    # 正直者・嘘つきものの組み合わせbin
    bin = iarr(n)
    for j in range(n):
        if i>>j&1: bin[j] = 1
    # jが嘘吐きの場合に、human[j][k]に値あれば変更
    for j in range(n):
        for k in range(n):
            if not bin[j]: # jは嘘吐き
                if human[j][k]==-1: continue
                else: human[j][k] += 1; human[j][k] %= 2
    # humanで真偽情報を整理したnewmanを作成、作成時に矛盾あればflag=0
    newman = [-1 for i in range(n)]
    flag = 1
    for j in range(n):
        for k in range(n):
            if human[j][k]==-1: continue
            if newman[k]==-1: newman[k] = human[j][k]; continue
            if newman[k] != human[j][k]: flag = 0; break
    # newman[j]に値あれば、bin[j]の情報と矛盾しないかチェック
    for j in range(n):
        if newman[j]==-1: continue
        if bin[j] != newman[j]: flag = 0; break
    if flag: anss.append(sum(bin))

ans = max(anss) if anss else 0
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

N = int(input())

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

saidai = 0
for i in itertools.product(range(2), repeat=N):
    ans = [-1]*N
    Flag = True
    for j in range(N):
        if ans[j] == i[j] or ans[j] == -1:
            ans[j] = i[j]
        else:                
            Flag = False
            break
            
        for k in A[j]:
            if ans[k[0]] == k[1] or ans[k[0]] == -1:
                ans[k[0]] = k[1]
            else:
                Flag = False
                break
    if Flag == True:
        saidai = max(ans.count(1), saidai)

print(saidai)

Submission status: Wrong Answer

Solution code:
import itertools

N = int(input())

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

saidai = 0
for i in itertools.product(range(2), repeat=N):
    ans = [-1]*N
    Flag = True
    for j in range(N):
        if i[j] == 1:
            if ans[j] == 0:
                Flag = False
                break
            ans[j] = 1

            for k in A[j]:
                if ans[k[0]] == k[1] or ans[k[0]] == -1:
                    ans[k[0]] = k[1]
                else:
                    Flag = False
                    break
    if Flag == True:
        saidai = max(ans.count(1), saidai)

print(saidai)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    XY = [[] for _ in range(N)]
    for n in range(N):
        A = ii()
        xy = [[] for _ in range(A)]
        for a in range(A):
            xy[a] = il()
        XY[n] = xy

    ret = 0
    for b in range(1 << N):
        tf = [0] * N
        for i in range(N):
            if b >> i & 1:
                tf[i] = 1

        flg = True
        for j in range(N):
            for x, y in XY[j]:
                if tf[x - 1] == 0:
                    continue
                if tf[x - 1] != y:
                    flg = False

        if flg:
            ret = max(ret, sum(tf))
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    XY = [[] for _ in range(N)]
    for n in range(N):
        A = ii()
        xy = [[] for _ in range(A)]
        for a in range(A):
            xy[a] = il()
        XY[n] = xy

    ret = 0
    for n in range(1 << N):
        tf = [-1] * N
        for m in range(N):
            if n >> m & 1 or tf[m] == 1:
                xy = XY[m]
                tf[m] = 1
                for x, y in xy:
                    if tf[x-1] == -1:
                        tf[x-1] = y
                    elif tf[x-1] != y:
                        break

        flg = True
        for l in range(N):
            for x, y in XY[l]:
                if tf[x-1] != -1 and tf[x-1] == y or tf[x-1] == -1 or tf[l] == 0 or tf[l] == -1:
                    continue
                else:
                    flg = False
        if flg:
            ret = max(ret, sum([1 for t in tf if t == 1]))

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
"""
メモ用
ビット全探索
不親切な人の証言をすべてひっくり返し、
できたリスト(la)の中で人、親切or不親切がすべて一致する時の人数を求める。
というやり方でやったが、方針が間違っていた。
親切な人の証言がすべて一致するかどうかという方針でやればok。
"""

import copy
N = int(input())
l = [] # 証言リスト
lo = [] # 親切な人の数のリスト
m = [] # 証言の個数リスト
ans = [-1] * 2 ** N # 答え
cnt = 0 #親切な人の数
# ↓入力
for _ in range(N):
  n = []
  a = int(input())
  m.append(a)
  for _ in range(a):
    b = list(map(int, input().split()))
    n.append(b)
  l.append(n)
# ↑入力
for i in range(2 ** N):
  ansa = copy.deepcopy(ans)
  la = copy.deepcopy(l)
  for j in range(N):
    if ((i >> j) & 1):
      cnt += 1 #人jが親切だったときにcnt += 1
    for k in range(m[j]):
      if ((i >> j) & 1): # 人jが親切なら
        pass
      else: # 0と1を入れ替える
        if la[j][k][1] == 0:
          la[j][k][1] = 1
        else:
          la[j][k][1] = 0
# ↓リストlaを結合
  li = []
  for x in range(N):
    for j in range(m[x]):
      li.append(la[x][j])
# ↑リストlaを結合
  for x in range(sum(m)-1):
    for j in range(x+1, sum(m)):
      if li[x][0] == li[j][0]:
        if li[x][1] != li[j][1]:
          ansa[i] = 0 # 一致しなかった場合ゼロを返す
  if ansa == [-1] * 2 ** N: # ゼロを一つも返さなかった場合
    lo.append(cnt) # cntをリストに代入
  cnt = 0
if len(lo) == 0:
  print(0)
else:
  print(max(lo))

Submission status: Wrong Answer

Solution code:
import copy
N = int(input())
l = [] # 証言リスト
lo = [] # 親切な人の数のリスト
m = [] # 証言の個数リスト
ans = [-1] * 2 ** N # 答え
cnt = 0 #親切な人の数
for _ in range(N):
  n = []
  a = int(input())
  m.append(a)
  for _ in range(a):
    b = list(map(int, input().split()))
    n.append(b)
  l.append(n)

for i in range(2 ** N):
  ansa = copy.deepcopy(ans)
  la = copy.deepcopy(l)
  for j in range(N):
    if ((i >> j) & 1):
      cnt += 1
    for k in range(m[j]):
      if ((i >> j) & 1): # 人jが親切なら
        pass
      else:
        if la[j][k][1] == 0:
          la[j][k][1] = 1
        else:
          la[j][k][1] = 0
  li = []
  for x in range(N):
    for j in range(m[x]):
      li.append(la[x][j])
  for x in range(sum(m)-1):
    for j in range(x+1, sum(m)):
      if li[x][0] == li[j][0]:
        if li[x][1] != li[j][1]:
          ansa[i] = 0
  if ansa == [-1] * 2 ** N:
    lo.append(cnt)
  cnt = 0
if len(lo) == 0:
  print(0)
else:
  print(max(lo))

Submission status: Wrong Answer

Solution code:
# 矛盾する場合とは？
# ・正直者として認識していた人に嘘つきと言われる、嘘つきの話は信用できないので情報として信用しなくて良い
# ・A -嘘-> B　A <-嘘- B : どっちかは正直者
# ・A -正-> B　A <-嘘- B : Bは正直者かも
# ・A -正-> B　A <-正- B : A,Bはどっちも正直者かも

# まず、全員正直者だと思っておく。
# 嘘つきだと言われた人を記録して嘘つきとおもう。
# 嘘つきだと思った人に嘘つきと言われても気にしないでおく

n = int(input())
p = [[] for _ in [0] * (n + 1)]
not_p = [[] for _ in [0] * (n + 1)]

for i in range(1, n+1):
    Ai = int(input())
    for _ in range(Ai):
        x, y = map(int, input().split())
        if y == 1:
            p[i] += [x]
        else:
            not_p[i] += [x]
#print(p, not_p)

lier = []
for i in range(1, n + 1):
    for a in not_p[i]:
        lier.append(a)
        try:
            not_p[a].remove(i)
        except ValueError:
            pass

print(n - len(lier))

Submission status: Wrong Answer

Solution code:
N=int(input())

evi=[[] for _ in range(N)]

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

ans=0

for i in range(2**N):
    cnt=0
    f=True
    for j in range(N):
        if (i>>j)&1:
            cnt+=1
            for x,y in evi[j]:
                if not (i>>x)&y:
                    f=False
                    break
        if not f:
            break
    if f:
        ans=max(ans,cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())

evi=[[] for _ in range(N)]

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

ans=0

for i in range(2**N):
    cnt=0
    f=True
    for j in range(N):
        if (i>>j)&1:
            cnt+=1
            for x,y in evi[j]:
                if (i>>x)&1 and y==0:
                    f=False
                    break
                if (i>>x)&0 and y==1:
                    f=False
                    break
        if not f:
            break
        ans=max(ans,cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())

evi=[[] for _ in range(N)]

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

ans=0

for i in range(2**N):
    cnt=0
    f=True
    print(bin(i))
    for j in range(N):
        if (i>>j)&1:
            cnt+=1
            for x,y in evi[j]:
                if (i>>x)&1 and y==0:
                    f=False
                    break
                if (i>>x)&0 and y==1:
                    f=False
                    break
        if not f:
            break
        ans=max(ans,cnt)

print(ans)

Submission status: Wrong Answer

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

ans=0
for i in range(2**n):
  list=[[] for j in range(n)]
  honest=[]
  for k in range(n):
    if (i>>k)&1:
      honest.append(k)
      for x,y in xy[k]:
        x-=1
        list[x].append(y)

#  print(list)
  bit_honest=[]
  for m in range(n):
    if list[m]:
      if 0 not in list[m]:
        bit_honest.append(m)
    else:
      if m in honest:
        bit_honest.append(m)

  if honest==bit_honest:
    ans=max(ans,len(honest))

print(ans)

Submission status: Wrong Answer

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

ans=0
for i in range(2**n):
  list=[[] for j in range(n)]
  honest=[]
  for k in range(n):
    if (i>>k)&1:
      honest.append(k)
      for x,y in xy[k]:
        x-=1
        list[x].append(y)

#  print(list)
  bit_honest=[]
  for m in range(n):
    if 0 not in list[m]:
      bit_honest.append(m)

  if honest==bit_honest:
    ans=max(ans,len(honest))

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

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

    c_max = 0
    for i in range(2 ** n):
        cnt = 0
        for j in range(n):
            if (i >> j) & 1:
                cnt += 1
                for xy in list_[j]:
                    x, y = xy
                    if not ((i >> x) ^ y) & 1:
                        break
                else:
                    continue
                break
        else:
            if cnt > c_max:
                c_max = cnt
            continue

    print(c_max)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

N = int(input())

lst = [[] for _ in range(N)]
for i in range(N):
    A = int(input())
    for _ in range(A):
        tmp = tuple(map(int, input().split()))
        lst[i].append(tmp)

ans = 0
for i in range(2 ** N): #1の時正直者
    tmp = 0
    flag = True
    for j in range(N):
        if (i >> j) & 1:
            tmp += 1
            for x, y in lst[j]:
                if y == 0:
                    if (i >> (x - 1)) == 0:
                        continue
                if y == 1:
                    if (i >> (x - 1)) & 1:
                        continue
                
                flag = False
                break
        if not flag:
            break
    if flag:
        ans = max(ans, tmp)
                    
print (ans)