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

des = []

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



ans = 0

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

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

    flag = True

    # print(to_search)

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

        if tf == 0:
            if state[s-1] == 0 or state[s-1] == -1:
                state[s-1] = -1
                continue
            else:
                flag = False
                break

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

        if s-1 in ald:
            continue

        state[s-1] = 1

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


            to_search.append(sen)

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


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

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

n = int(input())
a = list(map(int, input().split()))

mod = 10**9+7

s = 0
p = itertools.combinations(a,2)
for v in p:
  s += v[0]^v[1]
  
print(s%mod)

Submission status: Wrong Answer

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

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

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

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

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

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

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

acc_list = [0]*N

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

Submission status: Wrong Answer

Solution code:
N = int(input())
remark = [0] * N
NGlist = [0] * N
grouplist = [0]*N
ans = 0
for i in range(N):
    remark[i] = [-1] * N
    NGlist[i] = [0] * N
    grouplist[i] = [0] * N


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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
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))

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)
    for j in range(N):
        if j == i: continue
        while dic[j]:
            xj,yj = dic[j].pop()
            if p[j] == 0:
                if yj == 1: yj = 0
                elif yj == 0: yj = 1
            if p[xj] == -1: p[xj] = yj
            elif p[xj] != yj:
                flg = False
                break
        if not flg:
            p = [0]
            break
    # print(p)
    ans.append(p.count(1))
print(sum(ans))

Submission status: Wrong Answer

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

    l.append(ll)
ans=0
for i in range(n):
    h={}
    h[i]=1
    ans1=1
    dame={}
    for x,y in l[i]:
        h[x]=1
        if y==0:
            dame[x]=1
    for j in range(n):
        if j in dame:
            continue
        if i==j:
            continue
        f=1
        for x,y in l[j]:
            if x in h:
                if y!=h[x]:
                    f=0
            if j in h:
                if x in h:
                    if y!=h[x]:
                        ans1=0
                        break
                if y==1:
                    h[x]=1

        if f:
            ans1+=1


    ans=max(ans,ans1)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
a_dict = {i : {0 : [i], 1:[]} for i in range(n)}
for i in range(n):
    a = int(sys.stdin.readline().strip())
    for j in range(a):
        x, y = [int(i) for i in sys.stdin.readline().split()]
        x -= 1
        if y == 1:
            a_dict[i][0].append(x)
        else:
            a_dict[i][1].append(x)
best = 0
for i in range(n):
    que = [i]
    true_set = set()
    false_set = set()
    already = set()
    while len(que) > 0 and len(already) < n:
        cur = que.pop(0)
        already.add(cur)
        t = set(a_dict[cur][0])
        f = set(a_dict[cur][1])
        if true_set.intersection(f) or false_set.intersection(t):
            true_set = {}
            break
        already.update(f)
        true_set.update(t)
        false_set.update(f)
        que += list(true_set.difference(already | set(que)))
    best = max(best, len(true_set))
print(best)

Submission status: Wrong Answer

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

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

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

    # check
    ans = 0
    for i in range(N):
        result = [None]*N
        queue = list(range(N))
        queue.remove(i)  
        result[i] = True
        for x,y in aa[i]:
            result[x] = y
        #print(result)
        canceled = False

        while len(queue) != 0:
            target = queue.pop()
            canceled = False
            #print(target)
            for x,y in aa[target]:
                if result[target] is None:
                    break
                if not result[target]:
                    y = not y
                if result[x] != y:
                    canceled = True
                    break
                result[x] = y
            if canceled:
                break

        if canceled:
            continue
        ans = max(ans, result.count(True))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
for u in range(n):
    a.append(0)

for i in range(n):
    an = int(input())

    for j in range(an):
        answer = list(map(int, input().split()))
        if answer[1] == 1:
            a[(answer[0] - 1)] += 1
        else:
            a[(answer[0] - 1)] += -n
count = 0
for i in a:
    if i >= 0:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
l ={}
m = 0
for i in range(n):
  no = int(input())
  for j in range(int(no)):
    r =input().split()
    x = int(r[0])
    y = int(r[1])
    if l.get(x) != y:
      if x in l:
        m +=1
    l[r[0]]=int(r[1])
print(m)

Submission status: Wrong Answer

Solution code:
n = int(input())
dmap = {}
for i in range(0, n):
    an = int(input())
    for j in range(0, an):
        x, y = input().split()
        x = int(x)
        if (x not in dmap):
            dmap[x] = ''
        dmap[x] += y
ans = 0
for i in range(0, n):
    if (i not in dmap):
        continue
    if ('0' not in dmap[i]):
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    persons = []
    person_len = int(input())
    for i in range(1, person_len + 1):
        q_len = int(input())
        questions = []
        for j in range(q_len):
            x, y = [int(x) for x in input().split()]
            questions.append((x - 1, y))
        persons.append(questions)

    patterns = []
    for n in range(2 ** person_len):
        pattern = []
        for i in range(person_len):
            pattern.append((n << i) & n != 0)
        patterns.append(pattern)

    for pp in reversed(patterns):
        try:
            for i in range(len(persons)):
                for q in persons[i]:
                    if pp[q[0]]:
                        if q[1] == 1 and not pp[i]:
                            raise Exception
                        elif q[1] == 0 and pp[i]:
                            raise Exception
                    else:
                        if q[1] == 1 and pp[i]:
                            raise Exception
                        elif q[1] == 0 and not pp[i]:
                            raise Exception

            print(len(list(filter(lambda x: x, pp))))
            return
        except:
            # print(pp, "error")
            pass
    print(0)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

import itertools

#判定配列用意
a=[]
for i in range(n):
  templi=[]
  for j in range(int(input())):
    x,y=map(int,input().split())
    templi.append([x,y])
  a.append(templi)

for i in itertools.product((0,1),repeat=n): #2のn乗通りの組み合わせ全て調査。
  temp=[-1]*n #n人について判定用配列作る。
  flag=1


  for j in range(n): #n人それぞれの証言を検証する。
    for k in a[j]: #jさんのk番目の証言について。
      x=k[0]-1
      y=k[1]

      #ここから先はjさんが正直か迷惑かでわかれる
      if i[j]==1: #もしjさんが正直なら…

        #まだ判定用配列に値がない場合
        if temp[x]==-1:
          temp[x]=y #このyの値をデフォルトとする。
        
        #判定用配列に既に値がある場合
        else:
          if temp[x]!=y: #先に入っている値と矛盾する場合は、このitertoolsループをスキップ
            flag=0
            break

      else: #jさんが迷惑な場合…

        #まだ判定用配列に値がない場合
        if temp[x]==-1:
          if y==1:
            temp[x]=0 #このyの値をデフォルトとする。
          else:
            temp[x]=1
        #判定用配列に既に値がある場合
        else:
          if temp[x]==y: #先に入っている発言と矛盾する場合は、このitertoolsループをスキップ(jさんが嘘つきな場合なので、数値一致するケースが矛盾。)
            flag=0
            break
  #発言の検証のあとは、itertoolsと判定用配列の矛盾を調査
  for j in range(n):
    if temp[j]!=-1:
      if i[j]!=temp[j]: #ここで矛盾の検査
        flag=0
        break
  if flag==1: #全て検証して矛盾がない場合は、答えを入れてあげよう。
    ansli.append(sum(i))
    #print(i)

print(max(ansli))

Submission status: Wrong Answer

Solution code:
N = int(input())
L = []
candidates = [list(bin(i)[2:].zfill(N)) for i in range(2**N - 1)]

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

ans = 0
for pattern in candidates:
    tmp = 0
    flag = 1
    for j in range(N): #pattern内全て
        if pattern[j] == "1":
            for said in L[j]:
                if pattern[said[0] - 1] != str(said[1]):
                    flag = 0
        else:
            pass
    if flag == 1:
        ans = max(ans, pattern.count("1"))

print(ans)

Submission status: Wrong Answer

Solution code:
import copy

N = int(input())
A = []
xy=[]
for i in range(N):
    A.append(int(input()))
    xy.append([])
    for j in range(A[-1]):
        xy[-1].append([int(x) for x in input().split()])

#print(xy)

tr = [[]]
for i in range(N):
    tr[0].append(-1)
#print(tr)
    
for i in range(len(xy)):
    for j in xy[i]:
        this_tr = []
        for k in tr:
            if j[1] == 1:
                if k[j[0]-1] != 0 and k[i] != 0:
                    #print("A")
                    this_k = copy.deepcopy(k)
                    this_k[j[0]-1] = 1
                    this_k[i] = 1
                    this_tr.append(this_k)
            else:
                if k[j[0]-1] != 1 and k[i] != 0:
                    #print("B")
                    this_k = copy.deepcopy(k)
                    this_k[j[0]-1] = 0
                    this_k[i] = 1
                    this_tr.append(this_k)
            if k[i] != 1:
                #print("C")
                this_k = copy.deepcopy(k)
                this_k[i] = 0
                this_tr.append(this_k)
        tr = copy.deepcopy(this_tr)
        #print(tr)
            
#print(tr)
max_c = 0
for i in tr:
    count = 0
    for j in i:
        if j == 1:
            count += 1
    max_c = max(max_c ,count)
print(max_c)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = [0] * N
for i in range(N):
    A = int(input())
    for j in range(A):
        B = list(map(int,input().split()))
        
        if B[1] == 0:
           S[B[0]-1] = 1 
if N%2 == 0 and A-sum(S) == 0:
    print(1)
else:
    print(N-sum(S))

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
xys = []
for k in range(n):
    a = int(input())
    xys.append([])
    for i in range(a):
        xy = list(map(int, input().split()))
        xy[0] -= 1
        if xy[1] == 0:
            xy[1] = -1
        xys[-1].append(xy)
        

best = 0
for l in range(n):
    hantei = [0 for _ in range(n)]
    hantei[l] = 1
#     xys = xys[1:] + [xys[0]]
    flag = 0
    que = [l]
    done = []
    while len(que) > 0:
        i = que[0]
        a = xys[i]
        done.append(i)
        que = que[1:]
#     for i, a in enumerate(xys):
        #print("---")
        #print("que", que)
        #print("han", hantei)
        #print("flag", flag)
        #print("a", a)
        for k, b in enumerate(a):
            if k not in done:
                que.append(k)
            #print("b", b)
            if hantei[b[0]] == 0:
                hantei[b[0]] = b[1]
                #print("hantei", hantei)
            else:
                if hantei[b[0]] == b[1]:
                    if hantei[i] == -1:
                        flag = -1
                else:
                    if hantei[i] == 1:
                        flag = -1
                        #print("i", i)
                        #print("bad")

    if flag == 0:
        if best < np.sum(np.array(hantei) == 1):
            best = np.sum(np.array(hantei) == 1)


print(best)

Submission status: Wrong Answer

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

ans = 0

for i in range(2**n):
    temp=0
    se=set()
    for idx,x,y in xy:
        if i>>(idx-1) & 1:
            if i>>(x-1) & 1:
                if y==1 and idx not in se:
                    temp+=1
                    se.add(idx)
                elif y==0:
                    break
            else:
                if y==0 and idx not in se:
                    temp+=1
                    se.add(idx)
                elif y==1:
                    break
            
        else:
            continue
    else:
        ans=max(ans,temp)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
d={}
for i in range(1,n):
  d[i]=1
for i in range(n):
  J = int(input())
  for j in range(J):
    x,s = map(int,input().split())
    if s==0:
      d[x]=0

result=0
for i in d:
  if d[i]==1:
    result=result+1
    
print(result)

Submission status: Wrong Answer

Solution code:
import sys

n = int(input())
c = [0 for _ in range(n)]

for i in range(n):
  a = int(input())
  for j in range(a):
    jump = 0
    x,y = map(int, input().split())
    if y == 1 :
      if c[i] != c[x-1] :
        if c[i] == 0 :
          c[i] = c[x-1]
          jump = 1
        elif c[x-1] == 0 :
          c[x-1] = c[i]
          jump = 1
        if jump == 0:
          print(0)
          sys.exit()
      if c[i] == 0 and c[x-1] == 0 :
        c[i] = 1
        c[x-1] = 1
    if y == 0 :
      if c[i] == c[x-1] :
        if c[i] == 0 or c[x-1] == 0 :
          c[i] = 1
          c[x-1] = -1
          jump = 1
        if jump == 0:
          print(0)
          sys.exit()
      if c[i] == 0 :
        c[i] = -1*c[x-1]
      elif c[x-1] == 0 :
        c[x-1] = -1*c[i]
      
print(max(c.count(1),c.count(-1)))

Submission status: Wrong Answer

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

ans = 0
for i in range(2**N):
    flag = False
    cnt = 0
    bit = bin(i)[2:].zfill(N)
    memo2 = [int(b) for b in bit]
    # print(i, ans)
    for ii, b in enumerate(memo2):
        cnt += b
        if b:
            for x, y in memo[ii]:
                if memo2[x] == y:
                    continue
                else:
                    flag = True
                    break
        else:
            for x, y in memo[ii]:
                if memo2[x] != y:
                    continue
                else:
                    flag = True
                    break
        if flag:
            break
    if flag:
        continue
    ans = max(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
remark = [0] * N
NGlist = [0] * N
grouplist = [0]*N
ans = 0
for i in range(N):
    remark[i] = [-1] * N
    NGlist[i] = [0] * N
    grouplist[i] = [0] * N


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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
true = set()
false = set()

for i in range(n):
  for j in range(int(input())):
    x,y = map(int,input().split())
    if y == 1:
      true.add(x)
    else:
      false.add(x)
if len(false) == n and len(true) == 0:
  print(1)
else:
  print(n-len(true&false))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    # S = input().rstrip()
    mS = [[] for _ in [0,]*(N+1)]
    for i in range(N):
        Ai = int(input())
        for j in range(Ai):
            x, y = map(int, input().split())
            mS[i+1].append((x,y))

    # T1, T2 = map(int,input().split())
    # A1, A2 = map(int,input().split())
    # B1, B2 = map(int,input().split())
    # vA = list(map(int, input().split()))

    res = 0
    # print(mS)
    M = 1<<N
    for m in range(M):
        vS = []
        vH = [-1]*(N+1)
        cnt = 0
        while m:
            if m&1:
                vS.extend(mS[cnt+1])
                vH[cnt+1] = 1
                cnt += 1
            m >>= 1
        
        ok_in_xy = True
        while vS:
            x,y = vS.pop()
            if vH[x] == -1:
                vH[x] = y
                if y:
                    vS.extend(mS[x])
            elif vH[x] != y:
                ok_in_xy = False
                break

        if ok_in_xy:
            res = max(res, cnt)

    print(res)


main()

Submission status: Wrong Answer

Solution code:

muzyun = 0
data = {}
num = int(input())
for i in range(num):
    words = int(input())
    for j in range(words):
        a, b = input().split(' ')
        if a not in data:
            data[a] = b
        elif data[a] != b:
            muzyun = muzyun + 1
        #print(str(i+1) + ' ' + str(words) + ' ' + a + ' ' + b)

uso = 0
for i in data:
    uso = uso + int(data[i])
if uso == 0:
    print(num - 1)
else:
    print(num - muzyun)

Submission status: Wrong Answer

Solution code:
N=int(input())
SyoMax=0
syo=[set() for i in range(N)]
hus=[set() for i in range(N)]
for i in range(N):
  A=int(input())
  for j in range(A):
    x,y=map(int, input().split())
    if y==0:
      hus[i].add(x)
    else:
      syo[i].add(x)
syoflag=[0]*N

for i in range(N):
  syotemp=set(syo[i])
  syozumi=set()
  hustemp=set(hus[i])
  husflag=0
  while len(syotemp^syozumi)>0:
    A=set(syotemp^syozumi)
    s=A.pop()
    
    syotemp|=set(syo[s-1])
    hustemp|=set(hus[s-1])
    syozumi.add(s)
    if len(syotemp&hustemp)>0:
      husflag=1
      break
  syoflag[i]=len(syotemp) 
  if (i+1) in syotemp:
    syoflag[i]-=1
  if husflag==1:
    syoflag[i]=-1
print(max(syoflag)+1)

Submission status: Wrong Answer

Solution code:
import itertools

N = int(input())
a = []
dic = {}
ans = [1 for _ in range(N)]
trueans = 0
for i in range(N):
  a.append(int(input()))
  dic[i] = []
  for j in range(a[-1]):
    x, y = input().split()
    dic[i].append((int(x),int(y)))

def check(dic, ans):
  for k, v in dic.items():
    for x, y in v:
      if ans[k]==1:
        if ans[x-1] != y:
          return False
      else:
        if ans[x-1] == y:
          return False
  return True

slist = []
for i in range(1, N+1):
  slist.append(i)
if check(dic, ans):
  print(N)
else:
  while(True):
    for i in range(1, N+1):
      tmp = list(itertools.combinations(slist,i))
      for t in tmp:
        anstmp = ans
        for t in t:
          anstmp[t-1] = 0
          flag = check(dic, anstmp)
          if flag:
            break
        if flag:
          break
      if flag:
        trueans = N - i
        break
    if flag:
      break
    break
  print(trueans)

Submission status: Wrong Answer

Solution code:
n = int(input())

a = []
xys = [[] for i in range(n)]

for j in range(n):
    a.append(int(input()))
    for i in range(a[j]):
        xys[j].append(list(map(int,input().split())))

p = [1 for i in range(n)]
for i in range(n):
    for j in range(a[i]):
        if ((xys[i])[j])[1] == 0:
            p[((xys[i])[j])[0] - 1] = 0

print(sum(p))

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = 0
T = []
F = []
for _ in range(N):
    A = int(input())

    for a in range(A):
        xy = list(map(int, input().split()))
        
        if xy[1] == 1:
            T.append(xy[0])
        else:
            F.append(xy[0])
T.sort()
F.sort()
# print(T)
# print(F)

if T == F:
    print(0)
elif len(T) == 0:
    print(len(F)-1)
else:
    print(len(T))

Submission status: Wrong Answer

Solution code:
N = int(input())
C = []

flg = False
for _ in range(N):
    a = int(input())
    comment = [[int(_) for _ in input().split()] for i in range(a)]
    if a:
        flg=True
    C.append(comment)
if not flg :
    print(N)
    exit()


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


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

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

        if flg: break

    if not flg:

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

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

Submission status: Wrong Answer

Solution code:
import sys
from itertools import islice
read = map(int, sys.stdin.read().split())

N = next(read)
candidates = [format(i, 'b').zfill(N) for i in range(2 ** N)]
A = [0] * N
xy = [[] for _ in range(N)]
for i in range(N):
    A[i] = next(read)
    xy[i].extend(list(islice(read, A[i] * 2)))

answer = 0

for candidate in candidates:
    tmp = 0
    truth = set()
    false = set()
    for k in range(N):
        if candidate[k] == '1':
            truth.add(k)
            for i, j in zip(*[iter(xy[k])] * 2):
                i -= 1
                if j == 1:
                    if i in false:
                        break
                    truth.add(i)
                else:
                    if i in truth:
                        break
                    false.add(i)
            else:
                continue
            break
        else:
            if k in truth:
                break
            false.add(k)
    else:
        if len(truth) > answer:
            answer = len(truth)

print(answer)

Submission status: Wrong Answer

Solution code:
import itertools

N = int(input())
a = []
dic = {}
ans = [1 for _ in range(N)]
trueans = 0
for i in range(N):
  a.append(int(input()))
  dic[i] = []
  for j in range(a[-1]):
    x, y = input().split()
    dic[i].append((int(x),int(y)))

def check(dic, ans):
  for k, v in dic.items():
    for x, y in v:
      if ans[k]==1:
        if ans[x-1] != y:
          return False
      else:
        if ans[x-1] == y:
          return False
  return True

slist = []
for i in range(1, N+1):
  slist.append(i)
if check(dic, ans):
  print(N)
else:
  while(True):
    for i in range(1, N+1):
      tmp = list(itertools.combinations(slist,i))
      print(tmp)
      for t in tmp:
        anstmp = ans
        for t in t:
          anstmp[t-1] = 0
          flag = check(dic, anstmp)
          if flag:
            break
        if flag:
          break
      if flag:
        trueans = N - i
        break
    if flag:
      break
    break
  print(trueans)

Submission status: Wrong Answer

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

ans = 0

for i in range(2**n):
    temp=0
    se=set()
    for idx,x,y in xy:
        if i>>(idx-1) & 1:
            if i>>(x-1) & 1:
                if y==1 and idx not in se:
                    temp+=1
                    se.add(idx)
                elif y==0:
                    break
            else:
                if y==0 and idx not in se:
                    temp+=1
                    se.add(idx)
                elif y==1:
                    break
            
        else:
            if i>>(x-1) & 1:
                if y==1:
                    break
                else:
                    continue
            else:
                if y==0:
                    break
    else:
        ans=max(ans,temp)
print(ans)

Submission status: Wrong Answer

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