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:
n=int(input())
a=[0]*n
xy=[]
for i in range(n):
    a[i]=int(input())
    hoge=[]*a[i]
    for j in range(a[i]):
        hoge.append(tuple(int(i) for i in input().split()))
    xy.append(hoge)
 
ans=0
def check(j,pattarn):
    if j in pattarn:
        for x,y in xy[j]:
            if not y and (x-1 in pattarn):
                return 0
            if y and (x-1 not in pattarn):
                return 0
        return 1
 
for bit in range(1<<n):
    pattarn = []
    for j in range(n):
        if (bit & (1<<j)):
            pattarn.append(j)
 
    for j in range(n):
        if check(j,pattarn)==0:
            break
    else:
        ans=max(ans,len(pattarn))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[0]*n
xy=[]
for i in range(n):
    a[i]=int(input())
    hoge=[]*a[i]
    for j in range(a[i]):
        hoge.append(tuple(int(i) for i in input().split()))
    xy.append(hoge)

ans=0
def check(j,pattarn):
    if j in pattarn:
        for x,y in xy[j]:
            if not y and (x-1 in pattarn):
                return 0
            if y and (x-1 not in pattarn):
                return 0
        return 1

for bit in range(1<<n):
    pattarn = []
    for j in range(n):
        if (bit & (1<<j)):
            pattarn.append(j)

    for j in range(n):
        if check(j,pattarn)==0:
            break
    else:
        ans=max(ans,len(pattarn))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
n=int(input())
XY=[]
ans=0
for i in range(n):
    a=int(input())
    B=[]
    for _ in range(a):
        x,y=map(int,input().split())
        B.append([x-1,y])
    XY.append(B)
seigo = list(product([1,0],repeat=n))
for i in range(2**n):
    kumiawase = seigo[i]
    ninzu = sum(kumiawase)
    flag=0
    for j in range(n):#j+1人目の発言検証
        if kumiawase[j]==1:#正直者パターン
            for a, b in XY[j]:
                if b==1:
                    if kumiawase[a]==1:
                        flag+=0
                    else:
                        flag=1
                else:
                    if kumiawase[a]==0:
                        flag+=0
                    else:
                        flag=1
    if flag==0:
        ans=max(ans,ninzu)
print(ans)

Submission status: Accepted

Solution code:
def main():

    # inputの取得
    N = int(input())
    X = []
    for i in range(N):
        tmp = []
        a = int(input())
        for _ in range(a):
            tmp.append(list(map(int,input().split())))
        X.append(tmp)


    cnt = 0
    
    # bit探索で候補をあげる
    for i in range(2**N):
        flag = 0
        c = ("0" * N + bin(i)[2:])[-N:]

        for j in range(N):
            if c[j] == "0":
                continue
            for k, l in X[j]:
                # 正直者な場合矛盾してないかチェック
                if not (l == int(c[k-1]) ):
                    # 矛盾してるのでフラグあげてbreak
                    flag = 1
                    break

        if flag == 1:
            continue
        cnt = max(cnt, c.count("1"))

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#1　正直
#0　不親切
#「不親切な人」を「常に嘘を付く」と誤解してしまった結果
#僕は無限にWAを生成することとなってしまいました。
#つらいンゴ…

#誤読には気をつけよう！（注意喚起）

import itertools
N=int(input())
B=[[] for i in range(N)]
for i in range(N):
    A=int(input())
    for j in range(A):
        x,y=map(int,input().split())
        B[i].append((x-1,y))
ans=0
#print(B)
for seq in itertools.product(range(2),repeat=N):
    flag=1
    for i in range(N):
        for r in B[i]:
            x,y=r
            if seq[i]==1 and seq[x]!=y:
                flag=0
                break
        if flag==0:
            break
    if flag==1:
        ans=max(ans,sum(seq))
print(ans)

Submission status: Accepted

Solution code:
#python3 
g=[[-1 for _ in range(15)] for _ in range(15)]
n=int(input())
for i in range(n):
  a=int(input())
  for _ in range(a):
    x,y=map(int, input().split())
    g[i][x-1]=y

ans=0
for i in range(1<<n):
  hy = [0 for _ in range(n)]
  for j in range(n):
    if (i>>j)&1:
      hy[j]=1

  ok = True 
  for j in range(n):
    if hy[j]==1:
      for k in range(n):
        if g[j][k] == -1: continue; 
        if g[j][k] != hy[k]: ok = False; 
  if ok:
    ans=max(ans, hy.count(1))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [0]*n
xy = [[] for _ in range(n)]
for i in range(n):
    a[i] = int(input())
    xy[i] = [[int(j) for j in input().split()] for _ in range(a[i])]
ans = 0

for i in range(0,2**n+1):
    cnt = 0
    for j in range(len(a)):
        if i>>j & 1 == 0:
            continue
        st = True
        for k in range(a[j]):
            if i>>(xy[j][k][0]-1) & 1 != xy[j][k][1]:
                st = False
        if st == False:
            break
        cnt += 1
    else:
        ans = max(ans, cnt)
            
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


def valid(honest, a):
    n = len(honest)
    for i in range(n):
        if honest[i]:
            for idx, is_honest in a[i]:
                if honest[idx] != is_honest:
                    return False
    return True

def count_bit(n):
    ret = 0
    while n > 0:
        if n % 2:
            ret += 1
        n //= 2
    return ret

def solve(n, a):
    ret = 0
    for status in range(1 << n):
        honest = [0] * n
        for j in range(n):
            if (1 << j) & status:
                honest[j] = 1
        if valid(honest, a):
            ret = max(ret, count_bit(status))
    print(ret)
    return ret

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
x=[]
for i in range(n):
    a=int(input())
    x.append([])
    for j in range(a):
        x[-1].append(list(map(int,input().split())))
ans=0
c=2**n-1
for i in range(2**n):
    c+=1
    strc=str(bin(c))[3:]
    yn="Yes"
    for j in range(n):
        if strc[j]=="1":
            cnt=0
            for k in range(len(x[j])):
                if strc[x[j][k][0]-1]!=str(x[j][k][1]):
                    yn="No"
                    break
                else:
                    cnt+=1
            if cnt!=len(x[j]):
                break
    if yn=="Yes":
        ans=max(ans,strc.count("1"))
print(ans)

Submission status: Accepted

Solution code:
def is_right(i):
  trueA =bin(i)[2:].zfill(N)
  for ii,flag in enumerate(trueA):
    if flag == '1':
      for x,y in A[ii]:
        if trueA[x] != str(y):
          return False
  return True

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

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

Submission status: Accepted

Solution code:
#!python3

def resolve():
    N = int(input().rstrip())
    A = []

    ok = dict()
    ng = dict()
    for i in range(N):
        a = []
        for j in range(int(input().rstrip())):
            x, y = map(int, input().rstrip().split())
            a.append((x, y))

        A.append(a)

    def cbit(n):
        i = 0
        while n:
            if n & 1:
                i += 1
            n >>= 1
        return i

    def check(i, t):
        for x, y in t:
            ii = i & (1 << (x-1))
            if y == 1:
                if ii == 0: return False
            else:
                if ii != 0: return False
        return True

    n = -1
    for i in range(2**N-1, -1, -1):
        n0 = cbit(i)
        if n0 <= n: continue

        for j in range(N):
            k = 1 << j
            if not i & k:
                continue
            if not check(i, A[j]):
                break
        else:
            n = n0
    print(n)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
N = int(input())

evidence = [[] for _ in range(N)]

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

ans = 0
for i in range(2**N):
  flag = 0
  for j in range(N):
    if ((i>>j) & 1 ):
      for x,y in evidence[j]:
        if (i>>x)&1 != y:
          flag = 1
          break
  if flag == 0:
    ans = max(ans, bin(i)[2:].count('1'))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
D = [[-1]*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())
        D[i][x-1] = y
ans = 0
for i in range(2**N):
    T = []
    n = i
    for j in range(N):
        T.append(n%2)
        n//=2
    res = 1
    for j in range(N):
        if T[j]==1:
            for k in range(N):
                if D[j][k]!=-1 and D[j][k]!=T[k]:res=0
    if res:ans = max(ans,T.count(1))
print(ans)

Submission status: Accepted

Solution code:
#python3 
g = [[-1 for _ in range(15)] for _ in range(15)]

n = int(input())
for i in range(n):
  m = int(input())
  for j in range(m):
    x,y = map(int, input().split())
    g[i][x-1] = y

ans = 0
for i in range(1<<n):
  honests = [0 for _ in range(n)]
  for j in range(n):
    if (i>>j) &1:
      honests[j] = 1 
  ok = True
  for j in range(n):
    if honests[j]:
      for k in range(n):
        if g[j][k] == -1: continue
        if g[j][k] != honests[k]: ok = False
  if ok:
    ans = max(ans, honests.count(1))

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
l=[0]*n
ans=0
for i in range(n):
  a.append(int(input()))
  l[i]=[list(map(int,input().split())) for i in range(a[-1])]
for i in range(2**n):
  i=format(i,'b').zfill(n)
  c=[]
  for j in range(n):
    if i[j]=='1':
      c.append(j)
  for j in c:#cは正直者と仮定した人のインデックスを格納してる
    for k in l[j]:#kは1人あたりの証言たちから1つずつ取り出す
      if k[1]==1 and (k[0]-1 not in c):
        break#正直者(仮)が「正直者だ！」って言った人が正直者候補にいない場合（この人が嘘ついてる）
      elif k[1]==0 and (k[0]-1 in c):
        break#正直者(仮)が「嘘つきだ！」って言った人が正直者候補にいる場合（この人が嘘ついてる）
    else:
      continue
    break
  else:#これらを切り抜けたらcはすべて正直者だと言える
    ans=max(ans,len(c))
print(ans)

Submission status: Accepted

Solution code:
import itertools

n = int(input())
array = []
for i in range(n):
    t = int(input())
    array.append([])
    for j in range(t):
        tmp = list(map(int, input().split(" ")))
        array[i].append(tmp)

allcombs = list(itertools.product([0, 1], repeat=n))
max_val = 0
for comb in allcombs:

    if sum(comb) <= max_val:
        continue

    tmp = []
    for i, j in enumerate(comb):
        if j == 1:
            tmp += array[i]
            
    if all([comb[t[0]-1]==t[1] for t in tmp]):
        max_val = max(max_val, sum(comb))

print(max_val)

Submission status: Accepted

Solution code:
#python3 
g = [[-1 for _ in range(15)] for _ in range(15)]

n = int(input())
for i in range(n):
  m = int(input())
  for j in range(m):
    x,y = map(int, input().split())
    g[i][x-1] = y

ans = 0
for i in range(1<<n):
  honests = [0 for _ in range(n)]
  for j in range(n):
    if (i>>j) &1:
      honests[j] = 1 
  ok = True
  for j in range(n):
    if honests[j]:
      for k in range(n):
        if g[j][k] == -1: continue
        if g[j][k] != honests[k]: ok = False
  if ok:
    ans = max(ans, bin(i).count('1'))

print(ans)

Submission status: Accepted

Solution code:
# 2**15=32000ちょいなのであらかじめ誰が正直者で誰がそうでないかのテーブルを作成し、それをもとにして探索。
# 矛盾がないことを探索していくような判定とデータ構造が浮かばん
# 正直者と、真偽不明の人、というのが味噌 嘘つきではない
# bit操作がわからんので配列でやった
# まじで判定とデータ構造どうすっかわからん

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


def f(n, cur=[]):
    # 1と0からなる長さNの組み合わせを全2**n個出すジェネレータ
    if len(cur) == n:
        yield cur
    else:
        for i in range(2):
            _next = cur[:]
            _next.append(i)
            yield from f(n, _next)


def check(arr):
    for i in range(n):
        if arr[i] == 0:
            continue
        for x, y in syougen[i]:
            if arr[x] == 1 and y == 0:
                return False
            if arr[x] == 0 and y == 1:
                return False
    return True


ans = 0
for g in f(n):
    if check(g):
        ans = max(ans, sum(g))
print(ans)

Submission status: Accepted

Solution code:
import itertools
n=int(input())
A=[[] for i in range(n)]
for i in range(n):
  r=int(input())
  for j in range(r):
    A[i].append(list(map(int,input().split())))
ans=0
L=list(itertools.product([0,1],repeat=n))
for i in L:
  T=[]
  for num,j in enumerate(i):
    if j==1:
      for k in A[num]:
        T.append(k)
  if all(i[j[0]-1]==j[1] for j in T):
    ans=max(ans,sum(i))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[0]*n
x=[[] for i in range(n)]
for i in range(n):
    a[i]=int(input())
    for j in range(a[i]):
        p,q=map(int,input().split())
        x[i].append([p,q])
ans1=0
for i in range(2**n):
    ans=False
    for j in range(n):
        if i>>j&1:
            for k in range(a[j]):
                if (i>>(x[j][k][0]-1)&1)!=x[j][k][1]:
                    ans=True
                    break
            if ans:
                break
    cnt=0
    if not ans:
        for j in range(n):
            cnt+=i>>j&1
    ans1=max(cnt,ans1)
print(ans1)

Submission status: Accepted

Solution code:
N=int(input())
A,X,Y=[],[],[]
for n in range(N):
    An=int(input())
    Xn,Yn=[],[]
    for a in range(An):
        x,y=map(int,input().split())
        Xn.append(x-1)
        Yn.append(y)
    A.append(An)
    X.append(Xn)
    Y.append(Yn)

max_count=0
for k in range(2**N):
    P=[int(_) for _ in bin(k)[2:].zfill(N)]
    ok=True
    for i in range(N):
        for j in range(A[i]):
            if P[i]==1 and P[X[i][j]]!=Y[i][j]:
                ok=False
    if ok:
        max_count=max(max_count,sum(P))
print(max_count)

Submission status: Accepted

Solution code:
import sys
N = int(input())
testmonies = [[-1] * N for _ in range(N)]
for i in range(N):
    for _ in range(int(input())):
        tmp = list(map(int, input().split()))
        testmonies[i][tmp[0]-1] = tmp[1]
ans = -1
for i in reversed(range(2 ** N)):
    for n in range(N):
        for j in range(N):
            if testmonies[j][n] == -1 or i >> j & 1 == 0:
                continue
            if testmonies[j][n] == i >> n & 1:
                continue
            else:
                break
        else:
            continue
        break
    else:
        tmp = bin(i).count('1')
        if tmp > ans:
            ans = tmp
print(ans)

Submission status: Accepted

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

num_max = 0
for pat in range(1<<N):
    cond = True
    num = 0
    for i in range(N):
        # i番目の人が正直者の場合
        if (pat>>i) & 1 == 1:
            if all(pat>>x & 1 == y for x, y in lst[i]):
                num += 1
            else:
                cond = False
                break
    if cond:
        num_max = max(num, num_max)

print(num_max)

Submission status: Accepted

Solution code:
n = int(input())
a = [[-1 for i in range(n)] for j in range(n)]
x = 0
max = 0
flag = 0
for i in range(n):
    x = int(input())
    for j in range(x):
        y,z = map(int, input().split())
        a[i][y-1] = z
for i in range(2**n):
    flag = 0
    for j in range(n):
        if (i >> j) & 1 == 1:
            for k in range(n):
                if a[j][k] != -1:
                    if a[j][k] != (i >> k) & 1:
                        flag = 1
                        break
            if flag == 1:
                break
    if flag == 1:
        continue
    elif j == n-1:
        count = 0
        for j in range(n):
            if (i >> j) & 1 == 1:
                count+=1
        if count > max:
            max = count
print(max)

Submission status: Accepted

Solution code:
N = int(input())
sg = [[-1 for i in range(N)] for j in range(N)]
for i in range(N):
  M = int(input())
  for j in range(M):
    x, y = map(int, input().split())
    sg[i][x-1] = y
X = 2**N
H = []
for i in range(X):
  L = []
  for j in range(N):
    L.append(i%2)
    i //= 2
  mj = 0
  for j in range(N):
    if L[j] == 1:
      for k in range(N):
        if j != k and (sg[j][k] == 0 and L[k] == 1 or sg[j][k] == 1 and L[k] == 0):
          mj += 1
          break
    if mj >= 1:
      break
  if mj >= 1:
    H.append(0)
  else:
    H.append(sum(L))
print(max(H))

Submission status: Accepted

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

for i in range(N):
    a = int(input())
    A[i] = a
    for j in range(a):
        x, y = map(int, input().split())
        X[i].append(x)
        Y[i].append(y)

def solve(N, A, X, Y, B):
    for n in range(N):
        if B[n] == 0:
            continue
        for a in range(A[n]):
            if B[X[n][a] - 1] != Y[n][a]:
                return False
    return True

max_pop = 0
B = [0] * N

for i in range(2**N):
    pop = 0
    found = True
    for j in range(N):
        b = (i >> j) & 1
        B[j] = b
        pop += b
    if max_pop < pop and solve(N, A, X, Y, B):
        max_pop = pop

print(max_pop)

Submission status: Accepted

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

for i in range(N):
    a = int(input())
    A[i] = a
    for j in range(a):
        x, y = map(int, input().split())
        X[i].append(x)
        Y[i].append(y)

# print(N, A, X, Y)

def solve(N, A, X, Y, B):
    for n in range(N):
        if B[n] == 0:
            continue
        for a in range(A[n]):
            if B[X[n][a] - 1] != Y[n][a]:
                return False
    return True

max_pop = 0

for i in range(2**N):
    B = [0] * N
    pop = 0
    found = True
    for j in range(N):
        b = (i >> j) & 1
        B[j] = b
        if b == 1:
            pop += 1
    if max_pop >= pop:
        continue
    if solve(N, A, X, Y, B):
        max_pop = pop

print(max_pop)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
def inputs():return [int(x) for x in input().split()]
shogen=[[None]*(N) for _ in range(N)]
for i in range(N):
    a=int(input())
    for j in range(a):
        x,y=inputs()
        shogen[i][x-1]=y
#print(shogen)
ans = -10**8
for bit in range(1,1<<N):
    #print(bit)
    ans1 = 0
    for i in range(N):
        if not bit&1<<i:
         # print(bit&1<<i,bit)
          continue
        for j in range(N):
            if shogen[i][j]==None:
                if j==N-1:
                    ans1+=1
                    #print(i,j,bit)
                continue
            elif shogen[i][j]==1 and bit&1<<j:
                if j==N-1:
                    ans1+=1
                continue
            elif shogen[i][j]==0 and not bit&1<<j:
                if j==N-1:
                    ans1+=1
                continue
            else:
                ans1=0
                break
        else:
            continue
        break
    ans = max(ans1,ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A=[]
B=[]

for i in range(N):
  cyc = int(input())
  A.append(cyc)
  B.append([])
  for t in range(cyc):
    Ar = list(map(int,input().split()))
    B[i].append(Ar)

rep_10 = 2**N
Ans=0
for i in range(rep_10):
  rep_2 = bin(i)
  mem_list = list(rep_2)
  del mem_list[0:2]
  mem_list = list(map(int,mem_list))
  while len(mem_list)<N:
    mem_list = [0]+mem_list

  for t in range(N):
    cnt=0
    if mem_list[t]==1:
      for s in range(A[t]):
        u = B[t][s][0] - 1
        if (mem_list[u])!=(B[t][s][1]):
          cnt+=1
    if cnt!=0:
      break
  if (cnt==0)and(Ans<sum(mem_list)):
    Ans=sum(mem_list)

print(Ans)

Submission status: Accepted

Solution code:
# ABC147C - HonestOrUnkind2
from itertools import combinations


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

    for cnt_honest in range(N, 0, -1):
        for honest_people in combinations(range(1, N + 1), cnt_honest):
            is_consistent = True
            for i in honest_people:
                for x, y in testimonies[i]:
                    if (x in honest_people and not y) or (x not in honest_people and y):
                        is_consistent = False
                        break
                if not is_consistent:
                    break
            if is_consistent:
                print(cnt_honest)
                return
    print(0)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC147C - HonestOrUnkind2
from itertools import combinations


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

    for cnt_honest in range(N, 0, -1):
        for honest_people in combinations(range(1, N + 1), cnt_honest):
            honest_people = set(honest_people)
            is_consistent = True
            for i in honest_people:
                for x, y in testimonies[i]:
                    if (x in honest_people and not y) or (x not in honest_people and y):
                        is_consistent = False
                        break
                if not is_consistent:
                    break
            if is_consistent:
                print(cnt_honest)
                return
    print(0)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC147C - HonestOrUnkind2
from itertools import combinations


def main():
    N = int(input())
    testimonies = {i: {} for i in range(1, N + 1)}
    for i in range(1, N + 1):
        A = int(input())
        for _ in range(A):
            x, y = map(int, input().split())
            testimonies[i][x] = y

    for cnt_honest in range(N, 0, -1):
        for honest_people in combinations(range(1, N + 1), cnt_honest):
            honest_people = set(honest_people)
            is_consistent = True
            for i in honest_people:
                for x, y in testimonies[i].items():
                    if (x in honest_people and not y) or (x not in honest_people and y):
                        is_consistent = False
                        break
                if not is_consistent:
                    break
            if is_consistent:
                print(cnt_honest)
                return
    print(0)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
Tlist = deque([])
for i in range(N):
    list = []
    n = int(input())
    if n != 0:
        for i in range(n): #因数注意！
            o = input()    
            m = o.split()
            p = [int(j) for j in m] #1列の数列をリスト化
            list.append(p)
    Tlist.append(list)
max = 0
for i in range(2**N):
    p = format(i,'0'+str(N)+'b')
    ALL = True
    for j, value in enumerate(p):
        if value == '0':
            pass
        else:
            if len(Tlist[j]) == 0:
                pass
            else:
                for k in Tlist[j]:
                    if p[k[0]-1] == str(k[1]):
                        pass
                    else:
                        ALL = False
            if ALL:
                pass
            else:
                break
    else:
        new = p.count('1')
        if new > max:
            max = new

print(max)

Submission status: Accepted

Solution code:
import sys
import itertools
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    xy = []
    for i in range(n):
        a = int(readline())
        for j in range(a):
            x, y = list(map(int, readline().split()))
            xy.append([i, x-1, y])
    ls = collections.deque([v for v in itertools.product([True, False], repeat=n)])
    for i, x, y in xy:
        for j in range(len(ls)):
            lsv = ls.pop()
            if not lsv[i] or lsv[x] == bool(y):
                ls.appendleft(lsv)
    t = 0
    for i in range(len(ls)):
        t = max(t, ls[i].count(True))
    print(t)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
import itertools
import copy


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    xy = []
    for i in range(n):
        a = int(readline())
        for j in range(a):
            x, y = list(map(int, readline().split()))
            xy.append([i, x-1, y])
    ls = [v for v in itertools.product([True, False], repeat=n)]
    for i, x, y in xy:
        tls = []
        for j in range(len(ls)):
            lsv = ls.pop()
            if not lsv[i] or lsv[x] == bool(y):
                tls.append(lsv)
        ls = copy.deepcopy(tls)
    t = 0
    for i in range(len(ls)):
        t = max(t, ls[i].count(True))
    print(t)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n = int(input())

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


ans = 0
for i in range(2 ** n):
    bag = 0
    ok = 0
    for j in range(n):
        if (i >> j) & 1:
            bag += 1
            for x,y in deps[j]:
                if (i >> x-1) & 1:
                    if y != 1:
                        ok = -1
                else:
                    if y == 1:
                        ok = -1
    if ok == 0:
        ans = max(ans,bag)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

ret = 0
for a in range(2 ** N):
    flg = True
    for i in range(N):
        if (a >> i & 1) == 1:
            for j in range(N):
                if ary[i][j] == -1:
                    continue
                if (a >> j & 1) != ary[i][j]:
                    flg = False
                    break

    if flg:
        n = sum([a >> i & 1 for i in range(N)])
        ret = max(ret, n)

print(ret)

Submission status: Accepted

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y


N=II()
DATA=[[] for i in range(N+1)]

for i in range(1, N+1):
    for _ in range(II()):
        DATA[i].append(LI())

res = 0
for FLGS in range(1 << N):
    ok = True
    for i in range(N):
        if (FLGS >> i) & 1:
            for j, k in DATA[i+1]:
                ok = ok and ((FLGS >> (j-1)) & 1) == k
                # print("j:{} FLGS >> (j-1):{} k:{}".format(j, FLGS >> (j-1), k))
    if ok:
        pos_res = 0
        for s in range(N): pos_res += (FLGS >> s) & 1
        res = max(res, pos_res)
        # print("{:015b}".format(FLGS))
print(res)

Submission status: Accepted

Solution code:
def main():
    N = int(input())

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

    ans = 0
    for i in range(2**N):
        truths = [1 if 0 < (i & 2**j) else 0 for j in range(N)]

        sts = True
        for j in range(N):
            if truths[j] == 1:
                for xy in xxyy[j]:
                    x, y = xy
                    if y == 0 and truths[x] == 1:
                        sts = False
                    if y == 1 and truths[x] == 0:
                        sts = False
        if sts:
            ans = max(ans, len(list(filter(lambda x: 0 < x, truths))))

    print(ans)


main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int()] * N
    x = [[] for i in range(N)]
    y = [[] for i in range(N)]
    for i in range(N):
        A[i] = int(input())
        for j in range(A[i]):
            xij, yij = map(int, input().split())
            x[i].append(xij - 1)
            y[i].append(yij)
    ans = 0
    for b in range(1 << N):
        flg = True
        for i in range(N):
            if not b & 1 << i:
                continue
            for j in range(A[i]):
                if 1 & b >> x[i][j] ^ y[i][j]:
                    flg = False
                    break
            if not flg:
                break
        if flg:
            ans = max(ans, bin(b)[2:].count("1"))
    print(ans)
    return


main()

Submission status: Accepted

Solution code:
N = int(input())
A_list = [[] for _ in range(N)]
for i in range(N):
    A = int(input())
    for a in range(A):
        x, y = map(int, input().split())
        A_list[i].append([x,y])
ans = 0
for i in range(1 << N):
    for j in range(N):
        wrong = False
        if 1 << j & i:
            prf = A_list[j]
            for p in prf:
                x, y = p
                if y == 0 and not (i & 1 << (x - 1)):
                    continue
                elif (i & 1 << (x - 1)) and y == 1:
                    continue
                else:
                    wrong = True
                    break

        if wrong:
            break
    if not wrong:
        cnt = 0
        for j in range(N):
            if 1 << j & i:
                cnt += 1
        ans = max(ans, cnt)
print(ans)