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())
xy = []
for i in range(n):
    a = int(input())
    s = []
    for j in range(a):
        x, y = map(int, input().split())
        s.append([x, y])
    xy.append(s)

ans = 0
for bit in range(1, 2**n):
    flg = True
    # i人目の証言を検証する
    for i in range(n):
        if not flg:
            break

        # i人目が不親切の場合は検証する意味なし
        if not (bit >> i & 1):
            continue

        # i人目の各証言を確認
        for j in xy[i]:
            x = j[0]
            y = j[1]

            # 証言と矛盾していたらダメ
            if (bit >> (x - 1) & 1) ^ y:
                flg = False
                break
    if flg:
        ans = max(ans, bin(bit).count('1'))

print(ans)

Submission status: Accepted

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

ans = 0
for bit in range(1, 2**n):
    flg = True
    # i人目の証言を検証する
    for i in range(n):
        if not flg:
            break

        # i人目が不親切の場合は検証する意味なし
        if not (bit >> i & 1):
            continue

        # i人目の各証言を確認
        for j in xy[i]:
            x = j[0]
            y = j[1]

            # 証言と矛盾していたらダメ
            if (bit >> (x - 1) & 1) ^ y:
                flg = False
                break
    if flg:
        ans = max(ans, bin(bit).count('1'))

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
h=[]
xy=[[] for i in range(n)]
for i in range(n):
  a=int(input())
  h.append(a)
  xy[i]=[list(map(int,input().split())) for i in range(a)]
ans=0
for i in range(2**n):
  check=[0]*n
  for j in range(n):
    if (i>>j)&1:
      check[j]=1
  for j in range(n):
    if check[j]==1:
      for k in range(h[j]):
        if check[xy[j][k][0]-1]!=xy[j][k][1]:
          break
      else:
        continue
      break
  else:
    ans=max(ans,sum(check))
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(1 << N):
    ok = True
    cnt = 0
    for j in range(N):
        if (i >> j & 1) == 1:
            cnt += 1
    for j in range(N):
        if (i >> j & 1) == 1:
            for x, y in A[j]:
                if y == 0:
                    if (i >> x & 1) == 1:
                        ok = False
                elif y == 1:
                    if (i >> x & 1) == 0:
                        ok = False
    if ok:
        ans = max(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [0 for _ in range(N)]
x = []
y = []
for i in range(N):
    x_ = []
    y_ = []
    A[i] = int(input())
    for _ in range(A[i]):
        in1, in2 = list(map(int,input().split()))
        x_.append(in1 - 1)
        y_.append(in2)
    x.append(x_)
    y.append(y_)

def bit_all():
    ret = 0
    for p in range(2 ** N):
        temp = 0
        flag = 1
        b = str(format(p, '020b'))
        for i in range(N):
            if b[-(i + 1)] == "1":
                for j in range(A[i]):
                    if int(b[-(x[i][j] + 1)]) != y[i][j]:
                        flag = 0
                temp += 1
        if flag:
            ret = max(ret, temp)
    return ret

ans = bit_all()
print(ans)

Submission status: Accepted

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

ans = 0
for p in itertools.product((0, 1), repeat=N):
    flag = 1
    for i in range(N):
        if p[i] == 1:
            for x, y in ls[i]:
                x -= 1
                if p[x] != y:
                    flag = 0
    if flag == 1:
        ans = max(ans, sum(p))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
ans = 0
XY = [[] for i in range(N)]
for i in range(N):
  A = int(input())
  for j in range(A):
    XY[i].append(input())
for i in range(2**N):
  for j in range(N):
    if (i >> j) & 1:
      for xy in XY[j]:
        x, y = map(int, xy.split())
        x -= 1
        if (i >> x) & 1 != y:
          break
      else:
        continue
      break
  else:
    ans = max(ans, sum((i >> k) & 1 for k in range(N)))
    continue
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [] * N
xy = []
for _ in range(N):
    A.append(int(input()))
    xy.append([list(map(int, input().split())) for _ in range(A[-1]) ])

S = 0
for bit in range(2 ** N):
    s = 0
    T = True
    for i in range(N):
        if not T:
            break
        if (bit & (1 << i)):
            s += 1
            for x, y in xy[i]:
                x -= 1
                if y == 1 and (not (bit & (1 << x))):
                    T = False
                    break
                if y == 0 and (bit & (1 << x)):
                    T = False
                    break
    if T:
        S = max(S, s)

print(S)

Submission status: Accepted

Solution code:
N = int(input())
A = []
x = []
y = []
for i in range(N):
    A.append(int(input()))
    lx = []
    ly = []
    for j in range(A[i]):
        xx, yy = map(int, input().split())
        lx.append(xx-1)
        ly.append(yy)
    x.append(lx)
    y.append(ly)

m = -1
for pattern in range(2**N):
    p = format(pattern, '0'+str(N)+'b')[::-1]
    bl = True
    for i in range(N):
        if (pattern>>i)&1:
            for j in range(A[i]):
                if p[x[i][j]] != str(y[i][j]):
                    bl = False
    if bl:
        m = max(p.count('1'), m)

print(m)

Submission status: Accepted

Solution code:
n=int(input())
shoujiki=[[] for i in range(n)]
usotsuki=[[] 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:
			usotsuki[i].append(x-1)
		else:
			shoujiki[i].append(x-1)
ans = 0
for i in range(2**n):
	sl = []
	t = 0
	for j in range(n):
		if (i>>j) & 1:
			sl.append(1)
			t += 1
		else:
			sl.append(0)
	yes = 1
	for j in range(n):
		if sl[j] == 1:
			for k in shoujiki[j]:
				if sl[k] == 0:
					yes = 0
					break
			if yes == 0:
				break
			for k in usotsuki[j]:
				if sl[k] == 1:
					yes = 0
					break
			if yes == 0:
				break
	if yes == 1:
		ans = max(t, ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
import  math
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N=int(input())
mention=[[] for i in range(N+1)]
for i in range(N):
    a=int(input())
    for k in range(a):
        x,y=nm()
        mention[i+1].append((x,y))

ans=0
consistent=True
for i in range(2**N):
    consistent=True
    count=0
    for j in range(N):
        if((i>>j)&1):
            count+=1
            for k in range(len(mention[j+1])):    
                tmp=mention[j+1][k]
                if(tmp[1]!=((i>>(tmp[0]-1))&1)):
                        consistent=False

    if((consistent==True)):
        ans=max(ans,count)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=[]
for i in range(n):
  ll=[]
  for j in range(int(input())):
    ll.append(list(map(int,input().split())))
  l.append(ll)


def cobi(x):
  ret=0
  while True:
    if x==0:
      break
    ret+=x%2
    x=x//2
  return ret

def chbi(x,y,z):
  t=int((x&(2**y)))
  if z*(2**y)==t:
    return True
  else:
    return False

max_t=0

for i in range(2**n):
  f=0
  for j in range(n):
    if (2**j)&i:
      for k in l[j]:
        if not chbi(i,k[0]-1,k[1]):
          f=1
          break
      if f:
        break
  if f:
    continue
  max_t=max(max_t,cobi(i))
print(max_t)

Submission status: Accepted

Solution code:
n = int(input())
A = []
for i in range(n):
    a = int(input())
    tmp_A = [list(map(int,input().split())) for j in range(a)]
    A.append(tmp_A)

ans = 0
for bit in range(2**n): #2**nパターン考える
    flg = True
    cnt = 0
    for i in range(n):
        if (bit >> i) & 1: #i番目の人は正直者
            cnt += 1
            for j in A[i]: #i番目の人の証言を確認する
                x = j[0]-1
                y = j[1]
                if (bit >> x)&1 != y:
                    flg = False
                    break
        if not flg:
            break

    if flg:
        ans = max(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
claim = []
MAX = 0

for i in range(N):
    A = int(input())
    claim.append([input().split() for i in range(A)])

for i in range(2 ** N):
    people = [0 for i in range(N)]
    FLAG = True
    for j in range(N):  
        if ((i >> j) & 1):  
            people[j] = 1
    
    for k in range(len(claim)):
        if people[k] == 0:
            continue
        for l in range(len(claim[k])):
            if people[int(claim[k][l][0]) - 1] != int(claim[k][l][1]):
                FLAG = False
                break
    
    if FLAG:
        MAX = max(MAX, sum(people))

print(MAX)

Submission status: Accepted

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

#print(comment)
ans = 0

for k in range(1 << n):
    flag = True
    for i in range(n):
        for j in range(n):
            if k >> i & 1 == 0 or comment[i][j] == -1:
                continue
            else:
                if ((k >> j) & 1) != comment[i][j]:
                    flag = False
                    break

    #print("{} {}".format(k,flag))
    if flag:
        ans = max(ans,bin(k).count("1"))
print(ans)

Submission status: Accepted

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

res = 0
for i in range(1<<N):
  mapper = {1: [], 0: []}
  flg = True
  cnt = 0
  for j in range(N):
    if (i>>j)&1:
      cnt += 1
      for x,y in conditions[j]:
        if y==1 and not (i>>x)&1:
          flg = False
          break
        elif y==0 and (i>>x)&1:
          flg = False
          break
    if not flg: 
      break

  if flg:
    res = max(res, cnt)

print(res)

Submission status: Accepted

Solution code:
n = int(input())
xy = [[]for i in range(n)]
for i in range(n):
    ai = int(input())
    for j in range(ai):
        x,y = list(map(int,input().split()))
        xy[i].append([x-1,y])
ma = 0
for bit in range(2**n):
    bo = True
    for i in range(n):
        if bit >> i & 1:
            for x,y in xy[i]:
                if bit >> x & 1 != y:
                    bo = False
                    break
        if not bo:
            break
    if bo:
        count = bin(bit)[2:].count('1')
        ma = max(ma,count)
print(ma)

Submission status: Accepted

Solution code:
from collections import defaultdict
def main1():
    n = int(input())
    lis = [[] for _ in range(n)]
    for i in range(n):
        a = int(input())
        for j in range(a):
            lis[i].append(list(map(int, input().split())))
    res = 0

    for i in range(1<<n):
        f = True
        uso=set()
        syo=set()
        tmp=0
        for j in range(n):
            if(i&(1<<j)):
                tmp+=1
                for k in lis[j]:
                    if (i&(1<<(k[0]-1))) and k[1]==0:
                        f=False
                    if k[1]==1 and not (i&(1<<k[0]-1)):
                        f=False
        if f:
            res = max(res,tmp)
    print(res)


if __name__ == '__main__':
    main1()

Submission status: Accepted

Solution code:
n = int(input())
# graph = [[-1]*n]*n この初期化の仕方はよくない。すべてが同じ要素だと判断されて一個要素を変えるとすべてに反映される
graph = [[-1]*n for _ in range(n)]
for i in range(n):
  a = int(input())
  for _ in range(a):
    x, y = map(int, input().split())
    graph[i][x-1] = y
    
ans = 0
# n人が正直or不親切の場合を全探索
for i in range(2**n):
  honesty = [0]*n
  for j in range(n):
    if ((i >> j) & 1):
      honesty[j] = 1 # 0~n-1までの2進数表記

  ok = True # 矛盾しないかのフラッグok
  for j in range(n): # 一人ずつ証言と矛盾しないか確かめる
    if honesty[j]: # 正直の時は証言は確実でなければならない
      for k in range(n): # その人の他の人(自分も含める-1だから関係ないけど)への証言
        if graph[j][k] == -1: continue
        if graph[j][k] != honesty[k]: ok = False # 証言の有向グラフと仮定のhonestyが違ったらこれは矛盾している
  if ok: # 矛盾せずにここまでこれたbitの中でフラグが一番多いのが勝ち
    ans = max(ans, honesty.count(1))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

testimony = [[] for _ in range(n)]

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

ans = 0
for i in range(1 << n):
    flag = True

    for j in range(n):

        #if dishonest(=0), skip
        if (i >> j) & 1 == 0:
            continue

        for x, y in testimony[j]:
            if (i >> x) & 1 != y:
                flag = False

    if flag is True:
        ans = max(ans, bin(i).count("1"))

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())

testimony = defaultdict(list)

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

def beki(lst):
   res = [set()]
   for x in lst:
      res = res + [s | {x} for s in res]
   return res

res = 0
for s in beki(range(1, n+1)):
   flag = True
   d = {}
   for i in s:
      for x, y in testimony[i]:
         if x in d and d[x] != y:
            flag = False
         elif y == 1 and x not in s:
            flag = False
         elif y == 0 and x in s:
            flag = False
         else:
            d[x] = y
   if flag:
      res = max(res, len(s))
print(res)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
x=[[-1]*n for _ in range(n)]
y=[[-1]*n for _ in range(n)]
ans=0
for i in range(n):
  a.append(int(input()))
  for j in range(a[-1]):
    x[i][j],y[i][j]=map(int,input().split())
for i in range(2**n):
  for j in range(n):
    if (i>>j)&1:
      for k in range(a[j]):
        if not (i>>(x[j][k]-1))&1==y[j][k]:
          break
      else:
        continue
      break
  else:
    ans=max(ans,sum([(i>>j)&1 for j in range(n)]))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
#正直者を1で正直者じゃない人を0で表しbit表を作る
bit=[]
for i in range(2**n):
    b=[]
    for j in range(n):
        if (i>>j & 1):
            b.append(1)
        else:
            b.append(0)
    bit.append(b)
    
#データの入力
honest=[[] for i in range(n)]
for i in range(n):
  a=int(input())
  for j in range(a):
    x,y=list(map(int,input().split()))
    honest[i].append(x)
    honest[i].append(y)

ans=[]

#順番に全探索していく
for i in bit:
  flg=False
  for j in range(n):
    if i[j]==1:
      k=0
      while k<len(honest[j]):
        if i[honest[j][k]-1]!=honest[j][k+1]:
          flg=True
          break
        k=k+2
      if flg:
        break
    if flg:
      break
  if flg==False:
    ans.append(i.count(1))
  

print(max(ans))

Submission status: Accepted

Solution code:
n = int(input())

seq = [[0] * (n) for i in range(n)]

for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        if y:
            seq[i][x-1] = 1
        else:
            seq[i][x-1] = -1

ans = 0
for i in range(2 ** n):
    cnt = [0] * (n)
    for j in range(n):
        if (i >> j) & 1:
            cnt[j] = 1
    tot = True
    for k in range(n):
        if cnt[k]:
            for l in range(n):
                if seq[k][l] == 1 and not cnt[l]:
                    tot = False
                elif seq[k][l] == -1 and cnt[l]:
                    tot = False
    if tot:
        ans = max(ans, cnt.count(1))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

memo = [[] for _ in range(N)]
ans = 0

for i in range(N):
    A = int(input())
    for _ in range(A):
        #配列が0始まりなので、xは-1して使用する
        x, y = map(int, input().split())
        memo[i].append((x,y))

# print(memo)
for i in range(2**N):
    # print(i)#test
    flag = True
    for j in range(N):
        # bitが1の人の証言を確認していく。
        if i >> j & 1:
            for evidence in memo[j]:
                check_evidence = int(bin(i >> (evidence[0]-1))[-1])
                if check_evidence != evidence[1]:
                    # print(check_evidence==evidence[1])
                    flag = False
                    break
        if not flag:
            break
    if flag:
        bin_i = bin(i)
        ans = max(ans, bin_i.count("1"))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xy = [[]  for _ in range(n)]
ans = 0

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

for j in range(2 ** n):
    flag = True
    count = 0
    for k in range(n):
        if j >> k & 1 == 1:
            count += 1
            for x, y in xy[k]:
                if y == 0 and j >> x & 1 == 1: 
                    flag = False
                if y == 1 and j >> x & 1 == 0:
                    flag = False
    if flag == True:
        ans = max(count, ans)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xy = [[]  for _ in range(n)]
ans = 0

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

for j in range(2 ** n):
    flag = False
    count = 0
    for k in range(n):
        if j >> k & 1 == 1:
            count += 1
            for x, y in xy[k]:
                if y == 0 and j >> x & 1 == 1:
                    flag = True
                if y == 1 and j >> x & 1 == 0:
                    flag = True
    if flag == False:
        ans = max(count, ans)

print(ans)

Submission status: Accepted

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

    return honest_comments


def resolve():
    N = int(input())
    honest_comments = create_input(N)

    ans = 0
    for n in range(2**N):
        ss = [0] * N
        for i in range(N):
            if n & (1 << i) != 0:
                ss[i] = 1
        c = ss.count(1)
        if c <= ans:
            continue
        ok = True
        for i in range(N):
            s = ss[i]
            A, comment = honest_comments[i]
            for x, y in comment:
                if s == 1 and ss[x] != y:
                    ok = False
                    break
        if ok:
            ans = max(ans, c)
    print(ans)


resolve()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**5)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    n = gete(int)
    t = [[]]
    for _ in range(n):
        ret = []
        for _ in range(gete(int)):
            ret.append(tuple(geta(int)))
        t.append(ret)

    ans = 0
    for c in range(2**n):
        l = [0] * (n + 1)

        cur = 1
        tmp = c
        while tmp > 0:
            if tmp & 1 == 1:
                l[cur] = 1
            cur += 1
            tmp = tmp >> 1

        ok = True
        for i, h in enumerate(l):
            if h == 1:
                for tj in t[i]:
                    if tj[1] != l[tj[0]]:
                        ok = False
                        break
            if not ok:
                break

        if ok:
            ans = max(ans, sum(l))

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())

talk = []
for i in range(n):
    a = int(input())
    talk += [[list(map(int, input().split())) for _ in range(a)]]
    
ans = 0

for i in range(2**n):
    result = [True] * n
    
    for j in range(n):
        if ((i >> j) & 1):
            result[n-1-j] = False
    check = 1
    for k in range(n):
        for x, y in talk[k]:
            if result[k] == True:
                if result[x - 1] == y:
                    continue
                else:
                    check = 0
                    break
        else:
            continue
        break
    if check == 1:
        ans = max(ans, sum(result))
        
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
g = [[-1 for _ in range(N)] for _ in range(N)]
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):
    hornest = [0] * N
    for j in range(N):
        if (i >> j)&1:
            hornest[j] = 1
    is_ok = 1
    for j in range(N):
        if hornest[j] and is_ok:
            for k in range(N):
                if g[j][k] == -1:
                    continue
                if g[j][k] != hornest[k]:
                    is_ok = 0
    if is_ok:
        ans = max(ans,hornest.count(1))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
g = [[-1 for _ in range(N)] for _ in range(N)]
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):
    hornest = [0] * N
    for j in range(N):
        if (i >> j)&1:
            hornest[j] = 1
    is_ok = 1
    for j in range(N):
        if hornest[j] and is_ok:
            for k in range(N):
                if g[j][k] == -1:
                    continue
                if g[j][k] != hornest[k]:
                    is_ok = 0
    if is_ok:
        ans = max(ans,hornest.count(1))
        
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [0] * n
grid = [[-1 for _ in range(n)] for _ in range(n)]  # 証言を表す二次元配列
for i in range(n):
    a[i] = int(input())
    x = [0] * a[i]
    y = [0] * a[i]
    for j in range(a[i]):
        x[j], y[j] = map(int, input().split())
        grid[i][x[j] - 1] = y[j]
ans = 0
for i in range(1 << n):
    judge = [False] * n  # 誰を正直者としているか
    for j in range(n):
        if (i >> j) & 1:
            judge[j] = True
    is_ok = True  # 矛盾しているかどうか
    for j in range(n):
        if judge[j] and is_ok:
            for k in range(n):
                if grid[j][k] == -1:
                    continue
                if grid[j][k] != judge[k]:  # 矛盾
                    is_ok = False
    if is_ok:
        ans = max(ans, judge.count(True))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
g = [[-1 for _ in range(N)] for _ in range(N)]
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):
    hornest = [0] * N
    for j in range(N):
        if (i >> j)&1:
            hornest[j] = 1
    is_ok = 1
    for j in range(N):
        if hornest[j] and is_ok:
            for k in range(N):
                if g[j][k] == -1:
                    continue
                if g[j][k] != hornest[k]:
                    is_ok = 0
    if is_ok:
        ans = max(ans,hornest.count(1))
        
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A,B = [],[]
for i in range(N):
    n=int(input())
    A.append(n)
    for k in range(n):
        x,y = map(int,input().split())
        B.append([i,x,y])
ans = 0
for i in range(2**N):
    cnt = 0
    ok = True
    for j in range(N):
        #正直者を1にする
        if (i>>j) & 1:
            cnt += 1
            for k in range(len(B)):
                if B[k][0] != j:
                    continue
                else:
                    if ((i >> (B[k][1]-1)) & 1) and B[k][2] == 1:
                        continue
                    elif ((i >> (B[k][1]-1)) & 1 == 0) and B[k][2] == 0:
                        continue
                    else:
                        ok = False
                        break
    if ok:
        ans = max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
x=[[] for _ in range(n)]
y=[[] for _ in range(n)]
for i in range(n):
    m=int(input())
    a.append(m)
    for _ in range(m):
        xbuf,ybuf=map(int,input().split())
        x[i].append(xbuf)
        y[i].append(ybuf)
        
def bitsearch(b,n):
    for j in range(n):
        if ((b >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            for k in range(a[j]):
                if y[j][k]==1 and ((b >> x[j][k]-1)&1)==0:
                    return False
                if y[j][k]==0 and ((b >> x[j][k]-1)&1)==1:
                    return False
        else:
            continue
    return True
        
pmax=0
for i in range(2 ** n):
    #print(bitsearch(i,n))
    if bitsearch(i,n):
        t=0
        for j in range(n):
            if ((i >> j) & 1):
                t+=1
        if pmax<t:
            pmax=t
print(pmax)

Submission status: Accepted

Solution code:
import itertools
from functools import lru_cache

def main():
    n = int(input())
    a = [[] for _ in range(n)]
    for i in range(n):
        syougen_kosu = int(input())
        for __ in range(syougen_kosu):
            x, y = map(int, input().split())
            a[i].append((x-1,y))
    ans = [0]
    for x in itertools.product([-1,1], repeat=n):
        m = list(x)
        is_legal = True
        for i, v in enumerate(x):
            if v == -1:
                continue
            for j in a[i]:
                if j[1] == 1:
                    if m[j[0]] == -1:
                        is_legal = False
                        break
                    m[j[0]] = 1
                else:
                    if m[j[0]] == 1:
                        is_legal = False
                        break
                    m[j[0]] = -1
            if not is_legal:
                break
        if is_legal:
            ans.append(m.count(1))
    print(max(ans))
                
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
xy_l = [[] for i in range(n)]
cnt = 0
for i in range(n):
    a = int(input())
    for j in range(a):
        xy = list(map(int, input().split()))
        xy_l[i].append(xy)
# 　括りとして、x,yの組み合わせ、人ごとの証言の組み合わせでそれぞれ分ける
for k in range(1 << n):
    ev = [0]*n
    for l in range(n):
        if (k >> l) & 1:
            ev[l] = 1
    #         ここまでで仮定は完成
    f = True
    for p,q in enumerate(xy_l):  # 第一変数はindexで第二変数が要素
        if ev[p]:
            for r in q:  # xy_lの要素
                if r[1] != ev[r[0] - 1]:
                    f = False
    if f:
        cnt = max(cnt, ev.count(1))
 
print(cnt)

Submission status: Accepted

Solution code:

N=int(input())
xy =[[]for i in range(N)]
ans=0

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


for i in range(2**N):
    ans_kouho=0
    #発言に矛盾があればflag=-1,矛盾がなければflag=1
    flag=1
    #Torf[i]=1ならi+1人目は正直者、0なら不親切な人
    #注意、不親切な人＝「嘘つき」ではない（不親切な人でも正しいことを言うことがある）
    TorF=[0]*N
    for j in range(N):
        if (i>>j) & 1:
            TorF[j]=1

    for j in range(N):
        for k in range(len(xy[j])):
            
            if TorF[j]==1:#発言者が正直者ならば
                if TorF[xy[j][k][0]-1]!=xy[j][k][1]:
                    flag=-1
                    break
    
    if flag==1:
        
        ans_kouho=TorF.count(1)
        if(ans<ans_kouho):
            ans=ans_kouho   
    
               
print(ans)

Submission status: Accepted

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

c_max = 0
cnt = 0
for i in range(1 << N):
    ok = True
    for j in range(N):
        if (i >> j) & 1:
            for x, y in (xy[j]):
                if (i >> x) & 1 != y:
                    ok = False
                    break
        if not ok:
            break

    if ok:
        cnt = bin(i)[2:].count('1')
        if cnt > c_max:
            c_max = cnt

print(c_max)

Submission status: Accepted

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

result = 0
for i in range(2**n):
  flg = True
  for j in range(n):
    if (i>>j) & 1 == 0:
      continue
    for x,y in (xy[j]):
      if (i>>x) & 1 != y:
        flg = False
        break
    if not flg:
      break
  if flg:
    num_honest = bin(i)[2:].count('1')
    if result < num_honest:
      result = num_honest
print(result)

Submission status: Accepted

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

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

res = 0
for i in range(2**N):
    cnt = 0
    contra = False
    for j in range(N):
        if (i >> j) & 1 and contra == False: #正直者の時
            cnt += 1
            temp = xy[j]
            for x, y in temp:
                if (i >> x) & 1 != y:
                    contra = True
                    break
    if contra == False:
        res = max(res,cnt)
print(res)

Submission status: Accepted

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

for i in range(N):
    a = int(input())
    A.append(a)
    inter = []
    for x in range(a):
        xy = list(map(int,input().split()))
        inter.append(xy)
    XY.append(inter)
    #print(XY)

for i in range(2**N):
    pt = [0]*N
    ck = 1
    for j in range(N):
        if (i>>j)&1:
            pt[N-j-1]=1
    for k in range(N):
        if pt[k] ==1:
            for l in range(A[k]):
                if XY[k][l][1] != pt[XY[k][l][0] -1]: # 正直者と仮定した人の証言に矛盾がないかをチェック。正しいと向けられた人の証言が自分に返ってこないか。
                    ck = 0
    if ck == 1:
        honest_count.append(sum(pt))
print(max(honest_count))