Problem:


Score : 300 points

Problem Statement

There are N people numbered 1 to N. Each of them is either an honest person whose testimonies are always correct or an unkind person whose testimonies may be correct or not.

Person i gives A_i testimonies. The j-th testimony by Person i is represented by two integers x_{ij} and y_{ij}. If y_{ij} = 1, the testimony says Person x_{ij} is honest; if y_{ij} = 0, it says Person x_{ij} is unkind.

How many honest persons can be among those N people at most?

Constraints

All values in input are integers.

1 \leq N \leq 15

0 \leq A_i \leq N - 1

1 \leq x_{ij} \leq N

x_{ij} \neq i

x_{ij_1} \neq x_{ij_2} (j_1 \neq j_2)

y_{ij} = 0, 1

Input

Input is given from Standard Input in the following format:

N
A_1
x_{11} y_{11}
x_{12} y_{12}
:
x_{1A_1} y_{1A_1}
A_2
x_{21} y_{21}
x_{22} y_{22}
:
x_{2A_2} y_{2A_2}
:
A_N
x_{N1} y_{N1}
x_{N2} y_{N2}
:
x_{NA_N} y_{NA_N}

Output

Print the maximum possible number of honest persons among the N people.

Sample Input 1

3
1
2 1
1
1 1
1
2 0

Sample Output 1

2

If Person 1 and Person 2 are honest and Person 3 is unkind, we have two honest persons without inconsistencies, which is the maximum possible number of honest persons.

Sample Input 2

3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0

Sample Output 2

0

Assuming that one or more of them are honest immediately leads to a contradiction.

Sample Input 3

2
1
2 0
1
1 0

Sample Output 3

1



Sample input:
3
1
2 1
1
1 1
1
2 0


Sample output:
2

Submission status: Wrong Answer

Solution code:
N = int(input())
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,y])
M = 2**N-1
max = 0
for i in range(M,-1,-1):
    s = [0] * N
    k = bin(i)[2:]
    for i in range(len(k)):
        s[i] = k[i]
    c = 0
    state = 1
    for i in range(N):
        if int(s[i]) == 0:
            continue
        for b in B[i]:
            if int(s[b[0]-1]) != b[1]:
                state = 0
    if state == 1:
        for t in s:
            c += int(t)
    if max <= c:
        max = c
print(max)

Submission status: Wrong Answer

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 = [-1] * (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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = [i for i in range(N)]
XY = [[] for n in range(N)]
for n in range(N):
    A[n] = int(input())
    for a in range(A[n]):
        x, y = [int(x) for x in input().strip().split()]
        XY[n].append((x, y))
ans = 0
for n in range(N):
    #print('n = {}'.format(n))
    honest = [-1] * N
    f = True
    for nn in range(N):
        #print('nn = {}'.format(nn))
        if nn == n:
            continue
        xy = XY[nn][:]
        #print('  honest={}'.format(honest))
        for x, y in xy:
            if honest[x-1] == -1:
                honest[x-1] = y
            elif honest[x-1] != y:
                #print('xxxx')
                f = False
                break
        #print('  honest={}'.format(honest))
        if not f:
            break
    else:
        ans = max(ans, sum([1 for i in honest if i == 1]))
if N == 2 and ans == 0:
    print(1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

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

T = [-1]*N
ans = 0
for n in range(N):
    if T[n]!=-1: continue

    T[n] = 0
    queue = [n]
    m = [1,0]
    while queue:
        queue_new = []
        for q in queue:
            for e,x in E[q]:
                t = (T[q]+x)%2
                if T[e]==-1:
                    T[e] = t
                    m[T[e]]+=1
                    queue_new.append(e)
                elif T[e]!=t:
                    print(0)
                    exit()
        queue = queue_new
    ans += max(m)
print(ans)

Submission status: Wrong Answer

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

import itertools

def main():
    N = int(input())
    A= [] 
    XY = []
    for _ in range(N):
        a = int(input())
        A.append(a)
        xy = []
        if a == 0:
            XY.append([])
            continue
        for _ in range(a):
            xy.append(list(map(int,input().split())))
        XY.append(xy)

    bit_list = list(itertools.product([0, 1], repeat=N))

    answer = 0
    for b in bit_list:
        for i in range(N):
            for x,y in XY[i]:
                if b[i] == 1:
                    if b[x-1] == y:
                        continue
                    else:
                        break
                else:
                    if b[x-1] != y:
                        continue
                    else:
                        break
            else:
                continue
            break
        else:
            answer = max(sum(b),answer)
    
    print(answer)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
xy = [[] for i in range(n)]
for i in range(n):
    ai = int(input())
    a.append(ai)
    for j in range(ai):
        xyi = list(map(int, input().split()))
        xy[i].append(xyi)
res = 0
for i in range(n ** 2):
    flag = [(1 if i & 2 ** b == 2 ** b else 0) for b in range(n)]
    tres = 0
    outs = 0
    for j in range(n):
        if i & 2 ** j == 2 ** j:
            for k in range(a[j]):
                x, y = xy[j][k]
                x -= 1
                if flag[x] == -1 or flag[x] == y:
                    flag[x] = y
                else:
                    outs = 1
                    break
            if outs == 1:
                tres = 0
                break
            tres += 1
    res = max(tres, res)

print(res)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import itertools

N = int(input())
l = [0,1]
A_list = [0]*N
for i in range(N):
    A = int(input())
    A_list[i] = [list(map(int,input().split())) for _ in range(A)]
ans = 0

for s in itertools.product(l,repeat=N):
    flag = 0
    for i in range(N):
        if s[i] == 1:
            for a in A_list[i]:
                if a[1] == 1:
                    if s[a[0]-1] == 1:
                        pass
                    else:
                        flag = -1
                else:
                    if s[a[0]-1] == 0:
                        pass
                    else:
                        flag = -1
        else:
            for a in A_list[i]:
                if a[1] == 1:
                    if s[a[0]-1] == 0:
                        pass
                    else:
                        flag = -1
                else:
                    if s[a[0]-1] == 1:
                        pass
                    else:
                        flag = -1
    if flag == 0:
        ans = max(ans,s.count(1))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    ls = [[] for _ in range(n)]
    ls_a = []
    for i in range(n):
        a = int(input())
        ls_a.append(a)
        for _ in range(a):
            x,y = map(int,input().split())
            ls[i].append([x,y])
    ans =0
    for i in range(2**n):
        can = [0]*n
        for j in range(n):
            if (i >> j)&1:
                can[j] = 1
        flg = True
        for j in range(n):
            for k in range(ls_a[j]):
                now = ls[j][k]
                if can[j]==1:
                    if can[now[0]-1]==now[1]:
                        pass
                    else:
                        flg = False
                else:
                    if can[now[0]-1]!=now[1]:
                        pass
                    else:
                        flg =False
        if flg:
            ans = max(ans,sum(can))

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import product
N = int(input())
A = [[] for _ in range(N)]
for i in range(N):
    na = int(input())
    for j in range(na):
        x, y = map(int, input().split())
        A[i].append((x-1, y))
ans = 0
for pat in product((0, 1), repeat=N):
    num = pat.count(1)
    mujun = False
    for i, shogen in enumerate(A):
        for s in shogen:
            x, y = s
            if pat[x] != y ^ (1 - pat[i]):
                mujun = True
                break
        if mujun:
            break
    if mujun:
        continue
    ans = max(ans, num)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())

XY=[[] for _ 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 k in range(2**N):
  hu=list(map(int,bin(k)[2:].zfill(N)))
  j=0
  for i in range(len(XY)):
    if hu[i]==1:
      for x,y in XY[i]:
        if hu[x-1]!=y:
          j=1
    else:
      for x,y in XY[i]:
        if hu[x-1]==y:
          j=1
  if j==0:
    ans=max(ans,hu.count(1))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import product
#from collections import defaultdict
input = sys.stdin.readline
def main():
    N = int( input())
    A = [[0]*N for _ in range(N)]
    C = [0]*N
    for i in range(N):
        C[i] = int( input())
        for _ in range(C[i]):
            x, y = map( int, input().split())
            A[i][x-1] = -1+y*2
    ans = 0
    T = [-1, 1]
    for P in product( range(-1, 2, 2), repeat = N):
        check = True
        for i in range(N):
            for j in range(N):
                if A[i][j] == 0:
                    continue
                if A[i][j]*P[i] != P[j]:
                    check = False
                    break
        if check:
            if ans < (sum(P) + N)//2:
                ans = (sum(P) + N)//2
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
s=[[-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())
        s[i][x-1]=y
from itertools import product
r=0
for t in product((0,1),repeat=N):
    f=1
    for i in range(N):
        for j in range(N):
            if not ((t[i]==1 and s[i][j] in (t[j],-1)) or (t[i]==0 and s[i][j] in (t[j]^1,-1))):
                f=0
    if f==1:
        r=max(r,sum(t))
print(r)

Submission status: Wrong Answer

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

m = -1
for n in range(2**N):
    nn = n
    cur = [0] * N
    for i in range(N):
        cur[i] = nn % 2
        nn = nn // 2
    s = sum(cur)
    if s < m:
        break
    det = 1
    for i in range(N):
        if cur[i] == 0:
            continue
        for j in range(A[i]):
            if data[i][j][1] != cur[data[i][j][0]]:
                det = 0
                break
        if det == 0:
            break
    if det == 1:
        m = s
    #print(cur,s,det)

print(m)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = [None] * n
y = [None] * n
for i in range(n):
    a = int(input())
    x[i] = [0] * a
    y[i] = [0] * a
    for j in range(a):
        x[i][j], y[i][j] = map(int, input().split())
ans = 0
for i in range(2 ** n):
    a = [-1] * n
    cnt = 0
    for j in range(n):
        tmp = (i >> j) & 1
        cnt += tmp
        if tmp == 1:
            for p, q in zip(x[j], y[j]):
                a[p - 1] = q
    else:
        for j in range(n):
            tmp = (i >> j) & 1
            if a[j] != -1 and a[j] != tmp:
                break
        else:
            ans = max(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
dic = []
ls = [[] for i in range(N)]
for i in range(N):
  a = int(input())
  dic += [a]
  for j in range(a):
    x, y = map(int, input().split())
    ls[i] += [(x-1,y)]
ans = 0
for i in range(2**N):
  inf = []
  for j in range(N):
    if i%2==0:
      inf += [1]
    else:
      inf += [0]
    i >>= 1
  m = 0
  flag = False
  for j in range(N):
    for h in range(dic[j]):
      x, y = ls[j][h]
      if inf[j]==1:
        m += 1
        if inf[x]!=y:
          flag = True
          break
      else:
        if inf[x]==y:
          flag = True
          break
    if flag:
      break
  else:
    if ans<m:
      ans = m
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
h = [[] for _ in [0]*(n+1)]
not_h = [[] for _ in [0]*(n+1)]
for i in range(n):
  An = int(input())
  for j in range(An):
    x,y = map(int,input().split())
    if y == 1:
      h[i+1] += [x]
    if y == 0:
      not_h[i+1] += [x]    
      
cnt1 = 0
person = []
for i in range(1,n+1):
  for num_a in h[i]:
    if i in h[num_a]:
      cnt1 += 1
      if not i in person:
        person += [i]

        
cnt2 = 0
for i in range(1,n+1):
  for num_b in not_h[i]:
    if i in not_h[num_b] and not i in person:
      cnt2 += 1
      
print(cnt1+cnt2//2)

Submission status: Wrong Answer

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

ans = 0
for i in range(1<<N):
    h=[]
    for j in range(N):
        if(i&(1<<(j+1))):
            h.append(j)

    for j,x,y in T:
        if(j in h):
            if(not((x in h)==y)):
                break
    else:
        ans = max(ans,len(h))

print(ans)

Submission status: Wrong Answer

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

for i in range(N):
    A = int(input())
    temp = [i]
    for i in range(A):
        x, y = map(int, input().split())
        if y==1:
            temp.append(x-1)
    temp.sort()
    collect.append(temp)

ans = 0
for i in range(N):
    cand = collect[i]
    flag = True
    for j in cand:
        if not collect[j] == cand:
            flag = False
    if flag:
        ans = max(ans, len(cand))

print(ans)

Submission status: Wrong Answer

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

import itertools

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

    bit_list = list(itertools.product([0, 1], repeat=N))

    answer = 0
    for b in bit_list:
        for i in range(N):
            for x,y in XY[i]:
                if b[i] == 1:
                    if b[x-1] == y:
                        continue
                    else:
                        break
                else:
                    if b[x-1] != y:
                        continue
                    else:
                        break
            else:
                continue
            break
        else:
            answer = max(sum(b),answer)
    
    print(answer)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
evids = []
for _ in range(N):
    a = int(input())
    evids.append([list(map(int, input().split())) for _ in range(a)])

ans = 0
for pattern in range(2 ** N):
    p = pattern
    numHonest = 0
    correct = True
    for i in range(N):
        if p & 1:
            numHonest += 1
            for evid in evids[i]:
                if (pattern >> (evid[0]-1)) & 1 != evid[1]:
                    correct = False
                    break
        else:
            for evid in evids[i]:
                if (pattern >> (evid[0]-1)) & 1 == evid[1]:
                    correct = False
                    break
        if not correct:
            break
        p >>= 1
    if correct:
        ans = ans if ans > numHonest else numHonest
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = [None] * n
y = [None] * n
for i in range(n):
    a = int(input())
    x[i] = [0] * a
    y[i] = [0] * a
    for j in range(a):
        x[i][j], y[i][j] = map(int, input().split())
ans = 0
for i in range(2 ** n):
    a = [-1] * n
    cnt = 0
    for j in range(n):
        tmp = (i >> j) & 1
        cnt += tmp
        if a[j] != -1 and a[j] != tmp:
            break
        a[j] = tmp
        if tmp == 1:
            for p, q in zip(x[j], y[j]):
                a[p - 1] = q
    else:
        for j in range(n):
            tmp = (i >> j) & 1
            if a[j] != tmp:
                break
        else:
            ans = max(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
s=[[-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())
        s[i][x-1]=y
from itertools import product
r=0
for t in product((0,1),repeat=N):
    f=1
    for i in range(N):
        for j in range(N):
            if not (t[i]==1 and s[i][j] in (t[j],-1) or t[i]==0 and s[i][j] in (t[j]^1,-1)):
                f=0
    if f==1:
        r=max(r,sum(t))
print(r)

Submission status: Wrong Answer

Solution code:
import queue
import math
import copy
"""
N = int(input())
#S = input()
# (N,M) = (int(i) for i in input().split(" "))
# A = [int(i) for i in input().split()]
A = []
for i in range(N):
	A.append(int(input()))

print(A)

"""
P = 0
N = int(input())
ans = 0
mp =[]
for i in range(N):
	a = int(input())
	mp.append([])
	for j in range(a):
		(s,t) = (int(i) for i in input().split(" "))
		mp[-1].append([s-1,t])
#print(mp)
for P in range(1 << N):
	p_num = P
	pp = []
	for i in range(N):
		pp.append(p_num&1)
		p_num >>= 1
	p_len = sum(pp)
	##print(pp)
	ch = True
	for i in range(N):
		for info in mp[i]:
			if pp[i] != (pp[info[0]] == info[1])*1:
				ch = False
				break
	#print(ch)
	if ch and p_len > ans:
		ans = p_len
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N = I()
A = [0]*N
x = []
y = []
for i in range(N):
    A[i] = I()
    x0,y0 = Line(A[i],2)
    for j in range(len(x0)):
        x0[j] -= 1
    x.append(x0)
    y.append(y0)

ans = 0
from itertools import product
a = list(product([0,1],repeat=N))

for b in a:
    flag = True
    for i in range(N):
        if b[i]==1:
            for k in range(len(x[i])):
                if b[x[i][k]]!=y[i][k]:
                    flag=False
                    break
        else:
            for k in range(len(x[i])):
                if b[x[i][k]]==y[i][k]:
                    flag=False
                    break
    if flag:
        now = sum(b)
        if now>ans:
            ans = now
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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

ans = 0
for i in range(1<<n):
    # 正直者の数
    cnt = 0
    l = [i&(1<<j) for j in range(n)]
    f = True
    for j in range(n):
        if l[j]:
            if not all(G[j][k] == -1 or l[k] == G[j][k] for k in range(n)):
                f = False
                break
        else:
            if not all(G[j][k] == -1 or l[k] != G[j][k] for k in range(n)):
                f = False
                break
    if f:
        ans = max(ans, sum(l))

print(ans//2)

Submission status: Wrong Answer

Solution code:
N = int(input())

talk = [[-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())
        talk[i][x-1] = y

ans = 0

for i in range(1 << N):
    honest = []
    ansi = 0
    for j in range(N):
        if(1 << j and i):
            honest.append(1)
        else:
            honest.append(0)

    for j in range(N):
        flag = True
        for k in range(N):
            if(honest[k] != talk[j][k] and talk[j][k] != -1):
                flag = False

        if(flag):
            ansi += 1

    ans = max(ans, ansi)

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

# print(xy)
ans = 0
for i in range(2 ** n):
    h = [0] * n
    for j in range(n):
        if (i >> j) & 1:
            h[j] = 1

    f = True
    for j in range(n):
        for k in range(len(xy[j])):
            if xy[j][k][1] == 1:
                x = xy[j][k][0] - 1
                if (h[j] == 0 and h[x] == 1) or (h[j] == 1 and h[x] == 0):
                    f = False
                    break

            elif xy[j][k][1] == 0:
                x = xy[j][k][0] - 1
                if (h[j] == 0 and h[x] == 0) or (h[j] == 1 and h[x] == 1):
                    f = False
                    break

        if f == False:
            break

    if f:
        ans = max(ans, sum(h))

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
XY = []
for _ in range(N):
    a = int(sys.stdin.buffer.readline())
    xy = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(a)]
    XY.append([(x - 1, y) for x, y in xy])

ans = 0
for choice in itertools.product([0, 1], repeat=N):
    ok = True
    for i in range(N):
        # choice[i] == 1 のとき正直者
        for x, y in XY[i]:
            ok &= (choice[x] == y) == choice[i]
        if not ok:
            break
    if ok:
        ans = max(ans, sum(choice))
print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for i in range(n)]
    for i in range(n):
        a = I()
        for j in range(a):
            x,y = LI()
            x -= 1
            v[i].append((x,y))
    m = 1<<n
    ans = 0
    for b in range(m):
        f = [1 if b&(1<<i) else 0 for i in range(n)]
        for i in range(n):
            for x,y in v[i]:
                ny = (y==f[i])
                if f[x] != ny:
                    break
            else:
                continue
            break
        else:
            na = sum(f)
            if ans < na:
                ans = na
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
li = [np.full(n, -1, dtype=np.int) for _ in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        li[i][x-1] = y

ans = 0
for i in range(2**n):
    s = 0
    t = [0]*n
    for j in range(n):
        if i>>j & 1:
            t[j]=1
    is_contradict = 0
    for j in range(n):
        if t[j]:
            for k in range(n):
                if li[j][k]==-1:
                    continue
                if li[j][k] != t[k]:
                    is_contradict = 1
    if not is_contradict:
        ans = max(ans, sum(t))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
li = []
for i in range(n):
    a = int(input())
    p = np.full(n, -1, dtype=np.int)
    for j in range(a):
        x, y = map(int, input().split())
        p[x-1] = y
    li.append(p)

ans = 0
for i in range(2**n):
    s = 0
    t = [0]*n
    for j in range(n):
        if i>>j & 1:
            t[j]=1
    is_contradict = 0
    for j in range(n):
        if t[j]:
            for k in range(n):
                if li[j][k]==-1:
                    continue
                if li[j][k] != t[k]:
                    is_contradict = 1
    if not is_contradict:
        ans = max(ans, sum(t))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def digitSum(n):
    s = str(bin(n))
    s = s[2:]
    array = list(map(int, s))
    return sum(array)
N = int(input())
A = []
X = []
Y = []
res = 0
for i in range(N):
    a = int(input())
    A.append(a)
    X_temp = []
    Y_temp = []
    for j in range(a):
        x,y = map(int,input().split())
        X_temp.append(x)
        Y_temp.append(y)
    X.append(X_temp)
    Y.append(Y_temp)
for bit in range(1 << N):
    for i in range(1 << N):
        judge = True
        for j in range(N):
            if (i >> j) & 1:#もしAjが正直者だったら
                for k in range(A[j]):
                    if (i >> X[j][k]-1) & 1 != Y[j][k]:
                        judge = False
            else:
                for k in range(A[j]):
                    if (i >> X[j][k]-1) & 1 == Y[j][k]:
                        judge = False
        if judge:
            res = max(res,digitSum(i))
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
a = deque()
a_num = 0
b =deque()
c = deque()
for i in range(N):
  a_num = int(input())
  a.append(a_num)
  k,p=0,0
  x = [0]*N
  b_num=deque()
  for i in range(a_num):
    k,p = map(int,input().split())
    b_num.append(k-1)
    x[k-1]=p
  b.append(b_num)
  c.append(x)
max_num = 0   
for i in range(2**N):
  two = format(i,"015b")
  two = two[::-1]
  flag=True
  for i,k in enumerate(two):
    if i<N:
      if k =="1":
        for l in range(a[i]):
          for j in b[i]:
            #print(b[i],c[i][j],two[j])
            if c[i][j]!=int(two[j]):
              flag =False
              break
  if flag == True:
    #print(two)
    max_num = max(max_num,two.count("1"))  
print(max_num)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
a = deque()
a_num = 0
b =deque()
c = []
for i in range(N):
  a_num = int(input())
  a.append(a_num)
  k,p=0,0
  x = [0]*N
  b_num=deque()
  for i in range(a_num):
    k,p = map(int,input().split())
    b_num.append(k-1)
    x[k-1]=p
  b.append(b_num)
  c.append(x)
max_num = 0   
for i in range(2**N):
  two = format(i,"015b")
  two = two[::-1]
  flag=True
  for i,k in enumerate(two):
    if i<N:
      if k =="1":
        for l in range(a[i]):
          for j in b[i]:
            #print(b[i],c[i][j],two[j])
            if c[i][j]!=int(two[j]):
              flag =False
              break
  if flag == True:
    #print(two)
    max_num = max(max_num,two.count("1"))  
print(max_num)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools
n = int(input())
l = np.ones(n)
ixy = []
for i in range(n):
    a = int(input())
    for j in range(a):
        x,y = map(int, input().split())
        ixy.append([i,x-1,y])

ans = 0
ixy = np.array(ixy)
p = itertools.product([True,False], repeat=n)
for p_i in p:
    f = True
    for i,x,y in ixy:
        if not p_i[i]:
            continue
        else:
            if p_i[x] != y:
                f = False
    if f:
        ans = max(sum(p_i), ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
adjMat = [[-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())
        adjMat[i][x-1] = y
ans = 0
for i in range(1 << (n)):
    #print (bin(i))
    success = True
    for j in range(n):
        if i & 2**j:
            for k in range(n):
                if k == j:
                    continue
                if  i & 2**k == 0 and adjMat[j][k] == 1:
                    success = False
                if i & 2**k > 0 and adjMat[k][j] == 0:
                    success = False
                #print (j, k, adjMat[j][k], adjMat[k][j], success)
        if not success:
            break
    if success:
        i2 = i
        c = 0
        while i2 > 0:
            c += i2 & 1
            i2 //= 2
        ans = max(c, ans)
print (ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math





n= int(input())



xandy=np.ones((n,n))

xandy=xandy*(-1)

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

max=0


for l in range(0,2**n):
    i=2**n-1-l
    flag=1
    for j in range(0,n):
       
       #iを2進数表示した時kの位置ででの0-1が対応してあるか立っているか？
        if  bin( i& 2**j).count("1")>0:
             for k in range(0,n):
                  if  xandy[j][k]!=-1 and xandy[j][k]!=(i >> k)%2:
                      flag=0 
                      break
                       
        if flag==0:
            break
    if flag==1 and max<bin(i).count("1"):
         max=bin(i).count("1")

print(max)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math





n= int(input())



xandy=np.ones((n,n))

xandy=xandy*(-1)

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

max=0


for i in range(0,2**n):
    flag=1
    for j in range(0,n):
       
       #iを2進数表示した時kの位置ででの0-1が対応してあるか立っているか？
        if  bin( i& 2**j).count("1")>0:
             for k in range(0,n):
                  if  xandy[j][k]!=-1 and xandy[j][k]!=(i >> k)%2:
                      flag=0

    if flag==1 and max<bin(i).count("1"):
         max=bin(i).count("1")

print(max)