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())
persons = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        persons[i].append([x-1, y])
ans = 0
amax = 0
b = [[] for _ in range(n)]
for i in range(2**n):
    tmp = list([i >> j & 1 for j in range(n)])
    flag = 0
    for q, k in enumerate(tmp):
        if k == 1:
            for person in persons[q]:
                if person[1] == 1:
                    if 0 in b[person[0]]:
                        flag = 1
                else:
                    if 1 in b[person[0]]:
                        flag = 1
                b[person[0]].append(person[1])
        else:
            for person in persons[q]:
                if person[1] == 1:
                    if 1 in b[person[0]]:
                        flag = 1
                    b[person[0]].append(0)
                else:
                    if 0 in b[person[0]]:
                        flag = 1
                    b[person[0]].append(1)
    # print(b)
    u = []
    for h, b1 in enumerate(b):
        if len(set(b1)) > 1:
            flag = 1
        if set(b1):
            u.append(list(set(b1))[0])
        else:
            u.append(tmp[h])
    # print(u)
    # print(tmp)
    if flag == 0 and u == tmp:
        for t in tmp:
            if t == 1:
                ans += 1
    if amax < ans:
        amax = ans
    ans = 0
    b = [[] for _ in range(n)]
print(amax)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n=int(input())
cnt=[0 for i in range(n)]
x=[[]for i in range(n)]
for i in range(n):
    cnt[i]=int(input())
    for j in range(cnt[i]):
        x[i].append(list(map(int,input().split())))
lab=[0 for i in range(n)]
T=[0 for i in range(n)]
F=[0 for i in range(n)]
res2=0
def f(k,cnt2,res):
    global lab,x,cnt,T,F,res2,n
    if cnt2==n:
        if F!=lab:
            return
        #print("ok")
        my_sum=sum(lab)
        abc=n-my_sum
        if abc>res2:
            res2=abc
                
    else:
        #k if False
        lab[k]+=1
        f(k+1,cnt2+1,res)
        lab[k]-=1
        #k is True
        T2=T.copy()
        F2=F.copy()
        for i in range(cnt[k]):
            if x[k][i][1]==0:
                F[x[k][i][0]-1]+=1
            else:
                T[x[k][i][0]-1]+=1
        f(k+1,cnt2+1,res+1)
        T=T2.copy()
        F=F2.copy()

f(0,0,0)
    

print(res2)

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=0
katei=0
#katei[2:]
shou=[]
for i in range(N):
    n=int(input())
    tmp=[]
    for _ in range(n):
        x,y=list(map(int,input().split()))
        x-=1
        tmp.append([x,y])
    shou.append(tmp)
#print(shou)
for i in range(2**N):
    flag=True
    tmp=str(bin(katei))[2:].zfill(N)
    #print(tmp)
    #print()
    #print()
    for j in range(N):
        #print(tmp[j])
        if len(shou[j])==0:
            continue
        for k in shou[j]:
            #print(k)
            #print(tmp[k[0]])
            #print()
            if tmp[j]=="0":
                if tmp[k[0]]==str(k[1]):
                    #print("false")
                    flag=False
            else:
                if tmp[k[0]]!=str(k[1]):
                    #print("falkse")
                    flag=False
            #print(state)
    if flag:

        #print("collect:",tmp)
        ans=max(ans,bin(katei).count("1"))
            
            
    katei+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
dic = defaultdict(list)
A = []
for i in range(N):
    a = int(input())
    A.append(a)
    for j in range(a):
        x,y = map(int,input().split())
        dic[i].append((x-1,y))
# print(dic)

def dfs(n):
    if n == N: return
    

ans = []
for i in range(N):
    p = [-1] * N
    p[i] = 1
    for x,y in dic[i]:
        p[x] = y
    flg = True
    # print(p,i)
    for j in range(N):
        if j == i: continue
        if p[j] == 0: continue
        for xj,yj in dic[j]:
            if p[xj] != yj:
                if p[j] == 1:
                    flg = False
                    break
                elif p[j] == -1:
                    p[j] = 0
        if not flg:
            p = [0]
            break
    ans.append(p.count(1))
print(max(ans))

Submission status: Wrong Answer

Solution code:
import itertools

n = int(input())

answers = []
for i in range(n):
    a = int(input())
    xy = []
    for j in range(a):
        xy.append([int(x) for x in input().split(' ')])
    answers.append(xy)

max = 0

def recur(org_mappings, index, count):
    global max

    if index >= n:
        if count >= max:
            max = count
        return
    mappings = org_mappings.copy()

    flag = True
    for i in range(len(answers[index])):
        x, y = answers[index][i]
        x = x - 1
        if x in mappings:
            if y != mappings[x]:
                flag = False
                break
        else:
            mappings[x] = y

    if flag == True:
        if index in mappings and mappings[index] == 0:
            pass
        else:
            mappings[index] = 1
            recur(mappings, index + 1, count + 1)
    
    if (index in mappings) and (mappings[index] == 1):
        pass
    else:
        org_mappings = org_mappings.copy()
        recur(org_mappings, index + 1, count)

mappings = {}
recur(mappings, 0, 0)

print(max)

Submission status: Wrong Answer

Solution code:
import itertools
from collections import deque

def main():
    N = int(input())
    A = [0]*N
    x = [0]*N
    y = [0]*N
    for i in range(N):
        A[i] = int(input())
        x_i = deque()
        y_i = deque()
        for j in range(A[i]):
            x_j, y_j = map(int, input().split())
            x_i.append(x_j)
            y_i.append(y_j)
        x[i] = list(x_i)
        y[i] = list(y_i)

    ret_max = 0
    p = itertools.product([0, 1], repeat=N)
    for l in p:
        mujun = True
        for i in range(N):
            for j in range(A[i]):
                n = x[i][j]
                flag = y[i][j]
                if l[n-1] != int(not flag ^ l[i]):
                    mujun = False
                    break
        if mujun:
            ret_max = max(ret_max, sum(l))
    print(ret_max)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())   #人の人数

b = []
c = []
d = []
ans = 0
for i in range(n):
    a = int(input()) #何段の証言になるか
    for l in range(a):
        x,y = list(map(int,input().split()))
        b.append(x)  #矛先
        c.append(y)  #審議
#print(b)
#print(c)
for o in range(n):
    ans = 0
    for m in range(len(b)):
        if b[m] == o+1:
            if c[m] == 1:
                ans += 1
            else:
                ans -= 1
    d.append(ans)
#print(d)
sorted(d)

if len(set(d)) == 1:
    if sum(d) == 0:
        print(0)
    else:
        print(len(set(d)))
else:
    print(len(set(d)))

Submission status: Wrong Answer

Solution code:
import sys 

n = int(input())
Asgs = list()

def get_sgs(an):
    sgs = [list(map(int, input().split())) for i in range(an)]
    return sgs


for i in range(n):
    an = int(input())
    Asgs.append(get_sgs(an))

bits = [1] * n
end = False
# print(Asgs)
# sys.exit()
last_bits = [2] * n

cnt = 0
while cnt < 5:
    for i in range(n):
        
        # i人目の意見の個数
        for j in range(len(Asgs[i])):
            # bitsには正直者と登録されている人があるひと(正直者として登録されている)を不親切というなら
            if bits[i] == 1 and Asgs[i][j][1] == 0 and bits[Asgs[i][j][0]-1] ==1:
                
                #発言者もしくは発言対象者が偽
                bits[i] = 0
                # print(i, j)
            # 正直者とされている人が不親切とされてる人を正直者と言っている場合,発言者は不親切である。
            if bits[i] == 1 and bits[Asgs[i][j][0]-1] == 0 and Asgs[i][j][1] == 1:
                bits[i] = 0
                # print('mj11')
            
    if last_bits == bits:
        cnt += 1
    last_bits = bits
        
# print(bits)
print(sum(bits))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n = int(input())
target_cache = defaultdict(list)
lier = 0

def calc(n):
  if n == 2:
    statements = []
    a1_count = int(input())
    if a1_count == 1:
      _, a1_content = input().split(" ")
      statements.append(a1_content)
    a2_count = int(input())
    if a2_count == 1:
      _, a2_content = input().split(" ")
      statements.append(a2_content)
    if a1_count == 0 or a2_count == 0:
      return 2
    else:
      if "1" in statements:
        return 0
      else:
        return 1
  for _ in range(n):
    statements_count = int(input())
    for _ in range(statements_count):
      target, content = input().split(" ")
      target_cache[target].append(content)
  for statements in target_cache.values():
    if "0" in statements and "1" in statements:
        n -= 1
  return n

print(calc(n))

Submission status: Wrong Answer

Solution code:
N = int(input())

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

ans = 0
for i in range(2 ** N):
    check = [-1] * N #1:正直者、0:不親切
    count = 0 #カウント用
    flag = True
    for j in range(N):
        if (i >> j) & 1: #正直者のとき
            if check[j] == 0: #矛盾しているとき
                flag = False
                break
            else:
                check[j] == 1

            # count += 1

            for x, y in lst[j]:
                if y == 1:
                    if check[x] != 0:
                        check[x] = 1
                    else: #矛盾しているとき
                        flag = False
                        break
                else: #y == 0
                    if check[x] != 1:
                        check[x] = 0
                    else:
                        flag = False
                        break
        else: #正直者でないとき
            if check[j] == 1:
                flag = False
                break
            else:
                check[j] = 0

        if flag == False:
            break
    if flag:
        tmp = 0
        for j in range(N):
            if (i >> j) & 1:
                tmp += 1
        # print (i)
        # print (check, flag)
        ans = max(ans, tmp)

print (ans)
# print (lst)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

def solve(i):
    memo = {}
    for j in range(N):
        for x, y in A[j].items():
            if i >> j & 1:
                if x in memo and memo[x] != y:
                    return False
                memo[x] = y
            else:
                if x in memo and memo[x] == y:
                    return False
                memo[x] = (1 - y)
    for x, y in memo.items():
        if i >> x & 1 and y != 1:
            return False
        if i >> x & 1 == 0 and y != 0:
            return False

    return True

ans = 0
for i in range(2 ** N):
    if solve(i):
        ans = max(ans, bin(i).count("1"))

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

for n in range(N):
    A = int(input())
    A_list.append(A)
    Group.append('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)

ans = 0
flag = False

for i in range(N):
    for a_list in range(A_list[i]):
            if y_list[i][a_list] == 1:
                if Group[i] != 'false' and Group[x_list[i][a_list]-1] != 'false':
                    Group[i] = 'true'
                    Group[x_list[i][a_list]-1] = 'true'
                elif Group[i] != 'true' and Group[x_list[i][a_list]-1] != 'true':
                    Group[i] = 'false'
                    Group[x_list[i][a_list]-1] = 'false'
                else:
                    flag = True
                    break
            if y_list[i][a_list] == 0:
                if Group[i] != 'true' and Group[x_list[i][a_list]-1] != 'false':
                    Group[i] = 'false'
                    Group[x_list[i][a_list]-1] = 'true'
                elif Group[i] != 'false' and Group[x_list[i][a_list]-1] != 'true':
                    Group[i] = 'true'
                    Group[x_list[i][a_list]-1] = 'false'                   
                else:
                    flag = True
                    break


if flag:
    print(0)
else:
    print(max(Group.count('true'), Group.count('false')))

Submission status: Wrong Answer

Solution code:
n=int(input())
xy=[]
for i in range(n):
    ai=int(input())
    xyi=[]
    for j in range(ai):
        xyj=list(map(int,input().split()))
        xyi.append(xyj)
    xy.append(xyi)
#print(xy)

ans=0
for i in range(2**n):
    person=[-1 for _ in range(n)]
    bit_i=format(i,'b').zfill(n)
    clear=True
    for j in range(n):

        if(person[j] == -1):
            person[j] = int(bit_i[j])
            if(int(bit_i[j]) == 0):
                continue
        elif(person[j] != int(bit_i[j])):
#            print("{0} {1} a".format(bit_i,person))
            clear=False
            break

        xyj=xy[j]
        for k in range(len(xyj)):
            if(person[xyj[k][0]-1] == -1):
                person[xyj[k][0]-1] = xyj[k][1]
            elif(person[xyj[k][0]-1] != xyj[k][1]):
#                print("{0} {1} b".format(bit_i,person))
                clear=False
                break

        if(not clear):
            break

    if(clear and (ans < person.count(1))):
#        print(bit_i)
#        print(person)
        ans = person.count(1)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
import itertools
TF = [0,1]
All = list(itertools.product(TF, repeat=N))
lis_A = [0]
lis_x = []
lis_y = []
ans = 0
for i in range(N):
  A = int(input())
  lis_A.append(A)
  for j in range(A):
    x,y = map(int,input().split())
    lis_x.append(x-1)
    lis_y.append(y)
for p in range(1,N+1):
  lis_A[p] = lis_A[p-1]+lis_A[p]
for k in range(len(All)):
  L = All[k]
  jud = True
  for g in range(N):
    if L[g] == 1:
      for q in range(lis_A[g],lis_A[g+1]):
        if L[lis_x[q]] != lis_y[q]:
          jud = False
          break
    else:
      for q in range(lis_A[g],lis_A[g+1]):
        if L[lis_x[q]] == lis_y[q]:
          jud = False
          break
  if jud:
    ans = max(sum(L),ans)
print(ans)

Submission status: Wrong Answer

Solution code:
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N=one_int()

dicts = {i+1:{}  for i in range(N)}
un_dicts={i+1:{}  for i in range(N)}
for i in range(1,N+1):
    num = one_int()
    bits = ["0" for k in range(N)]
    un_bits = ["1" for k in range(N)]
    
    bits[int(i-1)]="1"
    un_bits[int(i-1)]="0"

    
    for j in range(num):
        hito, singi = two_int()
        bits[hito-1] = str(singi)
        
        if singi==1:
            un_bits[hito-1] = str(0)
        else:
            un_bits[hito-1] = str(1)
    
    dicts[i] = "".join(bits)
    un_dicts[i] = "".join(un_bits)



users = [j+1 for j in range(N)]
max_n=0
# 信じる人のループ
for i in dicts:
    all_syougens=[]
    all_or = 0
    old=0
    flg=False
    #信じる人の証言取得
    syougen = list(map(int, list(dicts[i])))
    
    # 信じる人の証言を各人の証言に適応
    count = 0
    for u,s in zip(users,syougen):
        si = dicts[u]
        #信じる人がうそつきだといったら反転
        if s==0:
            si = un_dicts[u]
        
        if count!=0:
            temps = old^int(si,2)

            if temps !=0:
                old = old^int(si,2)
                flg=False
            else:
                flg=True
            all_or = all_or | old
            
        else:
            old = int(si,2)
            all_or = old
        count+=1
    
    if flg:
        old =  old^int(si,2)
    
    if old == 0:
        temp = bin(all_or)[2:].count("1")
        if temp >= max_n:
            max_n = temp
print(max_n)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
 
N=int(input())
box = [[] for i in range(N)]

chk=0
for i in range(N):
  Ai = int(input())
  for j in range(Ai):
    x,y=map(int,input().split())
    box[x-1].append(y)

lier=0
chk=0
for xi in box:
  l = len(xi)
  s = sum(xi)
  if l>0 and s==0:
    chk+=1
  if l>1 and l!=s:
    lier+=1
if chk==N:
  print(1)
else:
  print(N-lier)

Submission status: Wrong Answer

Solution code:
n = int(input())   #人の人数

b = []
c = []
d = []
ans = 0
for i in range(n):
    a = int(input()) #何段の証言になるか
    for l in range(a):
        x,y = list(map(int,input().split()))
        b.append(x)  #矛先
        c.append(y)  #審議
#print(b)
#print(c)
for o in range(n):
    ans = 0
    for m in range(len(b)):
        if b[m] == o+1:
            if c[m] == 1:
                ans += 1
            else:
                ans -= 1
    d.append(ans)
#print(d)
sorted(d)

if len(set(d)) == 1:
    if sum(d) == 0:
        print(0)
    else:
        print(1)
else:
    print(len(set(d)))

Submission status: Wrong Answer

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

ans = [False]*n
for i in range(n):
    for j in range(n):
        if s[i][j] == 1 and s[j][i] == 1:
            ans[i] = True

cnt = 0
if any(ans) == False:
    for i in range(n):
        for j in range(a):
            if s[i][j] == 0:
                cnt = 1
            else:
                cnt = 0
                break
    print(cnt)
else:
    for i in ans:
        if i == True:
            cnt += 1
    print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
mat = []
zero = []
for i in range(N):
    A = int(input())
    if A == 0:
        zero.append(i+1)
    tmp = [list(map(int,input().split())) for _ in range(A)]
    mat.append(tmp)
ans = N
num = list(range(1,N+1))
flag = [[[] for _ in range(2)] for _ in range(N)]
dic = dict(zip(num,flag))
count = 1
for i in mat:
    for j in range(len(i)):
        dic[i[j][0]][0].append(count)
        dic[i[j][0]][1].append(i[j][1])
    count += 1
tmp = list(dic.values())
pres = []
for i in range(len(tmp)):
    if tmp[i][0] == []:
        pres.append(i+1)
for i in range(len(pres)):
    for j in range(len(tmp)):
        for k in range(len(tmp[j][0])):
            if tmp[j][0][k] == pres[i] and tmp[j][1][k] == 0:
                tmp[j][1][k] = 1
                ans += -1
for i in range(len(tmp)):
    if 0 in tmp[i][1] and 1 in tmp[i][1] and i+1 not in zero:
        ans += -1
for i in range(len(tmp)):
    if 1 in tmp[i][1] or tmp[i][1] == []:
        break
    else:
        if i == len(tmp)-1:
            ans += -1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
xy=[]
for i in range(n):
    ai=int(input())
    xyi=[]
    for j in range(ai):
        xyj=list(map(int,input().split()))
        xyi.append(xyj)
    xy.append(xyi)
#print(xy)

ans=0
for i in range(2**n):
    person=[-1 for _ in range(n)]
    bit_i=format(i,'b').zfill(n)
    clear=True
    for j in range(n):

        if(person[j] == -1):
            person[j] = int(bit_i[j])
            if(int(bit_i[j]) == 0):
                continue
        elif(person[j] != int(bit_i[j])):
#            print("{0} {1} a".format(bit_i,person))
            clear=False
            break

        xyj=xy[j]
        for k in range(len(xyj)):
            if(person[xyj[k][0]-1] == -1):
                person[xyj[k][0]-1] = xyj[k][1]
            elif(person[xyj[k][0]-1] != xyj[k][1]):
#                print("{0} {1} b".format(bit_i,person))
                clear=False
                break

        if(not clear):
            break

    if(clear and (ans < list(person).count(1))):
#        print(bit_i)
#        print(person)
        ans = list(person).count(1)

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N = inputInt()
	xyS = []
	for i in range(N):
		A = inputInt()
		hito = [3 for i in range(N)]

		for j in range(A):
			x,y = inputMap()
			hito[x-1] = y

		xyS.append(hito)

	ans = 0
	flg = [0 for i in range(N)]
	flg_n = [0 for i in range(N)]
	for i, val in enumerate(xyS):
		for j, vol in enumerate(val):
			if vol == 3:
				continue
			flg[j] += vol
			if vol == 0:
				flg_n[j] += 1

	ans = 0
	ans2 = 0
	ans3 = 0
	for i in range(N):
		if flg[i] > flg_n[i]:
			ans += 1
		elif flg_n[i] > flg[i]:
			ans2 += 1
		elif flg_n[i] == flg[i]:
			ans3 += 1

	#print(flg)
	#print(flg_n)
	tmp = ans + int(-(-ans2 // 2))
	#print(ans3)
	if ans3 % 2 == 0:
		tmp += ans3 // 2
	print(tmp)



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
N = int(input())
import itertools
TF = [0,1]
All = list(itertools.product(TF, repeat=N))
lis_A = [0]
lis_x = []
lis_y = []
ans = 0
for i in range(N):
  A = int(input())
  lis_A.append(A)
  for j in range(A):
    x,y = map(int,input().split())
    lis_x.append(x-1)
    lis_y.append(y)
for p in range(1,N+1):
  lis_A[p] = lis_A[p-1]+lis_A[p]
for k in range(len(All)):
  L = All[k]
  jud = True
  for g in range(N):
    if L[g] == 1:
      for q in range(lis_A[g],lis_A[g+1]):
        if L[lis_x[q]] != lis_y[q]:
          jud = False
          continue
    else:
      for q in range(lis_A[g],lis_A[g+1]):
        if L[lis_x[q]] == lis_y[q]:
          jud = False
          continue
  if jud:
    ans = max(sum(L),ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
X=[[] for i in range(N)]
T=[]
ans=N
for i in range(N):
    A=int(input())
    for j in range(A):
        x,y=map(int,input().split())
        X[x-1].append(y)
        if y==0: T.append([i+1,x])
for s in X:
    sx=set(s)
    if len(s)==2:
        ans-=1

for t in T:
    if t[::-1] in T:
        ans-=0.5
print(int(ans))

Submission status: Wrong Answer

Solution code:
num = int(input())


temp2_list = []

for i in range(num):
    A = int(input())

    temp1_list = []
    for j in range(A):
        temp1_list.append([int(k) for k in input().split()])

    temp2_list.append(temp1_list)

right_agree = 0
ng_agree = 0
un_agree = 0
unknown = 0


temp4_list = []
for i in range(num):
    temp3_list = [-1] * num
    for k in range(len(temp2_list[i])):
        # print(temp2_list[i][k][0])
        temp3_list[temp2_list[i][k][0]-1] = temp2_list[i][k][1]
    temp4_list.append(temp3_list)

for i in range(num):
    for k in range(num):
        if i !=k:
            if temp4_list[i][k] == temp4_list[k][i] and temp4_list[i][k] == 1:
                right_agree += 1
            elif temp4_list[i][k] == temp4_list[k][i] and temp4_list[i][k] == 0:
                ng_agree += 1
            elif temp4_list[i][k] != temp4_list[k][i]:
                un_agree += 1
            else:
                unknown += 0

# print(right_agree, ng_agree, un_agree, unknown)
# print(temp4_list)

res1 = (right_agree - un_agree)//2
res2 = num - ng_agree//2 - (un_agree//2)//2

print(max(res1,res2))

Submission status: Wrong Answer

Solution code:
# ABC147c


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)

    n = int(input())
    x = []
    aa = []
    for _ in range(n):
        a = int(input())
        aa.append(a)
        x.append((a, [list(map(int, input().split())) for _ in range(a)]))

    x.sort(reverse=True)
    # map(int,input().split())
    tadasii = [None]*n

    # i番目の人を正直とするdfs
    def dfs(i, su):
        if tadasii[i] == None:
            return 1 - 10 ** 3
        tadasii[i] = True
        an = su
        for j in range(x[i][0]):
            if x[i][1][j][1] == 1:
                if tadasii[x[i][1][j][0]-1] == True:
                    continue
                if tadasii[x[i][1][j][0]-1] == None:
                    return 1 - 10 ** 3
                tadasii[x[i][1][j][0]-1] = True
                an = max(an, dfs(x[i][1][j][0] - 1, su + 1))
        for j in range(n):
            if tadasii[j] == None:
                tadasii[j] = True
                an = max(an, dfs(j, su + 1))
                tadasii[j] = None
        return an

    ans = 0
    for i in range(n):
        tadasii[i] = True
        ans = max(ans, dfs(i, 1))
        tadasii = [None]*n
    print(ans-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

ans = 0
for i in range(2 << (n-1)):
    bn = str(bin(i))[2:].zfill(n)
    cnt = 0
    for j in range(n):
        for x,y in people[j+1].items():
            if bn[x-1] != str(y):
                break
            if y == 0:
                continue
            for xx,yy in people[x].items():
                if bn[xx-1] != str(yy):
                    break
            else:
                continue
            break
        else :
            cnt += 1
    cnt = min(cnt, bn.count('1'))
    if cnt > ans:
        ans = cnt

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
Harray = []
for i in range(N):
    Aarray = []
    A = int(input())
    for j in range(A):
        xy = list(map(int,input().split()))
        Aarray.append(xy)
    Harray.append(Aarray)

carray = []

for Ai in Harray:
    honest = [Ai]
    for ans in Ai:
        que = []
        if ans[1] == 1:
            honest.append(Harray[ans[0]-1])
            que.append(ans[0]-1)
        while len(que) > 0:
            d = que[0]

            que.pop(0)
            
            e = 0
            for h in honest:
                for h2 in h:
                    if h2[1] == 1:
                        h3 = [h2[0], 0]
                    else:
                        h3 = [h2[0], 1]
                    if h3 in Harray[d]:
                        e = 1
                    if [Harray.index(h),0] in Harray[d]:
                        e = 1
            
            if e == 0:
                for ans2 in Harray[d]:
                    if (ans2[1] == 1) and (ans2 not in honest):
                        que.append(ans2[0]-1)
            else:
                honest = []
                break
                    
    carray.append(len(honest))

print(max(carray))

Submission status: Wrong Answer

Solution code:
N = int(input())

xys = []

for i in range(N):
    tmp_xy = []
    for j in range(int(input())):
        tmp_xy.append(tuple(map(int, input().split())))
    xys.append(tmp_xy)
        



status = [0 for _ in range(N)]

ans = 0

for i in range(2**N):
    tmp = format(i, 'b').zfill(N)

    
    for j in range(N):
        status[j] = int(tmp[-j-1])
    
    tmp_ans = 0
    isCorrect = True
    for j in range(N):
        if(status[j] == 1):
            for xy in xys[j]:

                if(status[xy[0]-1] != xy[1]):
                    isCorrect = False
                    break
                tmp_ans += 1
        if(not isCorrect):
            tmp_ans = 0
            break

    ans = max(ans, tmp_ans)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
mat = []
zero = []
for i in range(N):
    A = int(input())
    if A == 0:
        zero.append(i+1)
    tmp = [list(map(int,input().split())) for _ in range(A)]
    mat.append(tmp)
ans = N
num = list(range(1,N+1))
flag = [[[] for _ in range(2)] for _ in range(N)]
dic = dict(zip(num,flag))
count = 1
for i in mat:
    for j in range(len(i)):
        dic[i[j][0]][0].append(count)
        dic[i[j][0]][1].append(i[j][1])
    count += 1
tmp = list(dic.values())
pres = []
for i in range(len(tmp)):
    if tmp[i][0] == []:
        pres.append(i+1)
for i in range(len(pres)):
    for j in range(len(tmp)):
        for k in range(len(tmp[j][0])):
            if tmp[j][0][k] == pres[i] and tmp[j][1][k] == 0:
                tmp[j][1][k] = 1
                ans += -1
for i in range(len(tmp)):
    if 0 in tmp[i][1] and 1 in tmp[i][1]:
        ans += -1
for i in range(len(tmp)):
    if 1 in tmp[i][1] or tmp[i][1] == []:
        break
    else:
        if i == len(tmp)-1:
            ans += -1
print(ans+len(zero))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
ans=0

for i in range(n):
  _=int(input())
  dic={}
  for j in range(_):
    x,y=map(int,input().split())
    dic[x]=y
  a.append(dic.copy())
  

for i in range(2 ** n):#bit全探索
    b=[]
    for j in range(n):
      if i>>j & 1:
        b.append(j)
    summ=0
    jdg=[-1]*n
    for j in range(len(b)):
      jdg[b[j]]=1
      dic=a[b[j]]
      key=list(dic.keys())
      flg=0
      for k in range(len(key)):
        if jdg[key[k]-1]==-1:
          jdg[key[k]-1]=dic[key[k]]
        elif jdg[key[k]-1]==dic[key[k]]:
          jdg[key[k]-1]=dic[key[k]]
        else:
          flg=1
          break
      if flg==1:
        jdg=[-2]*n
        break
    
    sumi=0
    for j in range(len(jdg)):
      if jdg[j]==1:
        sumi+=1
    if sumi==len(b):
      summ=sumi
    ans=max(ans,summ)
print(ans)