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 = [[] for _ in range(N)]
b = []
for i in range(N):
  A_i = int(input())
  b.append(A_i)
  for j in range(A_i):
    a[i].append(list(map(int, input().split())))
    
book = a
max_honest = 0

i = 0
while i < N:
  honest_p = []
  unkind_p = []
  honest_p.append(i)
  contradiction = False
  while True:
    changed = False
    for j in honest_p:
      for k in range(b[j]):
        people = book[j][k][0] - 1
        testimony = book[j][k][1]
        if testimony and people in unkind_p:
          max_honest = 0
          contradiction = True
          break
        if not testimony and people in honest_p:
          max_honest = 0
          contradiction = True
          break
        if testimony and not people in honest_p:
          honest_p.append(people)
          changed = True
        if testimony and not people in unkind_p:
          unkind_p.append(people)
          changed = True
    if contradiction:
      break
    if len(honest_p) > max_honest:
      max_honest = len(honest_p)
    if not changed:
      break
  i += 1

print(max_honest)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [[] for _ in range(N)]
b = []
for i in range(N):
  A_i = int(input())
  b.append(A_i)
  for j in range(A_i):
    a[i].append(list(map(int, input().split())))
    
book = a
max_honest = 0

i = 0
while i < N:
  honest_p = []
  unkind_p = []
  honest_p.append(i)
  contradiction = False
  while True:
    changed = False
    for j in honest_p:
      for k in range(b[j]):
        people = book[j][k][0] - 1
        testimony = book[j][k][1]
        if testimony and people in unkind_p:
          max_honest = 0
          contradiction = True
          break
        if not testimony and people in honest_p:
          max_honest = 0
          contradiction = True
          break
        if testimony and not people in honest_p:
          honest_p.append(people)
          changed = True
        if testimony and not people in unkind_p:
          unkind_p.append(people)
          changed = True
    print(honest_p)
    print(unkind_p)
    if contradiction:
      break
    if len(honest_p) > max_honest:
      max_honest = len(honest_p)
    if not changed:
      break
  i += 1

print(max_honest)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [[] for _ in range(N)]
b = []
for i in range(N):
  A_i = int(input())
  b.append(A_i)
  for j in range(A_i):
    a[i].append(list(map(int, input().split())))
    
book = a
max_honest = 0

i = 0
while i < N:
  honest_p = []
  unkind_p = []
  honest_p.append(i)
  contradiction = False
  while True:
    changed = False
    for j in honest_p:
      for k in range(b[j]):
        people = book[j][k][0] - 1
        testimony = book[j][k][1]
        if testimony and people in unkind_p:
          max_honest = 0
          contradiction = True
          break
        if not testimony and people in honest_p:
          max_honest = 0
          contradiction = True
          break
        if testimony and not people in honest_p:
          honest_p.append(people)
          changed = True
    print(honest_p)
    if contradiction:
      break
    if not changed:
      break
    if len(honest_p) > max_honest:
      max_honest = len(honest_p)
  i += 1

print(max_honest)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
data_xy = []
for i in range(N):
    A = int(input())
    xy = []
    for i in range(A):
        [x,y] = list(map(int,input().split()))
        xy.append([x-1, y])
    data_xy.append(xy)
data_xy = np.array(data_xy)
ans = 0
for i in range(2**N):
    p_list = np.zeros(N)
    for j in range(N):
        if (i>>j) & 1 == 1:
            p_list[j] = 1
    flag = True
    for j in range(N):
        if p_list[j] == 1:
            for k in range(len(data_xy[j])):
                x = data_xy[j][k][0]
                y = data_xy[j][k][1]
                if p_list[x] != y:
                    flag = False
    if flag == True:
        ans = max(sum(p_list),ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
data_xy = []
for i in range(N):
    A = int(input())
    xy = []
    for i in range(A):
        [x,y] = list(map(int,input().split()))
        xy.append([x-1, y])
    data_xy.append(xy)
data_xy = np.array(data_xy)
p_list = np.zeros(N)
ans = 0
for i in range(2**N):
    for j in range(N):
        if (i>>j) & 1 == 1:
            p_list[j] = 1
    flag = True
    for j in range(N):
        if p_list[j] == 1:
            for k in range(len(data_xy[j])):
                x = data_xy[j][k][0]
                y = data_xy[j][k][1]
                if p_list[x] != y:
                    flag = False
    if flag == True:
        ans = max(sum(p_list),ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
data_xy = []
for i in range(N):
    A = int(input())
    xy = []
    for i in range(A):
        [x,y] = list(map(int,input().split()))
        xy.append([x-1, y])
    data_xy.append(xy)
p_list = [0]*N
ans = 0
for i in range(2**N):
    for j in range(N):
        if (i>>j) & 1 == 1:
            p_list[j] = 1
    flag = True
    for j in range(N):
        if p_list[j] == 1:
            for k in range(len(data_xy[j])):
                x = data_xy[j][k][0]
                y = data_xy[j][k][1]
                if p_list[x] != y:
                    flag = False
    if flag == True:
        ans = max(sum(p_list),ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [] #どこからどこまでがiさんの証言かN×2の配列
tes = []#証言を入れていく
pro_sta = []#過程の状態
tes_count = 0
suc_flag = 1 #矛盾が生じてなければ1
max_honest = 0

# 入力受け取り
for i in range(N):
    a = int(input())
    A.append([tes_count,tes_count + a])
    tes_count += a
    for k in range(a):
        x,y = list(map(int,input().split()))
        tes.append([x,y])

t = (2 ** N -1)
for p in range(t):
    pro_sta = []
    suc_flag = 1
    t_str = str(format(p,"0"+str(N)+"b"))
    for q in range(N):
        pro_sta.append(t_str[q])

    for q in range(N):
        if pro_sta[q] == "1":
            for r in range(A[q][0],A[q][1]):
                if tes[r][1] != int(pro_sta[tes[r][0] - 1]):
                    suc_flag = 0
    if suc_flag == 1:
        honest_count = pro_sta.count("1")
        max_honest = max(max_honest,honest_count)

print(max_honest)

Submission status: Wrong Answer

Solution code:
N = int(input())
XY = []
for i in range(N):
    XY.append([])
    A = int(input())
    for a in range(A):
        x, y = map(int, input().split())
        XY[i].append([x, y])

answer = 0
for p in range(0, 2**N-1):
    ok = True
    h = 0
    for i in range(N):
        if p & (1 << i):
            h += 1
            for x, y in XY[i]:
                x -= 1
                if y == 0: # unkind
                    if p & (1 << x):
                        ok = False
                if y == 1: # x is honest
                    if not p & (1 << x):
                        ok = False
    if ok:
        answer = max(answer, h)
print(answer)

Submission status: Wrong Answer

Solution code:
#入力はn人のx,yに分けないといけない
n = int(input())
a = []
x = [[] for i in range(n)]
y = [[] for i in range(n)]
for i in range(n):
    a.append(int(input()))
    for j in range(a[i]):
        xx, yy = (int(i) for i in input().split())
        x[i].append(xx)
        y[i].append(yy)

testimony = [[2]*n for i in range(n)]

for i in range(n):
    for j in range(a[i]):
        if (y[i][j] == 1):
            testimony[i][x[i][j] - 1] = 1
        elif(y[i][j] == 0):
            testimony[i][x[i][j]-1] = 0

ans = 0
for i in range(2**n):
    bit_list = []
    for j in range(n):
        if ((i >> j) & 1):
            bit_list.append(1)
        else:
            bit_list.append(0)
    flag = 1
    for k in range(n):
        if(bit_list[k] == 1):
            for l in range(n):
                if(testimony[k][l] != 2):
                    if(testimony[k][l] != bit_list[l]):
                        flag = 0
                        break
    if(flag == 1):
        ans = max(sum(bit_list),ans)
    print(ans)

Submission status: Wrong Answer

Solution code:
#入力はn人のx,yに分けないといけない
n = int(input())
a = []
x = [[] for i in range(n)]
y = [[] for i in range(n)]
for i in range(n):
    a.append(int(input()))
    for j in range(a[i]):
        xx, yy = (int(i) for i in input().split())
        x[i].append(xx)
        y[i].append(yy)

testimony = [[2]*n for i in range(n)]

for i in range(n):
    for j in range(a[i]):
        if (y[i][j] == 1):
            testimony[i][x[i][j] - 1] = 1
        elif(y[i][j] == 0):
            testimony[i][x[i][j]-1] = 0

ans = 0
for i in range(2**n):
    bit_list = []
    for j in range(n):
        if ((i >> j) & 1):
            bit_list.append(1)
        else:
            bit_list.append(0)
            print(bit_list)
    flag = 1
    for k in range(n):
        if(bit_list[k] == 1):
            for l in range(n):
                if(testimony[k][l] != 2):
                    if(testimony[k][l] != bit_list[l]):
                        flag = 0
                        break
    if(flag == 1):
        ans = max(sum(bit_list),ans)
    print(ans)

Submission status: Wrong Answer

Solution code:
def ok(n, X, Y, mask):
    for i in range(n):
        for x, y in zip(X[i], Y[i]):
            z = mask & (2**(x-1))
            z = int(z > 0)
            if mask & (2**i):
                if z != y:
                    return False
            else:
                if z == y:
                    return False
    return True

def solve(n, X, Y):
    best = 0
    for mask in range(2**n):
        if ok(n, X, Y, mask):
            cnt = 0
            for i in range(n):
                if mask & (2**i):
                    cnt += 1
            best = max(best, cnt)
    return best

n = int(input())
X, Y = [], []
for i in range(n):
    a = int(input())
    x = [0] * a
    y = [0] * a
    for j in range(a):
        x[j], y[j] = map(int, input().split())
    X.append(x)
    Y.append(y)
print(solve(n, X, Y))

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=0
#katei[2:]
shou=[]
for i in range(N):
    n=int(input())
    if n!=0:
        tmp=[]
        for _ in range(n):
            h=list(map(int,input().split()))
            h[0]-=1
            tmp.append(h)
        shou.append(tmp)
    else:
        shou.append([])

for i in range(2**N):
    bit=str(bin(i))[2:].zfill(N)
    flag=True
    for j in range(N):
        if len(shou[j])==0:
            continue
        for each in shou[j]:
            
            if int(bit[j])==0:
                tmp=1-each[1]
                if int(bit[each[0]])!=tmp:
                    #print(each)
                    flag=False
            else:
                tmp=each[1]
                if int(bit[each[0]])!=tmp:
                    #print(each)
                    flag=False
    if flag:
        ans=max(ans,bit.count("1"))
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=0
#katei[2:]
shou=[]
for i in range(N):
    n=int(input())
    if n!=0:
        tmp=[]
        for _ in range(n):
            h=list(map(int,input().split()))
            h[0]-=1
            tmp.append(h)
        shou.append(tmp)
    else:
        shou.append([])

for i in range(2**N):
    bit=str(bin(i))[2:].zfill(N)
    flag=True
    for j in range(N):
        for each in shou[j]:
            
            if int(bit[j])==0:
                tmp=1-each[1]
                if int(bit[each[0]])!=tmp:
                    #print(each)
                    flag=False
            else:
                tmp=each[1]
                if int(bit[each[0]])!=tmp:
                    #print(each)
                    flag=False
    if flag:
        ans=max(ans,bit.count("1"))
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=0
#katei[2:]
shou=[]
for i in range(N):
    n=int(input())
    if n!=0:
        tmp=[]
        for _ in range(n):
            h=list(map(int,input().split()))
            h[0]-=1
            tmp.append(h)
        shou.append(tmp)
    else:
        shou.append([])

for i in range(2**N):
    flag=True
    bit=str(bin(i))[2:].zfill(N)
    for j in range(N):
        if len(shou[j])==0:
            continue
        for each in shou[j]:
            if bit[j]==0:
                tmp=1-each[1]
                if each[0]!=tmp:
                    flag=False
            else:
                tmp=each[1]
                if each[0]!=tmp:
                    flag=False
    if flag:
        ans=max(ans,bit.count("1"))
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=0
#katei[2:]
shou=[]
for i in range(N):
    n=int(input())
    tmp=[]
    for _ in range(n):
        h=list(map(int,input().split()))
        h[0]-=1
        tmp.append(h)
    shou.append(tmp)

for i in range(2**N):
    bit=str(bin(i))[2:].zfill(N)
    flag=True
    for j in range(N):
        for each in shou[j]:
            
            if int(bit[j])==0:
                tmp=1-each[1]
                if int(bit[each[0]])!=tmp:
                    #print(each)
                    flag=False
            else:
                tmp=each[1]
                if int(bit[each[0]])!=tmp:
                    #print(each)
                    flag=False
    if flag:
        ans=max(ans,bit.count("1"))
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
XY=[]
for i in range(N):
  a=int(input())
  s=[]
  for j in range(a):
    s.append(list(map(int,input().split())))
  XY.append(s)
  
ans=0
for i in range(2**N):
  table =list( format(i,"b").zfill(N)[::-1] )
  flag=1
  for j,l in enumerate(XY):
    for xy in l:
      x=xy[0]-1
      y=xy[1]
      if table[j]=="1":
        if table[x]!=str(y):
          flag=0
      elif table[j]=="0":
        if table[x]==str(y):
          flag=0
  if flag==1:
    ans=max(ans,table.count("1"))
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
XY=[]
for i in range(N):
  a=int(input())
  s=[]
  for j in range(a):
    s.append(list(map(int,input().split())))
  XY.append(s)
  
ans=0
for i in range(2**N-1,-1,-1):
  table =list( format(i,"b").zfill(N)[::-1] )
  flag=1
  for j,l in enumerate(XY):
    for xy in l:
      x=xy[0]-1
      y=xy[1]
      if table[j]=="1":
        if table[x]!=str(y):
          flag=0
          break
      elif table[j]=="0":
        if table[x]==str(y):
          flag=0
          break
    if flag==0:
      break
  if flag==1:
    ans=max(ans,table.count("1"))
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[]
XY=[]
for i in range(N):
  a=int(input())
  A.append(a)
  s=[]
  for j in range(a):
    s.append(list(map(int,input().split())))
  XY.append(s)
  
ans=0
for i in range(2**N-1,-1,-1):
  table =list( format(i,"b").zfill(N) )
  flag=1
  for j,l in enumerate(XY):
    for xy in l:
      x=xy[0]-1
      y=xy[1]
      if table[j]=="1":
        if table[x]!=str(y):
          flag=0
          break
      else:
        if table[x]==str(y):
          flag=0
          break
    if flag==0:
      break
  if flag==1:
    ans=max(ans,table.count("1"))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
Ans = []
for i in range(n):
    Ai = int(input())
    a = []
    for j in range(Ai):
        x,y = map(int,input().split())
        a.append((x,y))
    Ans.append(a)
Honest = 0
TT = [bin(i)[2:].zfill(n) for i in range(2**n)]
#print(TT)
for truth in TT:
    truth = str(truth)
    people = [-1]*n
    #print("====")
    #print(truth)
    flag = True
    for i in range(n):
        tt = truth[i]
        answers = Ans[i]
        #print(answers)
        if tt == "1":
            #証言は信頼できると仮定
            for x,v in answers:
                #xに対してv
                if v:#x人が正直者という証言
                    if people[x-1] == 0:#xは嘘つきと証言されているとき
                        flag = False
                        #print("A")
                    else:
                        people[x-1] = 1
                else:#xは嘘つきという証言
                    if people[x-1] == 1:
                        flag = False
                        #print("B")
                    else:
                        people[x-1] = 0
        else:
            #証言は嘘と仮定
            for x,v in answers:
                if v == 0:
                    if people[x-1] == 0:#xは嘘つきと証言されているとき
                        flag = False
                        #print("C")
                    else:
                        people[x-1] = 1
                else:#xは嘘つきという証言
                    if people[x-1] == 1:
                        flag = False
                        #print("D")
                    else:
                        people[x-1] = 0
    if flag:
        Flag = True
        for i in range(len(people)):
            if people[i] == -1:
                people[i] = 0
            else:
                if truth[i] != str(people[i]):
                    Flag = False
                    break
        #print(*people)
        
        if Flag:
            Honest = max(Honest,sum(people))
print(Honest)

Submission status: Wrong Answer

Solution code:
n = int(input())
Ans = []
for i in range(n):
    Ai = int(input())
    a = []
    for j in range(Ai):
        x,y = map(int,input().split())
        a.append((x,y))
    Ans.append(a)
Honest = 0
TT = [bin(i)[2:].zfill(n) for i in range(2**n)]
#print(TT)
for truth in TT:
    truth = str(truth)
    people = [-1]*n
    #print("====")
    #print(truth)
    flag = True
    for i in range(n):
        tt = truth[i]
        answers = Ans[i]
        #print(answers)
        if tt == "1":
            #証言は信頼できると仮定
            for x,v in answers:
                #xに対してv
                if v:#x人が正直者という証言
                    if people[x-1] == 0:#xは嘘つきと証言されているとき
                        flag = False
                        #print("A")
                    else:
                        people[x-1] = 1
                else:#xは嘘つきという証言
                    if people[x-1] == 1:
                        flag = False
                        #print("B")
                    else:
                        people[x-1] = 0
        else:
            #証言は嘘と仮定
            for x,v in answers:
                if v == 0:
                    if people[x-1] == 0:#xは嘘つきと証言されているとき
                        flag = False
                        #print("C")
                    else:
                        people[x-1] = 1
                else:#xは嘘つきという証言
                    if people[x-1] == 1:
                        flag = False
                        #print("D")
                    else:
                        people[x-1] = 0
    if flag:
        Flag = True
        for i in range(len(people)):
            if people[i] == -1:
                people[i] = 0
            else:
                if truth[i] != str(people[i]):
                    Flag = False
                    break
        #print(*people)
        
        if Flag:
            Honest = max(Honest,sum(people))
print(Honest)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
x = []
y = []
for i in range(N):
    A.append(int(input()))
    x2 = []
    y2 = []
    for j in range(A[i]):
        xy = input().split()
        x2.append(int(xy[0]))
        y2.append(int(xy[1]))
    x.insert(i, x2)
    y.insert(i, y2)

ans = 0
for i in range(pow(2, N)):
    flag = True
    for j in range(N):
        if not(i & (1<<j)):
            continue
        else:
            for k in range(A[j]):
                if (((i>>(x[j][k]-1))&1) ^ y[j][k]):
                    flag = False
    count = 0
    if flag:
        for j in range(N):
            if i&(i<<j):
                count += 1
    if ans < count:
        ans = count
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
X=[]
Y=[]
A=[0]*n
for i in range(n):
  A[i]=int(input())
  a=A[i]
  x=[0]*a
  y=[0]*a
  for j in range(a):
    x[j],y[j]=[int(s) for s in input().split()]
  X.append(x)
  Y.append(y)
  
s=0
for i in range(2**n):
  c=0
  d=0
  B=[0]*n
  for j in range(n):
    if((i >> j) & 1):
      c=c+1
      B[j]=1
  for k in range(n):
    if B[k]==1:
      for j in range(A[k]):
        if Y[k][j]!=B[X[k][j]-1]:
          d=-1
          break
    if d<0:
      break
  if s<c:
    s=c
      
      
print(s)

Submission status: Wrong Answer

Solution code:
import sys

def resolve():
    N=int(input().rstrip())
    A=[0]*N
    x=[[] for i in range(N)]
    y=[[] for i in range(N)]
    
    
    for i in range(N):
        A[i]=int(input().rstrip())

        for j in range(A[i]):
            x[i].append([0])
            y[i].append([0])
            x[i][j],y[i][j]=list(map(int,input().rstrip().split()))
        
        #自分は真を追加
        A[i]+=1
        x[i].append(i+1)
        y[i].append(1)


    flag=[[1 for i in range(N)] for j in range (N)]
    

    for i in range(N):
            for k in range(N):
                for j in range(A[i]):
                    for l in range(A[k]):
                        if((x[i][j]==x[k][l])&(y[i][j]!=y[k][l])):#iとkで矛盾
                            flag[i][k]=0
                            for s in range (A[i]):#自己矛盾チェック
                                if((x[i][s]-1==k)&(y[i][s]==1)):#自己矛盾
                                    flag[i][i]=0
                            break
                        else:
                            continue
                        break
                    else:
                        continue
                    break

    ans=0
    
    e=[[] for _ in range(N)]
    o=0
    flage=True
    for i in range(N):
        o+=flag[i][i]
        for j in range(N):
            e[i].append([0])
            #o[i].append([0])    
            e[i][j]=0
            #o[i][j]=0
            if(i==j):
                e[i][j]=1
            
            if(e[i][j]!=flag[i][j]):
                flage=False
            #if(o[i][j]!=flag[i][j]):
            #    flago=False
    
    if(flage):
        print(1)
        return
    if(o==0):
        print(0)
        return


    
    for i in range(N):
        b=0
        for j in range(N):
            if(flag[j][i]==1):
                b+=1
        if(b<=1):
            flag[i][i]=0
    for i in range(N):
        ans+=flag[i][i]

    if(ans==0):
        print(1)
        return
        
    print(ans)

    

    


from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3
1
2 1
1
1 1
1
2 0"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0"""
        output = """0"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """2
1
2 0
1
1 0"""
        output = """1"""
        self.assertIO(input, output)

if __name__ == "__main__":
    #unittest.main()
    resolve()

Submission status: Wrong Answer

Solution code:

import sys

def resolve():
    N=int(input().rstrip())
    A=[0]*N
    x=[[] for i in range(N)]
    y=[[] for i in range(N)]
    
    
    for i in range(N):
        A[i]=int(input().rstrip())

        for j in range(A[i]):
            x[i].append([0])
            y[i].append([0])
            x[i][j],y[i][j]=list(map(int,input().rstrip().split()))
        
        #自分は真を追加
        A[i]+=1
        x[i].append(i+1)
        y[i].append(1)


    flag=[[1 for i in range(N)] for j in range (N)]
    

    for i in range(N):
            for k in range(N):
                for j in range(A[i]):
                    for l in range(A[k]):
                        if((x[i][j]==x[k][l])&(y[i][j]!=y[k][l])):#iとkで矛盾
                            flag[i][k]=0
                            for s in range (A[i]):#自己矛盾チェック
                                if((x[i][s]-1==k)&(y[i][s]==1)):#自己矛盾
                                    flag[i][i]=0
                            break
                        else:
                            continue
                        break
                    else:
                        continue
                    break

    ans=0
    
    e=[[] for _ in range(N)]
    o=0
    flage=True
    for i in range(N):
        o+=flag[i][i]
        for j in range(N):
            e[i].append([0])
            #o[i].append([0])    
            e[i][j]=0
            #o[i][j]=0
            if(i==j):
                e[i][j]=1
            
            if(e[i][j]!=flag[i][j]):
                flage=False
            #if(o[i][j]!=flag[i][j]):
            #    flago=False
    
    if(flage):
        print(1)
        return
    if(o==0):
        print(0)
        return


    
    for i in range(N):
        b=0
        for j in range(N):
            if(flag[j][i]==1):
                b+=1
        if(b<=1):
            flag[i][i]=0
    for i in range(N):
        ans+=flag[i][i]

    print(ans)

    

    


from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3
1
2 1
1
1 1
1
2 0"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0"""
        output = """0"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """2
1
2 0
1
1 0"""
        output = """1"""
        self.assertIO(input, output)

if __name__ == "__main__":
    #unittest.main()
    resolve()

Submission status: Wrong Answer

Solution code:

import sys

def resolve():
    N=int(input().rstrip())
    A=[0]*N
    x=[[] for i in range(N)]
    y=[[] for i in range(N)]
    
    
    for i in range(N):
        A[i]=int(input().rstrip())

        for j in range(A[i]):
            x[i].append([0])
            y[i].append([0])
            x[i][j],y[i][j]=list(map(int,input().rstrip().split()))
        
        #自分は真を追加
        A[i]+=1
        x[i].append(i+1)
        y[i].append(1)


    flag=[[1 for i in range(N)] for j in range (N)]
    

    for i in range(N):
            for k in range(N):
                for j in range(A[i]):
                    for l in range(A[k]):
                        if((x[i][j]==x[k][l])&(y[i][j]!=y[k][l])):#iとkで矛盾
                            flag[i][k]=0
                            for s in range (A[i]):#自己矛盾チェック
                                if((x[i][s]-1==k)&(y[i][s]==1)):#自己矛盾
                                    flag[i][i]=0
                            break
                        else:
                            continue
                        break
                    else:
                        continue
                    break

    ans=0
    
    e=[[] for _ in range(N)]
    o=[[] for _ in range(N)]
    flage=True
    flago=True
    for i in range(N):
        
        for j in range(N):
            e[i].append([0])
            o[i].append([0])    
            e[i][j]=0
            o[i][j]=0
            if(i==j):
                e[i][j]=1
            
            if(e[i][j]!=flag[i][j]):
                flage=False
            if(o[i][j]!=flag[i][j]):
                flago=False
    
    if(flage):
        print(1)
        return
    if(flago):
        print(0)
        return


    
    for i in range(N):
        b=0
        for j in range(N):
            if(flag[j][i]==1):
                b+=1
        if(b<=1):
            flag[i][i]=0
    for i in range(N):
        ans+=flag[i][i]

    print(ans)

    

    


from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3
1
2 1
1
1 1
1
2 0"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0"""
        output = """0"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """2
1
2 0
1
1 0"""
        output = """1"""
        self.assertIO(input, output)

if __name__ == "__main__":
    #unittest.main()
    resolve()

Submission status: Wrong Answer

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

ans=0
for i in range(N**2):
    flag=True
    for j in range(N):
        if (i>>j)&1==0:
            continue
        for x,y in evidences[j]:
            if (i>>x)&1!=y:
                flag=False
                break
        if not flag:
            break

    if flag:
        ans=max(ans,bin(i)[2:].count('1'))

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[[] for i in range(n)]
for i in range(n):
    c=int(input())
    for j in range(c):
        x,y = map(int, input().split())
        a[i].append([x,y])
from itertools import permutations, combinations,combinations_with_replacement,product
ans3 = 0
for ans  in product([0,1],repeat=n):
    flag = True
    for i, check in enumerate(a):
        if ans[i]==0:
            continue
        
        for x, y in check:
            if y^ans[i] != ans[x-1]:
                flag = False
                break
    if flag:
        ans3=max(sum(ans), ans3)
print(ans3)