Problem p03768 (python)

Fixed submission:
import numpy as np

def dp(v, d, c):
    if memo[v-1][d]:
        return

    memo[v-1][d] = True
    if d == 0:
        res[v-1] = str(c)
        return

    dp(v, d-1, c)
    for e in dic[v-1]:
        dp(e, d-1, c)


N, M = [int(e) for e in input().split(' ')]

dic = [[] for _ in range(N)]
memo = [[False]*11 for _ in range(N)]

for m in range(M):
    a, b = [int(e) for e in input().split(' ')]
    dic[a-1].append(b)
    dic[b-1].append(a)

Q = int(input())


vdc = [[int(e) for e in input().split(' ')] for _ in range(Q)]

res = ['0']*N

[dp(v, d, c) for v, d, c in vdc[::-1]]


print('\n'.join(res))

Buggy submission (verdict: Runtime Error):
import numpy as np
from numpy import linalg as LA
import math

mat_dic = {}

def f(mat, n):
    if mat_dic.get(n, None) is not None:
        return mat_dic.get(n, None)

    if n == 1:
        return mat

    if int(math.sqrt(n))**2 == n:
        return LA.matrix_power(f(mat, int(math.sqrt(n))), 2)

    return mat.dot(f(mat, n-1))



N, M = tuple(map(int, input().split(' ')))

mat = np.identity(N)
res = np.zeros(N)

for m in range(M):
    a, b = tuple(map(int, input().split(' ')))
    mat[a-1, b-1] = 1
    mat[b-1, a-1] = 1
    mat[a-1, a-1] = 1
    mat[b-1, b-1] = 1

Q = int(input())

for q in range(Q):
    v, d, c = tuple(map(int, input().split(' ')))
    x = f(mat, d)
    res[x[v-1,:] > 0] = c


for i in range(N):
    print(int(res[i]))

Buggy submission (verdict: Runtime Error):
import numpy as np
from numpy import linalg as LA
import math

mat_dic = {}

def f(mat, n):
    if mat_dic.get(n, None) is not None:
        return mat_dic.get(n, None)

    if n == 1:
        return mat

    if int(math.sqrt(n))**2 == n:
        return LA.matrix_power(f(mat, int(math.sqrt(n))), 2)

    return mat.dot(f(mat, n-1))



N, M = tuple(map(int, input().split(' ')))

mat = np.identity(N)
res = np.zeros(N)

for m in range(M):
    a, b = tuple(map(int, input().split(' ')))
    mat[a-1, b-1] = 1
    mat[b-1, a-1] = 1
    mat[a-1, a-1] = 1
    mat[b-1, b-1] = 1

Q = int(input())

for q in range(Q):
    v, d, c = tuple(map(int, input().split(' ')))
    x = f(mat, d)
    res[x[v-1,:] > 0] = c


for i in range(N):
    print(int(res[i]))

Buggy submission (verdict: Runtime Error):
import numpy as np
from numpy import linalg as LA

mat_dic = {}

def f(mat, n):
    if mat_dic.get(n, None) is not None:
        return mat_dic.get(n, None)

    if n == 1:
        return mat
    return mat.dot(f(mat, n-1))


N, M = tuple(map(int, input().split(' ')))

mat = np.identity(N)
res = np.zeros(N)

for m in range(M):
    a, b = tuple(map(int, input().split(' ')))
    mat[a-1, b-1] = 1
    mat[b-1, a-1] = 1
    mat[a-1, a-1] = 1
    mat[b-1, b-1] = 1

Q = int(input())

for q in range(Q):
    v, d, c = tuple(map(int, input().split(' ')))
    x = f(mat, d)
    res[x[v-1,:] > 0] = c


for i in range(N):
    print(int(res[i]))

Buggy submission (verdict: Runtime Error):
import numpy as np
from numpy import linalg as LA


N, M = tuple(map(int, input().split(' ')))

mat = np.identity(N)
res = np.zeros(N)

for m in range(M):
    a, b = tuple(map(int, input().split(' ')))
    mat[a-1, b-1] = 1
    mat[b-1, a-1] = 1
    mat[a-1, a-1] = 1
    mat[b-1, b-1] = 1

Q = int(input())

for q in range(Q):
    v, d, c = tuple(map(int, input().split(' ')))
    x = LA.matrix_power(mat, d)
    res[x[v-1,:] > 0] = c


for i in range(N):
    print(int(res[i]))

Buggy submission (verdict: Runtime Error):
import numpy as np
from numpy import linalg as LA


N, M = tuple(map(int, input().split(' ')))

mat = np.zeros((N, N))
res = np.zeros(N)

for m in range(M):
    a, b = tuple(map(int, input().split(' ')))
    mat[a-1, b-1] = 1
    mat[b-1, a-1] = 1
    mat[a-1, a-1] = 1
    mat[b-1, b-1] = 1


Q = int(input())

for q in range(Q):
    v, d, c = tuple(map(int, input().split(' ')))
    x = LA.matrix_power(mat, d)
    res[x[v-1,:] > 0] = c


for i in range(N):
    print(int(res[i]))

Buggy submission (verdict: Runtime Error):
import numpy as np
from numpy import linalg as LA


N, M = tuple(map(int, input().split(' ')))

mat = np.zeros((N, N))
res = np.zeros(N)

for m in range(M):
    a, b = tuple(map(int, input().split(' ')))
    mat[a-1, b-1] = 1
    mat[b-1, a-1] = 1
    mat[a-1, a-1] = 1
    mat[b-1, b-1] = 1


Q = int(input())

for q in range(Q):
    v, d, c = tuple(map(int, input().split(' ')))
    x = LA.matrix_power(mat, d)
    res[x[v-1,:] > 0] = c


for i in range(N):
    print(int(res[i]))