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: Accepted

Solution code:
import sys


def main():
    n = int(sys.stdin.readline().strip())
    a = []
    xy = [[] for _ in range(n)]
    for i in range(n):
        ai = (int(sys.stdin.readline().strip()))
        a.append(ai)
        for j in range(ai):
            xij, yij = [int(s) for s in sys.stdin.readline().strip().split()]
            xy[i].append((xij-1, yij))

    # n = 3
    # xy = [[(1, 1), (2, 0)], [(2, 1), (0, 0)], [(0, 1), (1, 0)]]
    # xy = [[(1, 1)], [(0, 1)], [(1, 0)]]

    # print(a)
    # for i in range(n):
    #     print(xy[i])

    def is_possible2(state):
        honests = set()
        unkinds = set()

        for i in range(n):
            if state[i]:
                honests.add(i)
            else:
                unkinds.add(i)

        for i in range(n):
            if state[i]:
                for j in range(len(xy[i])):
                    person, is_honest = xy[i][j]
                    if is_honest:
                        if person in unkinds:
                            return False
                        honests.add(person)
                    else:
                        if person in honests:
                            return False
                        unkinds.add(person)
        return True

    state = [0] * n

    def gen_and_calc(state, pos):
        if pos == n:
            if is_possible2(state):
                return sum(state)
            return 0
        cand = gen_and_calc(state, pos+1)
        state[pos] = 1
        cand2 = gen_and_calc(state, pos+1)
        state[pos] = 0
        return max(cand, cand2)

    print(gen_and_calc(state, 0))


main()

Submission status: Accepted

Solution code:
import copy
import math
N = int(input())
lis = []
for i in range(N):
    li = []
    A = int(input())
    for j in range(A):
        li.append(list(map(int, input().split())))

    lis.append(copy.deepcopy(li))
#print(lis)
mtrue = 0
def mjyun(a):
    flag = 0
    #print(a)
    for i in range(len(a)):
        if flag == 1:
            break
        b = a[i]
        #print(b)
        for j in range(len(lis[b])):
            #print(lis[b][j], a)
            if (lis[b][j][1]  == 1 and lis[b][j][0] - 1 not in a) or (lis[b][j][1] == 0 and lis[b][j][0] -1 in a):
                flag = 1
                break

    if flag == 0:
        return len(a)
    else:
        return 0
for i in range(2 ** N):
    #print("a", i)
    count = 0
    a = []
    for j in range(N):
        if i & (1 << j) != 0:
            a.append(int(math.log2(i & (1 << j))))

    num = mjyun(a)
    #print(num)
    if mtrue < num:
        mtrue = num
print(mtrue)

Submission status: Accepted

Solution code:
n=int(input())
xy=[[] for i in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        xy[i].append(list(map(int,input().split())))
        
ans=0
for i in range(2**n):
    flg=0
    bin_i=format(i, '0{}b'.format(n))
    zero_one=list(bin_i)
    for j in range(n):
        if zero_one[j]=="1":
            for k in xy[j]:
                x,y=k
                if zero_one[x-1]=="1" and y==0:
                    flg=1
                if zero_one[x-1]=="0" and y==1:
                    flg=1

    if flg==0:
        tmp=0
        for w in zero_one:
            if w=="1":
                tmp+=1
        ans=max(ans,tmp)

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

N = int(input())
xys = [
    [tuple(map(int, input().split())) for _ in range(int(input()))] for A in range(N)
]

# 大きい順に
for ans in range(N, -1, -1):
    # 組み合わせ
    for c in combinations(range(1, 1 + N), ans):
        honest = [False] * N
        for ci in c:
            honest[ci - 1] = True

        for i, xy in zip(range(1, 1 + N), xys):
            for x, y in xy:
                if y:
                    if honest[i - 1] and not honest[x - 1]:
                        break
                else:
                    if honest[i - 1] and honest[x - 1]:
                        break
            else:
                continue
            break
        else:
            break
        continue
    else:
        continue
    break

print(ans)

Submission status: Accepted

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

    xy = [list(map(int, input().split())) for _ in range(a)]
    XY.append(xy)

V = [False] * N
ans = 0
for i in range(1, 2**N):
    tmp_i = i
    isOK = True
    cnt = 0
    H = [False] * N
    for j in range(N):
        if tmp_i & 1 == 1:
            cnt += 1
            H[j] = True
        tmp_i = tmp_i >> 1
    for j in range(N):
        if H[j] == True:
            for k in range(A[j]):
                status = XY[j][k][1]
                if status != H[XY[j][k][0]-1]:
                    isOK = False
                    break
        if isOK == False:
            break
    if isOK == True:
        ans = max(cnt, ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())


q_li = []
for i in range(N):
    q = []
    for _ in range(int(input())):
        a, b = map(int,input().split())
        q.append((a,b)) 
    q_li.append(q)

def f(q_li, i):
    for n, q in enumerate(q_li):
        for a, b in q:
            a = a-1
            if (i >> n) & 1:
                if (i >> a) & 1 != b:
                    return 0
            #elif (i >> a) & 1 == b:
            #    return 0
    return str(bin(i)).count('1')

s_max = 0
for i in range(2 ** N):
    res = f(q_li, i)
    if res > s_max:
        s_max = res 
        
print(s_max)

Submission status: Accepted

Solution code:
import itertools
import copy
N = int(input())
dic = {}
ans = [1 for _ in range(N)]
trueans = 0
for i in range(N):
  a = int(input())
  dic[i] = []
  for _ in range(a):
    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
  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 = copy.deepcopy(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: Accepted

Solution code:
from itertools import combinations

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

person = [x for x in range(N)]

for h_num in reversed(range(N + 1)):
    for h_ppl in combinations(person, h_num):
        ppl = [0] * N
        for i in h_ppl:
            ppl[i] = 1

        consistency = True
        for i, testimony in enumerate(A):
            for t in testimony:
                if (ppl[i] == 1 and ppl[t[0]] != t[1]):
                    consistency &= False

        if consistency:
            print(h_num)
            exit(0)

Submission status: Accepted

Solution code:
import itertools
n = int(input())
maru = []
batu = []
for i in range(n):
    tmp_maru = []
    tmp_batu = []
    a = int(input())
    for i in range(a):
        x,y = map(int,input().split())
        if y == 0:
            tmp_batu.append(x)
        else:
            tmp_maru.append(x)
    maru.append(tmp_maru)
    batu.append(tmp_batu)
seq = (0,1)
list = []
for i in itertools.product(seq, repeat=n):
    list.append(i)
ans = 0
for i in list:
    tmp = [2 for i in range(n)]
    check = 0
    for j in range(n):
        if i[j] == 0:
            tmp[j] = 0
        else:
            tmp[j] = 1
    for j in range(n):
        if i[j] == 1:
            for k in maru[j]:
                if tmp[k-1] == 0:
                    check = 1
                    break
                else:
                    tmp[k-1] = 1
            for k in batu[j]:
                if tmp[k-1] == 1:
                    check = 1
                    break
                else:
                    tmp[k-1] = 0
    if check == 0:    
        x = i.count(1)
        if x > ans:
            ans = x
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from copy import copy

def chk(shoji, N, A, x, y):
    for chk in range(N):
        if shoji[chk]==0: continue
        for s in range(A[chk]):
            if ((y[chk][s]==1 and shoji[x[chk][s]-1]!=1) or 
                (y[chk][s]==0 and shoji[x[chk][s]-1]!=0)):
                return False
    return True

def solve(N: int, A: "List[int]", x: "List[int][int]", y: "List[int][int]"):
    fmt="0"+str(N)+"b"
    ans=0
    for kans in range(2**N):
        lst=list(format(kans,fmt))
        if chk([int(c) for c in lst], N, A, x, y):
            ans=max(ans, lst.count('1'))
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A=[0]*N
    x=[[0 for i in range(N)] for j in range(15)]
    y=[[0 for i in range(N)] for j in range(15)]
    for k in range(N):
        A[k] = int(next(tokens))
        for l in range(A[k]):
            x[k][l] = int(next(tokens))
            y[k][l] = int(next(tokens))
    solve(N, A, x, y)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
X = [[] for k in range(N)]
A = [0 for k in range(N)]

for k in range(N):
    A[k] = int(input())
    X[k] = [list(map(int, input().split())) for i in range(A[k])]
    

ans = [0]
for m in range(2**N)[::-1]:
    s = str(bin(m))[2:].zfill(N)
    li = list(s)
    li = [int(a) for a in li]
    chk = 1
    for k in range(N): # 証言を1人ぶんずつみていく
        if li[k] == 0: # 不親切の人の証言の場合
            pass
        elif A[k] == 0: # 証言していない場合
            pass
        else: # 正直者の人の証言だけ検証する
            for y in X[k]:
                if y[1] == li[y[0]-1]: #y[0]さんに関する仮定 ＝？ y[0]さんに関する証言
                    pass
                else: # 矛盾した
                    chk = 0
                        
    if chk == 1:
        ans.append(sum(li))
        break
    else:
        pass


print(max(ans))

Submission status: Accepted

Solution code:
N = int(input())
matrix = [[0 for i in range(N)] for j in range(N)]
for n in range(N):
    A = int(input())
    for a in range(A):
        array = [int(i) for i in input().split()]
        matrix[n][array[0]-1] = 1 if array[1] == 1 else -1
l = [True,False]
from itertools import product
for pattern in product(l,repeat=N):
    able = True
    for i,p in enumerate(pattern):
        if p:
            for a,b in zip(matrix[i],pattern):
                if (b==True and a==-1) or (b==False and a == 1):
                    able = False
                    break
            if able == False:
                break
        else:
            pass
    if able == True:
        break
print(sum(pattern))

Submission status: Accepted

Solution code:
n = int(input())
P = []

for i in range(n):
    A = int(input())
    p = []
    for j in range(A):
        x,y = map(int, input().split())
        p.append([x,y])
    P.append(p)

d = len(str(bin(2**n))[2:])-1

for i in range(2**n)[::-1]:
    S = str(bin(i))[2:].zfill(d)
    for j,s in enumerate(S):
        if s == '1':
            for q in P[j]:
                x,y = q
                if S[x-1] != str(y):
                    break
            else:
                continue
            break
    else:
        print(S.count('1'))
        exit()

Submission status: Accepted

Solution code:
from copy import deepcopy 
n = int(input())
list1 = [] #[i人目][人、真偽(0,1)]
ans = 0
for i in range(n):
    q = int(input())
    if q != 0:
        list1.append([list(map(int,input().split())) for j in range(q)])
    else:
        list1.append([])

bin_list = []
for i in range(2**n):
    bin_list = list(format(i, 'b').zfill(n))
    bin_list = [0 if i == "1" else 1 for i in bin_list]
    tf_list = deepcopy(bin_list)
    flag = 1
    #矛盾が生じなかった時点でTRUE(max)
    #正直者の話に矛盾が生じなければ良い。
    for j in range(n):
        if bin_list[j] == 1: #正直者の話だけ聞けば良い
            for person,tf in list1[j]: #person-1する必要あり
                if tf_list[person-1] != tf:
                    if tf_list[person-1] == -1:
                        tf_list[person-1] = tf
                    else:
                        flag = 0
                        break
        if not flag:break
    if flag: #flag立ったままならそれが正解
        print(sum(bin_list))
        exit()

Submission status: Accepted

Solution code:
import sys
from itertools import combinations as combi
input = sys.stdin.readline
N = int(input())
a = [[] for _ in range(N + 1)]
for i in range(1, N + 1):
  t = int(input())
  for _ in range(t):
    a[i].append(tuple(map(int, input().split())))
x = [i for i in range(1, N + 1)]
res = 0
#print(a)
for i in range(N + 1):
  for c in combi(x, i):
    #print(c)
    table = [0] * (N + 1)
    for p in c:
      table[p] = 1
    f = 0
    for p in c:
      #print(a[p])
      for q in a[p]:

        if table[q[0]] != q[1] and (table[q[0]] != -1):
          f = 1
          break
        table[q[0]] = q[1]
      if f: break
    for i in range(1, N + 1):
      if table[i] == 1:
        for q in a[i]:
          if table[q[0]] != q[1] and (table[q[0]] != -1):
            f = 1
            break
          table[q[0]] = q[1]

        if f: break
    if f == 0:
      res = max(res, len(c))
      #print(c, table)

print(res)

Submission status: Accepted

Solution code:
N=int(input())
A=[0]*N
L=[[[-1]*2 for i in range (15)] for j in range (N)]
C=[1]*N
c=2**N-1
H=0
for i in range(N):
    A[i]=int(input())
    for j in range(A[i]):
        L[i][j][0],L[i][j][1]=map(int,input().split())

for i in range(c,-1,-1):
    C=list(format(i, '015b'))
    f=0
    M=C[15-N:15]
    h=0
    for e in range(N):
        h+=int(M[e])
    if(H>=h):break
    for k in range(N):
        for l in range(15):
            if(int(M[k])==0):break
            if(L[k][l][0]==-1):break
            if((int(M[L[k][l][0]-1])) != int(L[k][l][1])):
                f=1
                break
        if(f==1):
            break
    if(f==0):
        H=h

print(H)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
L = [[] for _ in range(N)]

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

ans = 0
for s in range(1 << N):
    honest = 0
    D = defaultdict(list)
    for i in range(N):
        if s >> i & 1:
            honest += 1
            D[i].append(1)
            for x, y in L[i]:
                D[x].append(y)

    mujun = False
    for k, v in D.items():
        if len(set(v)) != 1:
            mujun = True
        if s >> k & 1:
            if v[0] == 0:
                mujun = True
        else:
            if v[0] == 1:
                mujun = True

    if not mujun:
        ans = max(ans, honest)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
B = [[] for i in range(N)]
C = []
for i in range(N):
  M = int(input())
  C.append(M)
  for j in range(M):
    B[i].append([int(s) for s in input().split()])

def check_val(val, digit):
  return (val%2**(digit+1))//(2**(digit))

count = 0
for i in range(2**N):
  A = []
  for j in range(N):
    A.append(check_val(i, j))
  A.reverse()
  flg = True
  for j, Ad in enumerate(A):
    if Ad == 1:
      for E, F in B[j]:
        if F != A[E-1]:
          flg = False
  if flg == True:
    count = sum(A)
print(count)

Submission status: Accepted

Solution code:
n = int(raw_input())
d ={}
for i in range(1,n+1):
    nt = int(raw_input())
    all_testemonies = []
    for ii in range(nt):
        testemony_inpt = raw_input().split(" ")
        
        x, y =int(testemony_inpt[0]), int(testemony_inpt[1])
        all_testemonies.append([x,y])
    d[i] =all_testemonies

def get_honest_shougens(state, d, for_target):
    shougens = []
    for i in range(len(state)):
        if i+1 == for_target: # skip shougens from target
            continue
        elif state[i] != 1: #only collect honest shougens
            continue
        else:
            current_shougens = d[i+1]
            for ii in current_shougens:
                if ii[0] == for_target:
                    shougens.append(ii)
    return shougens

def check_consistency(state, d):
    c = 0
    for i in range(len(state)):
        shougens = get_honest_shougens(state, d, i+1)
        if state[i] == 1:
            if [i+1, 0] in shougens:
                return False
            else:
                c+=1
        elif state[i] == 0:
            if [i+1,1] in shougens:
                return False
            else:
                c+=1
        else:
            print("strange state..", state[i])
    if c == len(state):
        return True
    else:
        return False

import itertools
combinations = list(itertools.product([0, 1], repeat=n))
highest = 0
for i in combinations:
    s = sum(i)
    if s == 0:
        continue # always consistent if everyone can lie
    else:
        c = check_consistency(i, d)
        if c:
            if s>highest:
                highest = s
print(highest)

Submission status: Accepted

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

count=0
while count < N:
    A = int(input())
    temp = []
    in_count = 0
    while in_count < A:
        l=list(map(int, input().split()))
        temp.append( l )
        in_count += 1
    evid.append(temp)
    count += 1

all_pattern = 2**N

max_num = 0
for pattern in range(all_pattern+1):
    break_flag = False
    for ii in range(N):
        person_evid = (pattern>>ii) & 1
        #print(pattern, ii, person_evid)
        for temp_evid in evid[ii]:
            if person_evid == 1 and (pattern>>(temp_evid[0]-1) ) & 1 != temp_evid[1]:
                break_flag = True
            #if person_evid == 0 and (pattern>>(temp_evid[0]-1) ) & 1 == temp_evid[1]:
            #    break_flag = True
            if break_flag:
                #print(pattern, ii, person_evid)
                break

        if break_flag:
            break
    if break_flag:
        continue
    num = 0
    for ii in range(N):
        num += (pattern>>ii) & 1
    if max_num < num:
        max_num = num
print(max_num)

Submission status: Accepted

Solution code:
n=int(input())
lists=[[] for _ in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        lists[i].append([x,y])
ans=0
for k in range(2**n):
    subans=0
    flag=True
    string=format(k,"0%ib"%n)
    listss=["unknown" for i in range(n)]
    for i in range(n):
        if string[i]=="1":
            #正直者だとした場合の全探索
            subans+=1
            for some in lists[i]:
                if listss[some[0]-1]=="unknown":
                    listss[some[0]-1]=some[1]
                elif listss[some[0]-1]!="unknown":
                    if listss[some[0]-1]!=some[1]:
                        flag=False
                        break

    if flag:
        flags=True
        for i in range(n):
            if  listss[i]!="unknown" and listss[i]!=int(string[i]):
                flags=False
        if flags:
            ans=max(ans,subans)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

import sys
input = sys.stdin.readline

testimony = {}

for n in range(1, N+1):
    A = int(input())
    testimony[n] = {}
    for _ in range(A):
        x, y = map(int, input().split())
        testimony[n][x] = y
#print(testimony)        

def dfs(idx, ans):
    #print(idx, ans)
    if not idx in testimony:
        ret = 0
        #print(ans)
        for a in ans:
            if a != 0:
                ret += 1
        return ret
    
    ans_true = ans[:]
    flag_true = True
    ans_false = ans[:]
    flag_false = True
    
    if ans[idx] == 0:
        flag_true = False
    else:
        ans_true[idx] = 1
        for k, v in testimony[idx].items():
            if ans_true[k] == 2 or ans_true[k] == v:
                ans_true[k] = v
            else:
                flag_true = False
                break
    if ans[idx] == 1:
        flag_false = False
    else:
        ans_false[idx] = 0
        #for k, v in testimony[idx].items():
        #    v = (v+1)%2
        #    if ans_false[k] == 2 or ans_false[k] == v:
        #        ans_false[k] = v
        #    else:
        #        flag_false = False
        #        break
            
    if flag_false and flag_true:
        a = dfs(idx+1, ans_true)
        b = dfs(idx+1, ans_false)
        return max(a, b)
    elif flag_false:
        return dfs(idx+1, ans_false)
    elif flag_true:
        return dfs(idx+1, ans_true)
    else:
        return 0
        
    
ans = dfs(1, [0]+[2]*N)
print(ans)

Submission status: Accepted

Solution code:


n=int(input())
mention_list = {}

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

max_count = 0
num = 2**n
flag = 0
for i in range(1,num):
    bina = bin(i)[2:].zfill(n)
    count = 0
    for x in range(n):
        j = int(bina[x])
        flag = 0
        if j == 1:
            for mention in mention_list[x]:
                if int(bina[mention[0]]) != int(mention[1]):
                    flag = -1
                    break
            if flag == -1:
                break
            count = count + 1
    if flag == -1:
        continue
    max_count = max(max_count, count )

print(max_count)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    xy = {i+1:[] for i in range(N)}
    
    for i in range(N):
        for j in range(int(input())):
            xy[i+1].append(tuple(map(int, input().split())))
            
    ans = 0
    nums = [2**i for i in range(N)]
    for i in range(1, 2**N):
        num = [idx+1 for idx, n in enumerate(nums) if i & n != 0]
        visited = [False] * (N+1)
        A = [None] * (N+1)
        
        f = True
        for i in num: A[i] = True
        
        while num:
            n = num.pop(0)
            if visited[n]: continue
            visited[n] = True
            
            for x, y in xy[n]:
                if A[x] is None: 
                    A[x] = y
                    if y and not visited[x]: num.append(x)
                    
                elif A[x] == y: continue
                else: f = False; break
            if not f: break
        if f: 
            ans = max(ans, sum([a for a in A if not a is None]))
            
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
syougen=[]
for i in range(N):
  A=int(input())
  X=[list(map(int,input().split())) for i in range(A)]
  syougen.append(X)

def search(l):
  global seigo,syougen,flg
  for x,y in l:
    if seigo[x-1]==100:
      seigo[x-1]=y
      if y==1:
        search(syougen[x-1])
    elif seigo[x-1]!=y:
      flg=False

ans=0
for i in range(N):
  flg=True
  seigo=[100]*N
  seigo[i]=1
  _ans=0
  search(syougen[i])
  if flg:
    if sum(seigo)>100:
      i=0
      while sum(seigo)>100:
        if seigo[i]==100:
          _seigo=seigo[:]
          flg=True
          seigo[i]=1
          search(syougen[i])
          if flg:
            pass
          else:
            seigo=_seigo[:]
            seigo[i]=0
        i+=1
        i%=N
    _ans=sum(seigo)%100
    if _ans>ans:
      ans=_ans
      maxseigo=seigo        
print(ans)

Submission status: Accepted

Solution code:
import sys
inputs = sys.stdin.readlines()

n = int(inputs[0])
A = []
B = []

i = 1
try:
    while True:
        a = int(inputs[i])
        A.append(a)
        B.append([tuple(map(int, inputs[j].split())) for j in range(i+1, i+a+1)])
        i += a+1        
except IndexError:
    pass

C = set()
for i in range(2 ** n):
    flag = True
    for j in range(n):
        if((i >> j) & 1):
            flag &= all((i >> (x-1)) & 1 == y for x, y in B[j])
    if flag:
        C.add(i)

print(max([sum([int(bit == '1') for bit in str(bin(c))]) for c in C]))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = []
    for i in range(N):
        a = int(input())
        h, d = 0, 0
        for _ in range(a):
            x, y = [int(i) for i in input().split()]
            if y == 1:
                h |= 1 << (x - 1)
            else:
                d |= 1 << (x - 1)
        A.append((i, h, d))
    
    m = 0
    for n in range(2 ** N):
        ch, cd = 0, 0
        mm = 0
        for i, h, d in A:
            if n & (1 << i):
                ch |= h | (1 << i)
                cd |= d
                if ch & cd:
                    break
                if cd & n:
                    break
                mm += 1
            elif ch & (1 << i):
                break
        else:
            if n == ch:
                m = max(m, mm)
    print(m)


main()

Submission status: Accepted

Solution code:
N = int(raw_input())

flag = False

Ai = []
xij = []
yij = []


for i in range(N):
    Ai_temp=int(raw_input())
    Ai.append(Ai_temp)
    x_temp = []
    y_temp = []
    for j in range(Ai_temp):
        x, y = map(int, raw_input().split())
        x_temp.append(x)
        y_temp.append(y)
    xij.append(x_temp)
    yij.append(y_temp)

ans_max = 0
for l in reversed(range(2**N)):
    flag = True
    for i in range(N):
        Ai_temp = Ai[i]
        if (l>>i)&0b1 == 1:
            for j in range(Ai_temp):
                xij_temp = xij[i][j]
                yij_temp = yij[i][j]
                if (l>>(xij_temp-1))&0b1 != yij_temp:
#                    print l, xij_temp, yij_temp                                                       
                    flag = False
                    break

        if flag == False:
            break

    if flag == True:
#        print "--"                                                                                    
#        print l                                                                                       
        ans = 0
        for i in bin(l)[2:]:
            ans = ans + int(i)
        if ans > ans_max:
            ans_max = ans

print ans_max

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
A = np.zeros((N,2,N), dtype=bool) # A = {([false],[true]),,}

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

upper = 0

def hantei(mask):
  for a in A[mask]:
    if np.any(mask[a[0]]): return False
    if not(np.all(mask[a[1]])): return False
  return True

seed = 1 << np.arange(N)

for i in range(2**N):
  mask = (seed & i).astype(bool)
  s = np.sum(mask)
  if s <= upper: continue
  if hantei(mask): upper = s

print(upper)

Submission status: Accepted

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


def main():
    N = int(input())
    H = [set() for _ in range(N)]
    U = [set() for _ in range(N)]
    for i in range(N):
        m = int(input())
        for j in range(m):
            x, y = map(int, input().split())
            if y == 1:
                H[i].add(x)
            else:
                U[i].add(x)

    ans = 0
    for i in range(1 << N):
#        print('bin: {:015b}'.format(i))
        h = set()
        u = set()
        for j in range(N):
            if ((i >> j) & 1) == 1:
                h.add(j+1)
            else:
                u.add(j+1)
        b = True
        for j in range(N):
            if ((i >> j) & 1) == 1:
                if H[j] & u:
                    b = False
                    break
                else:
                    h |= H[j]
                if U[j] & h:
                    b = False
                    break
                else:
                    u |= U[j]
        if b:
            ans = max(ans, bin(i).count("1"))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

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

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


result = 0
for i in range(2**N):
  state = bin(i)[2:]
  state = list('0' * (N - len(state)) + state)
  d = 1
  for i, tf in enumerate(state):
    if tf == '1':
      c = 1
      for j, a in enumerate(table[i]):
        if a == 1:
          if state[j] != '1':
            c = 0
            break
        elif a == 0:
          if state[j] != '0':
            c = 0
            break
      if c != 1:
        d = 0
        break
  if d == 1:
    result = max(result, state.count('1'))

print(result)

Submission status: Accepted

Solution code:
n = int(input())
x_arr = []
y_arr = []

for i in range(n):
  a = int(input())
  x = []
  y = []
  for j in range(a):
    tmp1,tmp2 = map(int,input().split())
    x.append(tmp1)
    y.append(tmp2)
    
  x_arr.append(x)
  y_arr.append(y)

ans = 0
for i in range(2 ** n):
  
  flag3 = True
  bin_str = format(i,'b').zfill(n)
  array = [-1] * (n+1)
  for k in range(len(bin_str)):
    if (array[k+1] != -1) and (int(bin_str[k]) != array[k+1]):
      flag3 = False
      break
    
    if bin_str[k] == '0':
      array[k+1] = 0
      continue
    else:
      array[k+1] = 1
      

    x = x_arr[k]
    y = y_arr[k]
    
    flag2 = True
    for j in range(len(x)):
      flag = True
      tmp1 = x[j]
      tmp2 = y[j]
      if array[tmp1] == -1:
        array[tmp1] = tmp2
      elif array[tmp1] != tmp2:
        flag = False
      else:
        pass
      
      if not flag:
        flag2 = False
        break
        
    if not flag2:
      flag3 = False
      break
    
  if not flag3:
    continue
    
  ans = max(ans, len(bin_str.replace('0','')))
    
print(ans)