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

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

Group_1 = 'Group_1'
Group_2 = 'Group_2'
Group_none = 'None'

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

has_no_honest = False


for i in range(N):
    for A_list_i in range(A_list[i]):

        # 指名された人のGroup
        Group_mentioned = Group[x_list[i][A_list_i]-1]

        # 人iのA個目の証言が、誰かが正直者であるという内容のとき
        if y_list[i][A_list_i] == 1:
            
            # 人iのGroupと指名された人のGroupがまだ未分類のとき
            # 両方ともGroup1に振り分ける
            if Group[i] == Group_none and Group_mentioned == Group_none:
                Group[i] = Group_1
                Group[x_list[i][A_list_i]-1] = Group_1
            
            # 人iのGroupもしくは指名された人のGroupのどちらか一方は未分類かつ
            # もう片方は分類済みのとき
            # 未分類の方を分類済みのGroupと同じにする
            elif Group[i] != Group_mentioned and Group[i] == Group_none:
                Group[i] = Group_mentioned
            elif Group[i] != Group_mentioned and Group_mentioned == Group_none:
                Group[x_list[i][A_list_i]-1] = Group[i]

            # 人iのGroupと指名された人のGroupが違う、かつ
            # 人iと指名された人がともに分類済みであるとき
            # 矛盾するので、正直者は存在しない
            elif Group[i] != Group_mentioned and Group[i] != Group_none and Group_mentioned != Group_none:
                has_no_honest = True
                break
        
        # 人iのA個目の証言が、誰かが嘘つきであるという内容のとき
        if y_list[i][A_list_i] == 0:

            # 人iのGroupと指名された人のGroupがまだ未分類のとき
            # 人iはGroup1、指名された人はGroup2に分類する
            if Group[i] == Group_none and Group_mentioned == Group_none:
                Group[i] = Group_1
                Group[x_list[i][A_list_i]-1] = Group_2

            # 人iのGroupもしくは指名された人のGroupのどちらか一方は未分類かつ
            # もう片方は分類済みのとき
            # 未分類の方を分類済みのGroupと違うGroupにする
            elif Group[i] != Group_mentioned and Group[i] == Group_none:
                if Group_mentioned == Group_1:
                    Group[i] = Group_2
                else:
                    Group[i] = Group_1
            elif Group[i] != Group_mentioned and Group_mentioned == Group_none:
                if Group[i] == Group_1:
                    Group[x_list[i][A_list_i]-1] = Group_2
                else:
                    Group[x_list[i][A_list_i]-1] = Group_1

            # 人iのGroupと指名された人のGroupが同じ、かつ
            # 人iと指名された人がともに分類済みであるとき
            # 矛盾するので、正直者は存在しない
            elif Group[i] == Group_mentioned and Group[i] != Group_none and Group_mentioned != Group_none:
                has_no_honest = True
                break
    else:
        continue
    break


if has_no_honest:
    print(0)
else:
    print(max(Group.count(Group_1), Group.count(Group_2)))

Submission status: Wrong Answer

Solution code:
n=int(input())
X=[]
Y=[]
#A=[]
#for i in range(n):
A=int(input())
x=[]
y=[]
  #for j in range(A[i]):
    #x,y=[int(s) for s in input().split()]
  #X.append(x)
  #Y.append(y)
  
c=0
#for i in range(n):
 # l=[1]*n
  #for j in range(i, n-i):
   # if l[j]==0:continue
    #for k in range(A[j]):
   # 　　l[X[j][k]] *= Y[j][k]
#if c<l.count(1):
 # c=l.count(1) 
  
        
  
print(c)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for i in range(N):
        a = int(input())
        for j in range(a):
            x, y = (int(i) for i in input().split())
            G[i].append((x-1, y))
            # 人iは人xのことをyと言っている
    ans = 0
    for bit in range(1 << N):
        cur = 0
        good = True  # 矛盾がない
        for i in range(N):
            if bit & (1 << i):
                # 人iは正直者
                # 人iが言う人xの真偽に矛盾があればgood = False
                # 正直者iが嘘をついたらFalse
                cur += 1
                for j, y in G[i]:
                    if (bit & (1 << j)) and y == 0:
                        good = False
                        break
                    elif not(bit & (1 << j)) and y == 1:
                        good = False
                        break
            else:
                # 人iはうそつき
                # 人iが言う人xの真偽に矛盾がなければgood = False
                # うそつきiが正直になったらFalse
                for j, y in G[i]:
                    if (bit & (1 << j)) and y == 1:
                        good = False
                        break
                    elif not(bit & (1 << j)) and y == 0:
                        good = False
                        break
        # print(bit, ":", good)
        if good:
            ans = max(ans, cur)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from __future__ import print_function
# import numpy as np
# import numpypy as np
import sys
input = sys.stdin.readline

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

import math
import string
import fractions
from fractions import Fraction
from fractions import gcd

def lcm(n,m):
    return int(n*m/gcd(n,m))

import re
import array
import copy
import functools
import operator

import collections
import itertools
import bisect
import heapq


from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace

from queue import PriorityQueue as pq

def reduce(p, q):
    common = fractions.gcd(p, q)
    return (p//common , q//common )
# from itertools import accumulate
# from collections import deque

from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

import random

def check(index_person, x_true_or_false, bin_str):
    return (bin_str[index_person] == x_true_or_false)


def main():
    n = int(input().strip())
    ll_xy = [[] for _ in range(n)]
    for i in range(n):
        a = int(input().strip())
        for j in range(a):
            l = list(map(int, input().strip().split()))
            l[0]-=1
            ll_xy[i].append(l)
    eprint("ll_xy ",end=": ")
    eprint(ll_xy)

    cnt=0
    ans=0
    for i in range(2 ** n):     # 場合ループ
        eprint("i ",end=": ")
        eprint(i,end=" and ")

        bin_str = format(i,'b').zfill(n)
        eprint("bin_str ",end=": ")
        eprint(bin_str)
        failure_flag=0
        for j in range(n):      # 人ループ
            if bin_str[j]=="1":   # その人を「真実の人」だと仮定している場合
                a=len(ll_xy[j])
                for k in range(a):  # 証言ループ
                    #eprint("証言ループ")
                    p=int(bin_str[ll_xy[j][k][0]])
                    if ll_xy[j][k][1] == 0:
                        if check(p,"0",bin_str):
                            pass
                        else:
                            failure_flag=1

                    elif ll_xy[j][k][1] == 1:
                        if check(p,"1",bin_str):
                            pass
                        else:
                            failure_flag=1
                    else:
                        try:
                            raise ValueError("error!")
                        except ValueError as e:
                            eprint("e")
        if failure_flag==0:
            cnt+=1
            ans_temp=0
            for x in bin_str:
                if x=="1":
                    ans_temp+=1
            ans=max(ans_temp,ans)
            # #eprint("success!")
    #eprint("cnt ",end=": ")
    #eprint(cnt)
    print(ans)
    return
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
X=[]
Y=[]
#A=[]
#for i in range(n):
  #A=int(input())
  #x=[]
  #y=[]
  #for j in range(A[i]):
    #x,y=[int(s) for s in input().split()]
  #X.append(x)
  #Y.append(y)
  
c=0
#for i in range(n):
 # l=[1]*n
  #for j in range(i, n-i):
   # if l[j]==0:continue
    #for k in range(A[j]):
   # 　　l[X[j][k]] *= Y[j][k]
#if c<l.count(1):
 # c=l.count(1) 
  
        
  
print(c)

Submission status: Wrong Answer

Solution code:
n=int(input())
X=[]
Y=[]
A=[]
#for i in range(n):
  #A=int(input())
  #x=[]
  #y=[]
  #for j in range(A[i]):
    #x,y=[int(s) for s in input().split()]
  #X.append(x)
  #Y.append(y)
  
c=0
#for i in range(n):
 # l=[1]*n
  #for j in range(i, n-i):
   # if l[j]==0:continue
    #for k in range(A[j]):
   # 　　l[X[j][k]] *= Y[j][k]
#if c<l.count(1):
 # c=l.count(1) 
  
        
  
print(c)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for i in range(N):
        a = int(input())
        for j in range(a):
            x, y = (int(i) for i in input().split())
            G[i].append((x-1, y))
            # 人iは人xのことをyと言っている
    ans = 0
    for bit in range(1 << N):
        cur = 0
        good = True  # 矛盾がない
        for i in range(N):
            if bit & (1 << i):
                # 人iは正直者
                cur += 1
                for j, y in G[i]:
                    if (bit & (1 << j)) and y == 1:
                        continue
                    elif not(bit & (1 << j)) and y == 0:
                        continue
                    elif (bit & (1 << j)) and y == 0:
                        good = False
                    elif not(bit & (1 << j)) and y == 1:
                        good = False
            else:
                # 人iはうそつき
                for j, y in G[i]:
                    if (bit & (1 << j)) and y == 0:
                        continue
                    elif not(bit & (1 << j)) and y == 1:
                        continue
                    elif (bit & (1 << j)) and y == 1:
                        good = False
                    elif not(bit & (1 << j)) and y == 0:
                        good = False
        # print(bit, ":", good)
        if good:
            ans = max(ans, cur)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
#X=[]
#Y=[]
#A=[]
#for i in range(n):
  #A=int(input())
  #x=[]
  #y=[]
  #for j in range(A[i]):
    #x,y=[int(s) for s in input().split()]
  #X.append(x)
  #Y.append(y)
  
c=0
#for i in range(n):
 # l=[1]*n
  #for j in range(i, n-i):
   # if l[j]==0:continue
    #for k in range(A[j]):
   # 　　l[X[j][k]] *= Y[j][k]
#if c<l.count(1):
 # c=l.count(1) 
  
        
  
print(c)

Submission status: Wrong Answer

Solution code:
#n=int(input())
#X=[]
#Y=[]
#A=[]
#for i in range(n):
  #A=int(input())
  #x=[]
  #y=[]
  #for j in range(A[i]):
    #x,y=[int(s) for s in input().split()]
  #X.append(x)
  #Y.append(y)
  
c=0
#for i in range(n):
 # l=[1]*n
  #for j in range(i, n-i):
   # if l[j]==0:continue
    #for k in range(A[j]):
   # 　　l[X[j][k]] *= Y[j][k]
#if c<l.count(1):
 # c=l.count(1) 
  
        
  
print(c)

Submission status: Wrong Answer

Solution code:
def inTable(i,cs,table,kind):
	#print(i,ps,table,kind)
	
	if table[i] == None:
		table[i] = kind
	elif table[i] != kind:
		#print("自身の位置の矛盾")
		return 0
	
	for c in ps[i]:
		pn = c[0]
		tf = not (kind ^ c[1])
		if table[pn] == None:
			table[pn] = tf
		elif table[pn] != tf:
			#print("矛盾")
			return 0
		else:
			pass
			
	return dfs(i+1,ps,table[:])

def dfs(i,ps,table):
	if len(ps) <= i:
		#print("無矛盾",table)
		return table.count(True)
		
	table1 = table[:]
	table2 = table[:]
	
	#i番目が正直者
	count1 = inTable(i,ps,table1,True)
	
	#i番目が不正直者
	count2 = inTable(i,ps,table2,False)
		
	return max(count1,count2)

N = int(input())
ps = []
for _ in range(N):
	An = int(input())
	cs = []
	for _ in range(An):
		x,y = map(int,input().split())
		cs.append((x-1,bool(y)))
	ps.append(cs)
#print(ps)

table = [None for _ in range(N)]
print(dfs(0,ps,table[:]))

Submission status: Wrong Answer

Solution code:
import collections
import itertools

n = int(input())

per_dict = collections.defaultdict(list)
for i in range(n):
  a = int(input())
  for j in range(a):
    x, y = map(int, input().split())
    per_dict[i + 1].append([x,y]) 

for i in range(n, -1, -1):
  flag = True
  for honests in itertools.combinations(range(1, n + 1), i):
    for h in honests:
      for x, y in per_dict[h]:
        if y == 1 and x not in honests:
          flag = False 
        if y == 0 and x in honests:
          flag = False
    if flag == True:
      break
  if flag == True:
    break
print(i)

Submission status: Wrong Answer

Solution code:
from __future__ import print_function
# import numpy as np
# import numpypy as np
import sys
input = sys.stdin.readline

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

import math
import string
import fractions
from fractions import Fraction
from fractions import gcd

def lcm(n,m):
    return int(n*m/gcd(n,m))

import re
import array
import copy
import functools
import operator

import collections
import itertools
import bisect
import heapq


from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace

from queue import PriorityQueue as pq

def reduce(p, q):
    common = fractions.gcd(p, q)
    return (p//common , q//common )
# from itertools import accumulate
# from collections import deque

from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

import random

def check(index_person, x_true_or_false, bin_str):
    return (bin_str[index_person] == x_true_or_false)


def main():
    n = int(input().strip())
    ll_xy = [[] for _ in range(n)]
    for i in range(n):
        a = int(input().strip())
        for j in range(a):
            l = list(map(int, input().strip().split()))
            l[0]-=1
            ll_xy[i].append(l)
    #eprint("ll_xy ",end=": ")
    #eprint(ll_xy)

    cnt=0
    ans=0
    for i in range(2 ** n):     # 場合ループ
        #eprint("i ",end=": ")
        #eprint(i,end=" and ")

        bin_str = format(i,'b').zfill(n)
        #eprint("bin_str ",end=": ")
        #eprint(bin_str)
        failure_flag=0
        for j in range(n):      # 人ループ
            if bin_str[j]=="1":   # その人を「真実の人」だと仮定している場合
                a=len(ll_xy[j])
                for k in range(a):  # 証言ループ
                    #eprint("証言ループ")
                    p=int(bin_str[ll_xy[j][k][0]])
                    if ll_xy[j][k][1] == 0:
                        if check(p,"0",bin_str):
                            pass
                        else:
                            failure_flag=1

                    elif ll_xy[j][k][1] == 1:
                        if check(p,"1",bin_str):
                            pass
                        else:
                            failure_flag=1
                    else:
                        try:
                            eprint("error1")
                        except Exception:
                            eprint("errorE")
        if failure_flag==0:
            cnt+=1
            ans_temp=0
            for x in bin_str:
                if x=="1":
                    ans_temp+=1
            ans=max(ans_temp,ans)
            # #eprint("success!")
    #eprint("cnt ",end=": ")
    #eprint(cnt)
    print(ans)
    return
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for i in range(N):
        a = int(input())
        for j in range(a):
            x, y = (int(i) for i in input().split())
            G[i].append((x-1, y))
            # 人iは人xのことをyと言っている
    ans = 0
    for bit in range(1 << N):
        cur = 0
        good = True  # 矛盾がない
        for i in range(N):
            if bit & (1 << i):
                # 人iは正直者
                cur += 1
                for j, y in G[i]:
                    if (bit & (1 << j)) and y == 1:
                        continue
                    elif not(bit & (1 << j)) and y == 0:
                        continue
                    elif (bit & (1 << j)) and y == 0:
                        good = False
                        break
                    elif not(bit & (1 << j)) and y == 1:
                        good = False
                        break
            else:
                # 人iはうそつき
                for j, y in G[i]:
                    if (bit & (1 << j)) and y == 0:
                        continue
                    elif not(bit & (1 << j)) and y == 1:
                        continue
                    elif (bit & (1 << j)) and y == 1:
                        good = False
                        break
                    elif not(bit & (1 << j)) and y == 0:
                        good = False
                        break
        # print(bit, ":", good)
        if good:
            ans = max(ans, cur)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools
n = int(input())
l = []
flag = True
for i in range(n):
    a = int(input())
    tmp = []
    for j in range(a):
        a1, a2 = map(int, input().split())
        if a2 == 0:
            flag = False
        l.append([i, a1-1, a2])
ans = 0
for i in range(1 << n):
    uso = False
    # print(i)
    for ll in l:
        # ll[0]が正直なのかをチェック]
        # print(ll)
        if i >> ll[0] & 1:  # 正直
            if i >> ll[1] & 1 == ll[2]:
                pass
            else:
                uso = True
                break
        else:  # 嘘
            if i >> ll[1] & 1 == ll[2]:
                uso = True
                break
    if uso == False:
        # print(bin(i))
        ans = max(ans, len(str(bin(i)).replace('0b', "").replace('0', "")))
print(ans)

Submission status: Wrong Answer

Solution code:
from __future__ import print_function
# import numpy as np
# import numpypy as np
import sys
input = sys.stdin.readline

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

import math
import string
import fractions
from fractions import Fraction
from fractions import gcd

def lcm(n,m):
    return int(n*m/gcd(n,m))

import re
import array
import copy
import functools
import operator

import collections
import itertools
import bisect
import heapq


from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace

from queue import PriorityQueue as pq

def reduce(p, q):
    common = fractions.gcd(p, q)
    return (p//common , q//common )
# from itertools import accumulate
# from collections import deque

from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

import random

def check(index_person, x_true_or_false, bin_str):
    return (bin_str[index_person] == x_true_or_false)


def main():
    n = int(input().strip())
    ll_xy = [[] for _ in range(n)]
    for i in range(n):
        a = int(input().strip())
        for j in range(a):
            l = list(map(int, input().strip().split()))
            l[0]-=1
            ll_xy[i].append(l)
    eprint("ll_xy ",end=": ")
    eprint(ll_xy)

    cnt=0
    ans=0
    for i in range(2 ** n):     # 場合ループ
        eprint("i ",end=": ")
        eprint(i,end=" and ")

        bin_str = format(i,'b').zfill(n)
        eprint("bin_str ",end=": ")
        eprint(bin_str)
        failure_flag=0
        for j in range(n):      # 人ループ
            if bin_str[j]=="1":   # その人を「真実の人」だと仮定している場合
                a=len(ll_xy[j])
                for k in range(a):  # 証言ループ
                    eprint("証言ループ")
                    p=int(bin_str[ll_xy[j][k][0]])
                    if ll_xy[j][k][1] == 0:
                        if check(p,"0",bin_str):
                            pass
                        else:
                            failure_flag=1

                    elif ll_xy[j][k][1] == 1:
                        if check(p,"1",bin_str):
                            pass
                        else:
                            failure_flag=1
                    else:
                        try:
                            eprint("error1")
                        except Exception:
                            eprint("errorE")
        if failure_flag==0:
            cnt+=1
            ans_temp=0
            for x in bin_str:
                if x=="1":
                    ans_temp+=1
            ans=max(ans_temp,ans)
            eprint("success!")
            # eprint("bin_str ",end=": ")
            # eprint(bin_str)
    # eprint("bin_str ",end=": ")
    # eprint(bin_str)
    eprint("cnt ",end=": ")
    eprint(cnt)
    print(ans)
    return
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for i in range(N):
        a = int(input())
        for j in range(a):
            x, y = (int(i) for i in input().split())
            G[i].append((x-1, y))
            # 人iは人xのことをyと言っている
    ans = 0
    for bit in range(1 << N):
        cur = 0
        good = True  # 矛盾がない
        for i in range(N):
            if bit & (1 << i):
                # 人iは正直者
                cur += 1
                for j, y in G[i]:
                    # if (bit & (1 << j)) and y == 1:
                    #    continue
                    # elif not(bit & (1 << j)) and y == 0:
                    #    continue
                    if (bit & (1 << j)) and y == 0:
                        good = False
                        break
                    elif not(bit & (1 << j)) and y == 1:
                        good = False
                        break
            else:
                # 人iはうそつき
                for j, y in G[i]:
                    # if (bit & (1 << j)) and y == 0:
                    #    continue
                    # elif not(bit & (1 << j)) and y == 1:
                    #    continue
                    if (bit & (1 << j)) and y == 1:
                        good = False
                        break
                    elif not(bit & (1 << j)) and y == 0:
                        good = False
                        break
        # print(bit, ":", good)
        if good:
            ans = max(ans, cur)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())

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

Group_1 = 'Group_1'
Group_2 = 'Group_2'
Group_none = 'None'

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

has_no_honest = False


for i in range(N):
    for A_list_i in range(A_list[i]):

        # 指名された人のGroup
        Group_mentioned = Group[x_list[i][A_list_i]-1]

        # 人iのA個目の証言が、誰かが正直者であるという内容のとき
        if y_list[i][A_list_i] == 1:
            
            # 人iのGroupと指名された人のGroupがまだ未分類のとき
            # 両方ともGroup1に振り分ける
            if Group[i] == Group_none and Group_mentioned == Group_none:
                Group[i] = Group_1
                Group_mentioned = Group_1
            
            # 人iのGroupもしくは指名された人のGroupのどちらか一方は未分類かつ
            # もう片方は分類済みのとき
            # 未分類の方を分類済みのGroupと同じにする
            elif Group[i] != Group_mentioned and Group[i] == Group_none:
                Group[i] = Group_mentioned
            elif Group[i] != Group_mentioned and Group_mentioned == Group_none:
                Group_mentioned = Group[i]

            # 人iのGroupと指名された人のGroupが違う、かつ
            # 人iと指名された人がともに分類済みであるとき
            # 矛盾するので、正直者は存在しない
            elif Group[i] != Group_mentioned and Group[i] != Group_none and Group_mentioned != Group_none:
                has_no_honest = True
                break

        # 人iのA個目の証言が、誰かが嘘つきであるという内容のとき
        elif y_list[i][A_list_i] == 0:

            # 人iのGroupと指名された人のGroupがまだ未分類のとき
            # 人iはGroup1、指名された人はGroup2に分類する
            if Group[i] == Group_none and Group_mentioned == Group_none:
                Group[i] = Group_1
                Group_mentioned = Group_2

            # 人iのGroupもしくは指名された人のGroupのどちらか一方は未分類かつ
            # もう片方は分類済みのとき
            # 未分類の方を分類済みのGroupと違うGroupにする
            elif Group[i] != Group_mentioned and Group[i] == Group_none:
                if Group_mentioned == Group_1:
                    Group[i] = Group_2
                else:
                    Group[i] = Group_1
            elif Group[i] != Group_mentioned and Group_mentioned == Group_none:
                if Group[i] == Group_1:
                    Group_mentioned = Group_2
                else:
                    Group_mentioned = Group_1

            # 人iのGroupと指名された人のGroupが同じ、かつ
            # 人iと指名された人がともに分類済みであるとき
            # 矛盾するので、正直者は存在しない
            elif Group[i] == Group_mentioned and Group[i] != Group_none and Group_mentioned != Group_none:
                has_no_honest = True
                break

if has_no_honest:
    print(0)
else:
    print(max(Group.count(Group_1), Group.count(Group_2)))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for i in range(N):
        a = int(input())
        for j in range(a):
            x, y = (int(i) for i in input().split())
            G[i].append((x-1, y))
            # 人iは人xのことをyと言っている
    ans = 0
    for bit in range(1 << N):
        cur = 0
        good = True  # 矛盾がない
        for i in range(N):
            if bit & (1 << i):
                # 人iは正直者
                cur += 1
                for j, y in G[i]:
                    print(i, j, y, "人jは、", bit & (1 << j))
                    # if (bit & (1 << j)) and y == 1:
                    #    continue
                    # elif not(bit & (1 << j)) and y == 0:
                    #    continue
                    if (bit & (1 << j)) and y == 0:
                        good = False
                        break
                    elif not(bit & (1 << j)) and y == 1:
                        good = False
                        break
            else:
                # 人iはうそつき
                for j, y in G[i]:
                    print(i, j, y, "人jは、", bit & (1 << j))
                    # if (bit & (1 << j)) and y == 0:
                    #    continue
                    # elif not(bit & (1 << j)) and y == 1:
                    #    continue
                    if (bit & (1 << j)) and y == 1:
                        good = False
                        break
                    elif not(bit & (1 << j)) and y == 0:
                        good = False
                        break
        # print(bit, ":", good)
        if good:
            ans = max(ans, cur)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

ans = 0
honest = [0]*n
cnt=0
for i in range(2**n): #bit全探索
    for j in range(n):
        if((i>>j)&1):
            honest[j] = 1
            cnt+=1
        else:
            honest[j] = 0
            
        f = True
        for k in range(n):
            if honest[k]!=1:
                f = False
                break
            for l in range(a[k]):
                if y[k][l]!=honest[x[k][l]]:
                    f = False
                    break
            if f:
                ans = max(ans,cnt)
        cnt=0

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

N = int(input())

xy_list = [{} for i in range(N)]
for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = list(map(int, input().split()))
        xy_list[i][str(x - 1)] = y

max_n_honest = 0
for n_honest in range(N + 1):
    for is_honest in itertools.combinations(range(N), n_honest):
        aaa = True
        for h_idx in range(N):
            target_is_honest = int(h_idx in is_honest)
            testimony = xy_list[h_idx]
            for honest_idx in is_honest:
                if str(honest_idx) in testimony:
                    if testimony[str(honest_idx)] != target_is_honest:
                        aaa = False
                        break
        if not aaa:
            continue
        n_honest = len(is_honest)

        if n_honest > max_n_honest:
            max_n_honest = n_honest

print(max_n_honest)

Submission status: Wrong Answer

Solution code:
import collections
import itertools

n = int(input())

per_dict = collections.defaultdict(list)
for i in range(n):
  a = int(input())
  for j in range(a):
    x, y = map(int, input().split())
    per_dict[i].append([x,y]) 

for i in range(n, -1, -1):
  flag = True
  for honests in itertools.combinations(range(n), i):
    for h in honests:
      for x, y in per_dict[h]:
        if y == 1 and x not in honests:
          flag = False 
        if y == 0 and x in honests:
          flag = False
    if flag == True:
      break
  if flag == True:
    break
print(i)

Submission status: Wrong Answer

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


def countBit(x):
    if x == 0:
        return 0
    else:
        return countBit(x >> 1) + (x & 1)


res = 0
for bits in range(2 ** N):
    consistency = True
    for i, testimony in enumerate(A):
        if not (bits & (1 << i)):
            continue
        for t in testimony:
            if (bits & (1 << t[0])) ^ t[1]:
                consistency = False

    if consistency:
        res = max(res, countBit(bits))

print(res)