Problem:


Score : 700 points

Problem Statement

Squid loves painting vertices in graphs.

There is a simple undirected graph consisting of N vertices numbered 1 through N, and M edges.
Initially, all the vertices are painted in color 0. The i-th edge bidirectionally connects two vertices a_i and b_i. The length of every edge is 1.

Squid performed Q operations on this graph. In the i-th operation, he repaints all the vertices within a distance of d_i from vertex v_i, in color c_i.

Find the color of each vertex after the Q operations.

Constraints

1 ≤ N,M,Q ≤ 10^5

1 ≤ a_i,b_i,v_i ≤ N

a_i ≠ b_i

0 ≤ d_i ≤ 10

1 ≤ c_i ≤10^5

d_i and c_i are all integers.

There are no self-loops or multiple edges in the given graph.

Partial Score

200 points will be awarded for passing the testset satisfying 1 ≤ N,M,Q ≤ 2{,}000.

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
:
a_{M} b_{M}
Q
v_1 d_1 c_1
:
v_{Q} d_{Q} c_{Q}

Output

Print the answer in N lines.
In the i-th line, print the color of vertex i after the Q operations.

Sample Input 1

7 7
1 2
1 3
1 4
4 5
5 6
5 7
2 3
2
6 1 1
1 2 2

Sample Output 1

2
2
2
2
2
1
0

Initially, each vertex is painted in color 0.
In the first operation, vertices 5 and 6 are repainted in color 1.
In the second operation, vertices 1, 2, 3, 4 and 5 are repainted in color 2.

Sample Input 2

14 10
1 4
5 7
7 11
4 10
14 7
14 3
6 14
8 11
5 13
8 3
8
8 6 2
9 7 85
6 9 3
6 7 5
10 3 1
12 9 4
9 6 6
8 2 3

Sample Output 2

1
0
3
1
5
5
3
3
6
1
3
4
5
3

The given graph may not be connected.



Sample input:
7 7
1 2
1 3
1 4
4 5
5 6
5 7
2 3
2
6 1 1
1 2 2


Sample output:
2
2
2
2
2
1
0

Submission status: Wrong Answer

Solution code:
import collections
N,M = map(int, input().split())

nodes = [[] for i in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    nodes[a-1].append(b-1)
    nodes[b-1].append(a-1)


shots = []
Q = int(input())
for i in range(Q):
    v,d,c = map(int, input().split())
    shots.append((v-1, d, c))
colors = [0 for i in range(N)]
sizes = [-1 for i in range(N)]
edges = [[i] for i in range(N)]
for query in range(Q-1, -1, -1):
    v, d, c = shots[query]
    dq = collections.deque()
    dq.append((d, v))
    visited = [False for i in range(N)]
    while dq:
        size, idx = dq.popleft()
        if sizes[idx] >= size:
            continue
        else:
            sizes[idx] = size
        visited[idx] = True
        if colors[idx] == 0:
            colors[idx] = c
        if size >= d:
            continue
        for nv in nodes[idx]:
            if not visited[nv]:
                dq.append((size+1, nv))
print(*colors, sep='\n')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())

link = [[] for _ in range(N)]
color = [0] * N

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    link[a].append(b)
    link[b].append(a)

Q = int(input())


def paint(current, history, c, d):
    color[current] = c
    if d > 0:
        for next in link[current]:
            if current != next and next not in history:
                history.add(next)
                paint(next, history, c, d - 1)


for i in range(Q):
    v, d, c = map(int, input().split())
    v -= 1
    paint(v, set([v]), c, d)

print(*color, sep='\n')

Submission status: Wrong Answer

Solution code:
import collections
N,M = map(int, input().split())

nodes = [[] for i in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    nodes[a-1].append(b-1)
    nodes[b-1].append(a-1)


shots = []
Q = int(input())
for i in range(Q):
    v,d,c = map(int, input().split())
    shots.append((v-1, d, c))
colors = [0 for i in range(N)]
sizes = [0 for i in range(N)]
edges = [[i] for i in range(N)]
for i in range(Q-1, -1, -1):
    v, d, c = shots[i]
    colors[v] = c
    dq = collections.deque()

    for nv in nodes[v]:
        dq.append((1, nv))
    visited = [False for i in range(N)]
    visited[v] = True
    while dq:
        dist, idx = dq.popleft()
        visited[idx] = True
        if colors[idx] == 0:
            colors[idx] = c
        if dist >= d:
            continue
        for nv in nodes[idx]:
            if not visited[nv]:
                dq.append((dist+1, nv))
print(*colors, sep='\n')

Submission status: Wrong Answer

Solution code:
import collections
N,M = map(int, input().split())

nodes = [[] for i in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    nodes[a-1].append(b-1)
    nodes[b-1].append(a-1)


shots = []
Q = int(input())
for i in range(Q):
    v,d,c = map(int, input().split())
    shots.append((v-1, d, c))
colors = [0 for i in range(N)]
sizes = [0 for i in range(N)]
edges = [[i] for i in range(N)]
for i in range(Q-1, -1, -1):
    v, d, c = shots[i]
    if colors[v] == 0:
        colors[v] = c
        dq = collections.deque()

        for nv in nodes[v]:
            dq.append((1, nv))
        visited = [False for i in range(N)]
        visited[v] = True
        while dq:
            dist, idx = dq.popleft()
            visited[idx] = True
            if colors[idx] == 0:
                colors[idx] = c
            if dist >= d:
                continue
            for nv in nodes[idx]:
                if not visited[nv]:
                    dq.append((dist+1, nv))
print(*colors, sep='\n')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

EPS = 1e-9

#http://www.deqnotes.net/acmicpc/2d_geometry/lines
def dot(a, b):
    return a.real * b.real + a.imag * b.imag

def cross(a, b):
    return a.real * b.imag - a.imag * b.real

def distance(a, b, c):
    if dot(b-a, c-a) <= EPS:
        return abs(c-a)
    if dot(a-b, c-b) <= EPS:
        return abs(c-b)
    return abs(cross(b-a, c-a)/(b-a))

def dijkstra(s):
    dist = z[:]
    dist[s] = 0
    heap = []
    heapq.heappush(heap, (0, s))
    
    while heap:
        dd, v = heapq.heappop(heap)
        dv = dist[v]
        if dv < dd:
            continue
        for i in path[v]:
            dvi = 1
            if dist[i] > dv + dvi:
                dist[i] = dv + dvi
                heapq.heappush(heap, (dist[i], i))
    return dist

N, M = ln()

z = [10000000] * (N + 1)

path = collections.defaultdict(list)
for i in xrange(M):
    a, b = ln()
    path[a].append(b)
    path[b].append(a)


Q = n()
VDC = []
for i in xrange(Q):
    v, d, c = ln()
    VDC.append((v, d, c))

if N > 2000 or M > 2000 or Q > 2000:
    sys.exit(0)

distance = [[]]
for i in xrange(1, N + 1):
    distance.append(dijkstra(i))

distance_sorted = [[]]
for i in xrange(1, N + 1):
    temp = zip(distance[i], range(N + 1))
    temp.sort()
    distance_sorted.append(temp)

color = [0] * (N + 1)
for v, d, c in VDC:
    for b, i in distance_sorted[v]:
        if b <= d:
            color[i] = c
        else:
            break

for c in color[1:]:
    print c

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())

link = [[] for _ in range(N)]
color = [0] * N

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    link[a].append(b)
    link[b].append(a)

Q = int(input())


def paint(nodes, c, d):
    current = nodes[-1]
    color[current] = c
    if d > 0:
        for next in link[current]:
            if current != next and not next in nodes:
                nodes.append(next)
                paint(nodes, c, d - 1)


for i in range(Q):
    v, d, c = map(int, input().split())
    v -= 1
    paint([v], c, d)

print(*color, sep='\n')

Submission status: Wrong Answer

Solution code:
N, M = map(int, raw_input().split())
graph = dict()
colors = dict()
for i in xrange(N):
    graph[i + 1] = []
    colors[i + 1] = 0
for i in xrange(M):
    a, b = map(int, raw_input().split())
    graph[a].append(b)
    graph[b].append(a)

def paint(curNodes, color, g, colors, remLevel):
    if remLevel == 0:
        return colors
    newCurNodes = []
    for node in curNodes:
        if colors[node] == color:
            continue
        colors[node] = color
        newCurNodes += g[node]
    return paint(newCurNodes, color, g, colors, remLevel - 1)

Q = int(raw_input())
for i in xrange(Q):
    v, d, c = map(int, raw_input().split())
    colors = paint([v], c, graph, colors, d + 1)
for v in colors.values():
    print v

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

EPS = 1e-9

#http://www.deqnotes.net/acmicpc/2d_geometry/lines
def dot(a, b):
    return a.real * b.real + a.imag * b.imag

def cross(a, b):
    return a.real * b.imag - a.imag * b.real

def distance(a, b, c):
    if dot(b-a, c-a) <= EPS:
        return abs(c-a)
    if dot(a-b, c-b) <= EPS:
        return abs(c-b)
    return abs(cross(b-a, c-a)/(b-a))

def dijkstra(s):
    dist = z[:]
    dist[s] = 0
    heap = []
    heapq.heappush(heap, (0, s))
    
    while heap:
        dd, v = heapq.heappop(heap)
        dv = dist[v]
        if dv < dd:
            continue
        for i in path[v]:
            dvi = 1
            if dist[i] > dv + dvi:
                dist[i] = dv + dvi
                heapq.heappush(heap, (dist[i], i))
    return dist

N, M = ln()

z = [10000000] * (N + 1)

path = collections.defaultdict(list)
for i in xrange(M):
    a, b = ln()
    path[a].append(b)
    path[b].append(a)


Q = n()
VDC = []
for i in xrange(Q):
    v, d, c = ln()
    VDC.append((v, d, c))

if N > 2000 or M > 2000 or Q > 2000:
    sys.exit(0)

distance = [[]]
for i in xrange(1, N + 1):
    distance.append(dijkstra(i))

color = [0] * (N + 1)
for v, d, c in VDC:
    for i, b in enumerate(distance[v]):
        if b <= d:
            color[i] = c

for c in color[1:]:
    print c

Submission status: Wrong Answer

Solution code:
from collections import namedtuple
class Node:
    def __init__(self):
        self.color = 0
        self.to = []

def dfs(graph, cur, color, visited, dist):
    visited[cur] = True
    graph[cur].color = color
    if dist == 0:
        return
    for n in graph[cur].to:
        if visited[n]:
            continue
        dfs(graph, n, color, visited, dist-1)
    
def main():
    N, M = [int(i) for i in input().split()]
    graph = [Node() for _ in range(N)]
    for _ in range(M):
        a, b = [int(i) for i in input().split()]        
        graph[a-1].to.append(b-1)
        graph[b-1].to.append(a-1)
    Q = int(input())
    for _ in range(Q):
        v, d, c = [int(i) for i in input().split()]
        visited = [False] * N
        dfs(graph, v-1, c, visited, d)
    for i in range(N):
        print(graph[i].color)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,m = map(int,input().split())
e = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    e[a].append(b)
    e[b].append(a)
qv = int(input())
Q = [list(map(int,input().split())) for i in range(qv)]
Q = Q[::-1]
l = [[0]*(11) for i in range(n+1)]
for v,d,c in Q:
    if l[v][d] > 0:
        continue
    l[v][d] = c
color = [0]*(n+1)

left = [i for i in range(1,n+1)]
num = 0
while num < qv and left:
    v,d,c = Q[num]
    s = set()
    s.add(v)
    dist = [float("INF")]*(n+1)
    dist[v] = 0
    q = [v]
    for i in range(1,d+1):
        nq = []
        for now in q:
            for nex in e[now]:
                if dist[nex]<= i:
                    continue
                nq.append(nex)
                dist[nex] = i
                s.add(nex)
        q = nq
    nl = []
    
    for i in left:
        if i in s:
            color[i] = c
        else:
            nl.append(i) 
    num += 1
    left = nl
    
for i in color[1:]:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,m = map(int,input().split())
e = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    e[a].append(b)
    e[b].append(a)
qv = int(input())
Q = [list(map(int,input().split())) for i in range(qv)]
Q = Q[::-1]
l = [[0]*(11) for i in range(n+1)]
for v,d,c in Q:
    if l[v][d] > 0:
        continue
    l[v][d] = c
dic = {}
color = [0]*(n+1)

left = [i for i in range(1,n+1)]
num = 0
while num < qv and left:
    v,d,c = Q[num]
    if v not in dic:
        for i in range(10,-1,-1):
            if l[v][i] > 0:
                M = i
                break
        dic[v] = [set() for i in range(M+1)]
        s = set()
        s.add(v)
        dic[v][0] |= s
        q = [v]
        for i in range(1,M+1):
            nq = []
            for now in q:
                for nex in e[now]:
                    if nex in s:
                        continue
                    nq.append(nex)
                    s.add(nex)
            dic[v][i] |= s
            q = nq
    nl = []
    
    for i in left:
        if i in dic[v][d]:
            color[i] = c
        else:
            nl.append(i) 
    num += 1
    left = nl
    
for i in color[1:]:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,m = map(int,input().split())
e = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    e[a].append(b)
    e[b].append(a)
qv = int(input())
Q = [list(map(int,input().split())) for i in range(qv)]
Q = Q[::-1]
l = [[0]*(11) for i in range(n+1)]
for v,d,c in Q:
    if l[v][d] > 0:
        continue
    l[v][d] = c
dic = {}
color = [0]*(n+1)

left = [i for i in range(1,n+1)]
num = 0
while num < qv and left:
    v,d,c = Q[num]
    if v not in dic:
        for i in range(10,-1,-1):
            if l[v][i] > 0:
                M = i
                break
        dic[v] = [set() for i in range(M+1)]
        s = set()
        s.add(v)
        dic[v][0] |= s
        dist = [float("INF")]*(n+1)
        dist[v] = 0
        q = [v]
        for i in range(1,M+1):
            nq = []
            for now in q:
                for nex in e[now]:
                    if dist[nex]<= i:
                        continue
                    nq.append(nex)
                    dist[nex] = i
                    s.add(nex)
            dic[v][i] |= s
            q = nq
    nl = []
    
    for i in left:
        if i in dic[v][d]:
            color[i] = c
        else:
            nl.append(i) 
    num += 1
    
    left = nl
    
for i in color[1:]:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)
n,m=map(int, input().split())
e=[[] for _ in range(n)]
for _ in range(m):
    ai,bi=map(int, input().split())
    ai-=1;bi-=1
    e[ai].append(bi);e[bi].append(ai)
Q=int(input())
q=[tuple(map(int, input().split())) for _ in range(Q)]

q.reverse()
color=[0]*n
from collections import deque
que=deque()
used=set()
def bfs(v,d,c):
    if d<0:
        return
    used.add(v)
    if not color[v]:
        color[v]=c
    #que.append((v,d))
    for u in e[v]:
        que.append((u,d-1))
    while que:
        u,dd=que.popleft()
        if u not in used:
            bfs(u,dd,c)
for v,d,c in q:
    v-=1
    used=set()
    bfs(v,d,c)
    #print(v,d,c,"   ",*color)
for c in color:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,m = map(int,readline().split())
data = list(map(int,read().split()))
ab = data[:2*m]
q = data[2*m]
vdc = data[2*m+1:]

links = [[] for _ in range(n+1)]
it = iter(ab)
for a,b in zip(it,it):
    links[a].append(b)
    links[b].append(a)

ans = [0] * (n+1)
length = [-1] * (n+1)

for i in range(q-1,-1,-1):
    v,d,c = vdc[i*3:i*3+3]
    if( length[v] >= d):
        continue

    stack = [(v,d)]
    while(stack):
        vj,dj = stack.pop()
        if(ans[vj]==0):
            ans[vj] = c
        if(dj > 0):
            for vk in links[vj]:
                if( length[vk] < dj-1):
                    stack.append((vk,dj-1))

print('\n'.join(map(str,ans[1:])))

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
Q = int(input())
queries = [list(map(int, input().split())) + [i] for i in range(Q)]
num = [-1] * (N+1)
color = [0] * (N+1)
paint = [[] for _ in range(N+1)]
for v, d, c, i in queries:
    paint[v].append((i, d, c))

used = [set() for _ in range(N+1)]

for _ in range(11):
    npaint = [[] for _ in range(N+1)]
    for v in range(1, N+1):
        if not paint[v]:
            continue

        paint[v].sort(key=lambda p: -p[0])
        pv = []
        for i, d, c in paint[v]:
            if i in used[v]:
                continue
            if not pv or pv[-1][1] < d:
                pv.append((i, d, c))
                used[v].add(i)

        if not pv:
            continue

        if num[v] < pv[0][0]:
            num[v], _, color[v] = pv[0]

        for u in G[v]:
            for i, d, c in pv:
                if d > 0:
                    npaint[u].append((i, d - 1, c))
    paint = npaint

print(*color[1:], sep='\n')

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
Q = int(input())
queries = [list(map(int, input().split())) + [i] for i in range(Q)]
num = [-1] * (N+1)
color = [0] * (N+1)
paint = [[] for _ in range(N+1)]
for v, d, c, i in queries:
    paint[v].append((i, d, c))

for _ in range(11):
    npaint = [[] for _ in range(N+1)]
    for v in range(1, N+1):
        if not paint[v]:
            continue
        paint[v].sort(key=lambda p: -p[0])
        pv = []
        for i, d, c in paint[v]:
            if not pv or pv[-1][1] < d:
                pv.append((i, d, c))
        if num[v] < pv[0][0]:
            num[v], _, color[v] = pv[0]
        for u in G[v]:
            for i, d, c in pv:
                if d > 0:
                    npaint[u].append((i, d - 1, c))
    paint = npaint

print(*color[1:], sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
color = [0] * (N+1)

Q = int(input())
for _ in range(Q):
    v, d, c = map(int, input().split())
    queue = deque([v])
    dist = [-1] * (N+1)
    dist[v] = 0
    while queue:
        u = queue.popleft()
        if dist[u] > d:
            break
        color[u] = c
        for w in G[u]:
            if dist[w] == -1:
                dist[w] = dist[u] + 1
                queue.append(w)
print(*color[1:], sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, deque
    n, m = map(int, readline().split())
    edge = defaultdict(list)
    for _ in range(m):
        a, b = map(int, readline().split())
        edge[a].append(b)
        edge[b].append(a)

    q = int(readline())
    mat = [[] for _ in range(q)]

    for i in range(q):
        mat[i] = list(map(int, readline().split()))

    paint = [[0, -1] for _ in range(n + 1)]
    outer = defaultdict(list)

    for v, d, c in mat[::-1]:
        if d == 0 and paint[v] == -1:
            paint[v][0] = c
            paint[v][1] = 0
        else:
            if paint[v][1] >= d:
                continue
            que = deque()
            que.append((v, d, c))
            visited = [False] * (n+1)
            while que:
                cur, rem, color = que.popleft()
                visited[cur] = True
                if paint[cur][0] == 0:
                    paint[cur][0] = color
                    paint[cur][1] = rem
                    outer[v].append(cur)
                if rem > 0:
                    n_rem = rem - 1
                    for nx in edge[cur]:
                        if visited[nx]:
                            continue
                        if paint[nx][1] >= n_rem:
                            pass
                        else:
                            que.append((nx, n_rem, color))

    for i in range(1, n + 1):
        print(paint[i][0])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, deque
    n, m = map(int, readline().split())
    edge = defaultdict(list)
    for _ in range(m):
        a, b = map(int, readline().split())
        edge[a].append(b)
        edge[b].append(a)

    q = int(readline())
    mat = [[] for _ in range(q)]

    for i in range(q):
        mat[i] = list(map(int, readline().split()))

    paint = [[0, -1] for _ in range(n + 1)]
    for v, d, c in mat[::-1]:
        if d == 0 and paint[v] == -1:
            paint[v][0] = c
            paint[v][1] = 0
        else:
            if paint[v][1] >= d:
                continue
            que = deque()
            que.append((v, d, c))
            while que:
                cur, rem, color = que.popleft()
                if paint[cur][0] == 0:
                    paint[cur][0] = color
                    paint[cur][1] = rem
                if rem > 0:
                    n_rem = rem - 1
                    for nx in edge[cur]:
                        if paint[nx][1] >= n_rem:
                            pass
                        else:
                            que.append((nx, n_rem, color))

    for i in range(1, n + 1):
        print(paint[i][0])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, deque
    n, m = map(int, readline().split())
    edge = defaultdict(list)
    for _ in range(m):
        a, b = map(int, readline().split())
        edge[a].append(b)
        edge[b].append(a)

    mat = []
    q = int(readline())
    for _ in range(q):
        mat.append(list(map(int, readline().split())))

    paint = [[0, -1] for _ in range(n + 1)]
    for v, d, c in mat[::-1]:
        if d == 0 and paint[v] == -1:
            paint[v][0] = c
            paint[v][1] = 0
        else:
            que = deque()
            que.append((v, d, c))
            while que:
                cur, rem, color = que.popleft()
                if paint[cur][0] == 0:
                    paint[cur][0] = color
                    paint[cur][1] = rem
                if rem > 0:
                    n_rem = rem - 1
                    for nx in edge[cur]:
                        if paint[nx][1] >= n_rem:
                            pass
                        else:
                            que.append((nx, n_rem, color))

    for i in range(1, n + 1):
        print(paint[i][0])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(set)
for _ in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)
dp = [[(-1,0)]*n for _ in range(11)]
q = int(input())
qs = [None]*q
for i in range(q):
    v,d,c = tuple(map(int, input().split()))
    v -= 1
    qs[i] = (i,v,d,c)
from itertools import product
for i0,i,u in product(range(10,-1,-1), range(0,11), range(n)):
# for i0 in range(10, -1, -1):
    if i==0:
        for i,v,d,_ in qs:
            if i0<=d:
                dp[0][v] = (i,d)
    else:
#     for i in range(1,11):
#         for u in range(n):
        if dp[i-1][u][0]>dp[i][u][0]:
            ind0, d0 = dp[i-1][u]
        else:
            ind0, d0 = dp[i][u]
        for v in ns[u]:
            ind,d = dp[i-1][v]
            if ind>ind0 and d>0:# and i0<=i+d:
                ind0, d0 = ind, d-1
        dp[i][u] = (ind0, d0)
#     print(dp[10])
write("\n".join(map(str, ((qs[dp[10][u][0]][3] if dp[10][u][0]>=0 else 0) for u in range(n)))))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(set)
for _ in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)
dp = [[(-1,0)]*n for _ in range(11)]
q = int(input())
qs = [None]*q
for i in range(q):
    v,d,c = tuple(map(int, input().split()))
    v -= 1
    qs[i] = (i,v,d,c)
for i0 in range(10, -1, -1):
    for i,v,d,_ in qs:
        if i0<=d:
            dp[0][v] = (i,d)
    for i in range(1,11):
        for u in range(n):
            if dp[i-1][u][0]>dp[i][u][0]:
                ind0, d0 = dp[i-1][u]
            else:
                ind0, d0 = dp[i][u]
            for v in ns[u]:
                ind,d = dp[i-1][v]
                if ind>ind0 and d>0:# and i0<=i+d:
                    ind0, d0 = ind, d-1
            dp[i][u] = (ind0, d0)
#     print(dp[10])
write("\n".join(map(str, ((qs[dp[10][u][0]][3] if dp[10][u][0]>=0 else 0) for u in range(n)))))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(set)
for _ in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)
dp = [[(-1,0,0)]*n for _ in range(11)]
q = int(input())
qs = [None]*q
for i in range(q):
    v,d,c = tuple(map(int, input().split()))
    v -= 1
    qs[i] = (i,v,d,c)
for i0 in range(10, -1, -1):
    for i,v,d,c in qs:
        if i0<=d:
            dp[0][v] = (i,c,d)
    for i in range(1,11):
        for u in range(n):
            if dp[i-1][u][0]>dp[i][u][0]:
                ind0, c0, d0 = dp[i-1][u]
            else:
                ind0, c0, d0 = dp[i][u]
            for v in ns[u]:
                ind,c,d = dp[i-1][v]
                if ind>ind0 and d>0 and i0<=i+d:
                    ind0, c0, d0 = ind, c, d-1
            dp[i][u] = (ind0, c0, d0)
#     print(dp[10])
write("\n".join(map(str, (dp[10][u][1] for u in range(n)))))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(M)]
Q = int(input())
vdc = [list(map(int,input().split())) for i in range(Q)]
'''
N,M = 10**5,7
ab = [[1,2],[1,3],[1,4],[4,5],[5,6],[5,7],[2,3]]
Q = 2
vdc = [[6,1,1],[1,2,2]]
'''
g = defaultdict(set)
for a,b in ab:
    g[a].add(b)
    g[b].add(a)

ans = [0]*(N+1)

for v,d,c in vdc[::-1]:
    visited = set([v])
    vs = [v]
    if ans[v] == 0:
        ans[v] = c 
    for i in range(d):
        temp = []
        for pv in vs:
            for nv in g[pv]:
                if not nv in  visited:
                    visited.add(nv)
                    if ans[nv] == 0:
                        ans[nv] = c
                    temp.append(nv)
        vs = temp

for a in ans[1:]:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(M)]
Q = int(input())
vdc = [list(map(int,input().split())) for i in range(Q)]

g = defaultdict(set)
for a,b in ab:
    g[a].add(b)
    g[b].add(a)

ans = [0]*(N+1)
colored = [False]*(N+1)

for v,d,c in vdc[::-1]:
    visited = [False]*(N+1)
    visited[v] = True
    vs = [v]
    if ans[v] == 0:
        ans[v] = c 
    for i in range(d):
        temp = []
        for pv in vs:
            for nv in g[pv]:
                if not visited[nv]:
                    visited[nv] = True
                    if ans[nv] == 0:
                        ans[nv] = c
                    temp.append(nv)
        vs = temp

for a in ans[1:]:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(M)]
Q = int(input())
vdc = [list(map(int,input().split())) for i in range(Q)]

g = defaultdict(set)
for a,b in ab:
    g[a].add(b)
    g[b].add(a)

ans = [0]*(N+1)

for v,d,c in vdc[::-1]:
    targets = [v]
    visited = [False]*(N+1)
    visited[v] = True
    vs = [v]
    for i in range(d):
        temp = []
        for pv in vs:
            for nv in g[pv]:
                if not visited[nv]:
                    visited[nv] = True
                    targets.append(nv)
                    temp.append(nv)
        vs = temp
    for tv in targets:
        if ans[tv] == 0:
            ans[tv] = c

for a in ans[1:]:
    print(a)