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: Time Limit Exceeded

Solution code:
from collections import defaultdict,  deque

visited = [False]*(10**6 + 1)
color = [0]*(10**6 + 1)
level = [None]*(10**6 + 1)

class Graph:
  
    def __init__(self,vertices):
        self.V= vertices
        self.graph = defaultdict(list)
  
    def addEdge(self,u,v):
        self.graph[u].append(v)
        self.graph[v].append(u)
        
    def rmvEdge(self, u, v):
        for index, key in enumerate(self.graph[u]):
            if key == v:
                self.graph[u].pop(index)
        for index, key in enumerate(self.graph[v]):
            if key == u:
                self.graph[v].pop(index)
                
def BFS(graph, start, colorTemp, depth):
    queue = deque()
    queue.append(start)
    color[start] = colorTemp
    visited[start] = True
    level[start] = 0
    while queue:
        s = queue.popleft()
        if level[s] == depth:
            break
        for i in graph[s]:
            if not visited[i]:
                level[i] = level[s] + 1
                queue.append(i)
                color[i] = colorTemp
                visited[i] = True
    
n, m = map(int, raw_input().split())

g = Graph(n)

for _ in xrange(m):
    a, b = map(int, raw_input().split())
    g.addEdge(a, b)

q = int(raw_input())

for _ in xrange(q):
    v, d, c = map(int, raw_input().split())
    visited = [False]*(10**6 + 1)
    level = [None]*(10**6 + 1)
    BFS(g.graph, v, c, d)
    #print color[1: n+1]

for i in xrange(1, n+1):
    print color[i]

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

for _ in range(Q):
    v, d, c = map(int, input().split())
    # BFS
    dist = dict()
    deq = deque([v])
    color[v] = c
    dist[v] = 0
    while len(deq) > 0:
        s = deq.popleft()
        if dist[s] >= d:
            break
        for t in G[s]:
            if t in dist.keys():
                pass
            else:
                dist[t] = dist[s] + 1
                color[t] = c
                deq.append(t)
                
for n in range(1, N+1):
    print(color[n])

Submission status: Time Limit Exceeded

Solution code:
import copy
temp=input().split()
N=int(temp[0])
M=int(temp[1])

ab=[[int(j)-1 for j in input().split()] for i in range(M)]
Q=int(input())

color=[-1 for i in range(N)]
chain=[[] for i in range(N)]
for i in range(M):
	chain[ab[i][0]]+=[ab[i][1]]
	chain[ab[i][1]]+=[ab[i][0]]
#print(chain)
#do
for i in range(Q):
	vdc=[int(j)-1 for j in input().split()]
	paint=[vdc[0]]
	nextPaint=[]
	painted=[False for i in range(N)]
	painted[vdc[0]]=True
	color[vdc[0]]=vdc[2]
	#print(vdc)
	for j in range(vdc[1]+1):
		for k in paint:
			for m in chain[k]:
				if not painted[m]:
					color[m]=vdc[2]
					nextPaint+=[m]
			painted[k]=True
		paint=copy.deepcopy(nextPaint)
		nextPaint=[]
	#print(color)
for i in range(N):
	print(color[i]+1)

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int,input().split()))

e = [[[i] for j in range(11)] for i in range(n+1)]

for i in range(m):
	a,b = list(map(int,input().split()))
	e[a][1].append(b)
	e[b][1].append(a)

for i in range(2,11):
	for j in range(1,n+1):
		e[j][i] = e[j][i-1][:]
		l = e[j][i][:]
		for k in l:
			e[j][i].extend((e[k][1]))
		e[j][i] = list(set(tuple(e[j][i])))

# for i in e:
# 	print(i)

q = int(input())
que = [list(map(int,input().split())) for i in range(q)]

color = [0 for i in range(n+1)]
for v,d,c in que:
	for i in e[v][d]:
		color[i] = c

color = list(map(str,color))
print("\n".join(color[1:]))

Submission status: Time Limit Exceeded

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 i in range(Q-1, -1, -1):
    v, d, c = shots[i]
    dq = collections.deque()
    dq.append((0, v))
    visited = [False for i in range(N)]
    while dq:
        dist, idx = dq.popleft()
        if sizes[idx] >= d - dist:
            continue
        else:
            sizes[idx] = d- dist
        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: Time Limit Exceeded

Solution code:
import re
from scipy import integrate
from operator import itemgetter
from collections import Counter
from collections import deque
import fractions
import itertools
from pydoc import help


from heapq import heappop, heappush, heapify
import numpy as np
from copy import deepcopy as dcopy

import math
from collections import defaultdict as dd
def main():
    N, M = map(int, input().split())

    edges = np.array([[float('inf')]*N for i in range(N)])
    for m in range(M):
        a, b = map(int, input().split())
        edges[a-1][b-1] = 1
        edges[b-1][a-1] = 1

    for n in range(N):
        edges[n][n] = 0

    # print(edges)
    D = dcopy(edges)
    for k in range(N):  # 中間地点
        for i in range(N):  #  
            if edges[i][k] == float('inf'):
                continue
            for j in range(N):
                if D[k][j] == float('inf'):
                    continue
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
                D[j][i] = min(D[j][i], D[j][k] + D[k][i])

    # print(D)

    Q = int(input())
    colors = [0]*N

    for q in range(Q):
        v,d,c = map(int, input().split())
        for n in range(N):
            if D[v-1][n] <= d:
                colors[n] = c

    for c in colors:
        print(c)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python

def coloring(e, v, t, d, c):
    global visited
    global color
    
    color[v] = c
    if t == d:
        return

    for i in e[v]:
        if visited[i] > t + 1:
            visited[i] = t + 1
    for i in e[v]:
        if visited[i] == t + 1:
            coloring(e, i, t+1, d, c)
    return
    

N, M = map(int, input().split())
e = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    e[a-1].append(b-1)
    e[b-1].append(a-1)
    
Q = int(input())
color = [0 for i in range(N)]
for i in range(Q):
    v, d, c = map(int, input().split())
    v = v - 1
    visited = [1000000 for j in range(N)]
    visited[v] = 0
    coloring(e, v, 0, d, c)
    
for c in color:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
max_n, max_m = map(int, input().split())
v = [[] for x in range(max_n + 1)]
color = ["0" for x in range(max_n + 1)]
def define(a, b):
    v[a].append(b)

for i in range(max_m):
    a, b = map(int, input().split())
    define(a, b)
    define(b, a)

def visit(point, length, col):
    if length:
        next_points = v[point]
        for next_point in next_points:
            visit(next_point, length - 1, col)
    color[point] = col

q = int(input())
for i in range(q):
    a, b, c = input().split()
    visit(int(a), int(b), c)
print("\n".join(color[1:]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

N, M = map(int, raw_input().split(" "))
ABs = []
for i in range(0, M):
    a, b = map(int, raw_input().split(" "))
    ABs.append([a, b])

# 初期
Data = []
for i in range(1, N+1):
    Data.append([i, 0])

Q = int(raw_input())
for i in range(0, Q):
    v, d, c = map(int, raw_input().split(" "))

    canPoints = [v]

    # 繋がりの点
    for ii in range(0, d):
        filterABs = filter(lambda n: n[0] in canPoints or n[1] in canPoints, ABs)
        for filterAB in filterABs:
            canPoints.extend(filterAB)

    canPoints = list(set(canPoints))
    for canPoint in canPoints:
        Data[canPoint-1][1] = c


for d in Data:
    print d[1]

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

for _ in range(Q):
    v, d, c = map(int, input().split())
    # BFS
    dist  = [-1]*(N+1)
    deq = deque([v])
    color[v] = c
    dist[v] = 0
    while len(deq) > 0:
        s = deq.popleft()
        if dist[s] >= d:
            break
        for t in G[s]:
            if dist[t] != -1:
                pass
            else:
                dist[t] = dist[s] + 1
                color[t] = c
                deq.append(t)
                
for n in range(1, N+1):
    print(color[n])

Submission status: Time Limit Exceeded

Solution code:
import copy
temp=input().split()
N=int(temp[0])
M=int(temp[1])

ab=[[int(j)-1 for j in input().split()] for i in range(M)]
Q=int(input())

color=[-1 for i in range(N)]
chain=[[] for i in range(N)]
for i in range(M):
	chain[ab[i][0]]+=[ab[i][1]]
	chain[ab[i][1]]+=[ab[i][0]]
#print(chain)
#do
for i in range(Q):
	vdc=[int(j)-1 for j in input().split()]
	paint=[vdc[0]]
	nextPaint=[]
	painted=[]
	color[vdc[0]]=vdc[2]
	#print(vdc)
	for j in range(vdc[1]+1):
		for k in paint:
			for m in chain[k]:
				if not m in painted:
					color[m]=vdc[2]
					nextPaint+=[m]
			painted+=[k]
		paint=copy.deepcopy(nextPaint)
		nextPaint=[]
	#print(color)
for i in range(N):
	print(color[i]+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
vertices,edges = (int(n) for n in input().split(" "))
connect = defaultdict(list)
for v in range(edges):
    a,b = (int(n) - 1 for n in input().split(" "))
    connect[a].append(b)
    connect[b].append(a)
color = [0 for n in range(vertices)]
trial = int(input())
for t in range(trial):
    ver,dep,col = (int(n) for n in input().split(" "))
    ver -= 1
    queue = connect[ver]
    color[ver] = col
    temp_set = set() | {ver}
    # print(queue)
    while dep > 0 and queue != []:
        newqueue = []
        for q in queue:
            if q not in temp_set:
                temp_set |= {q}
                color[q] = col
                newqueue.extend(connect[q])
        queue = newqueue
        # print(queue)
        dep -= 1
for c in color:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python

def coloring(e, v, t, d, c):
    global visited
    global color
    
    color[v] = c
    visited[v] = t
    if t == d:
        return

    for i in e[v]:
        if visited[i] > t:
            coloring(e, i, t+1, d, c)
    return
    

N, M = map(int, input().split())
e = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    e[a-1].append(b-1)
    e[b-1].append(a-1)
    
Q = int(input())
color = [0 for i in range(N)]
for i in range(Q):
    v, d, c = map(int, input().split())
    v = v - 1
    visited = [1000000 for j in range(N)]
    coloring(e, v, 0, d, c)
    
for c in color:
    print(c)

Submission status: Time Limit Exceeded

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)
                nodes.pop()


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

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

Submission status: Time Limit Exceeded

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(node, c, d):
    color[node] = c
    if d > 0:
        for next in link[node]:
            if node != next:
                paint(next, 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: Time Limit Exceeded

Solution code:
import heapq

def dijkstra(s,g,n):
    d=[float('inf')]*n
    d[s]=0
    pq=[]
    heapq.heappush(pq,[0,s])
    while len(pq)!=0:
        t,u=heapq.heappop(pq)
        if d[u]<t:
            continue
        for v in g[u]:
            if d[u]+1<d[v]:
                d[v]=d[u]+1
                heapq.heappush(pq,[d[v],v])
    return d

n,m=map(int,raw_input().split())
g=[[] for _ in xrange(n)]
for i in xrange(m):
    a,b=map(int,raw_input().split())
    a-=1;b-=1
    g[a].append(b)
    g[b].append(a)
q=int(raw_input())
color=[0]*n
for i in xrange(q):
    v,d,c=map(int,raw_input().split())
    v-=1
    dist=dijkstra(v,g,n)
    for j in xrange(n):
        if dist[j]<=d:
            color[j]=c
for i in xrange(n):
    print color[i]

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def main():
    n,m = LI()
    e = collections.defaultdict(set)
    for _ in range(m):
        a,b = LI()
        e[a-1].add(b-1)
        e[b-1].add(a-1)
    r = [0] * n

    qq = I()
    for _ in range(qq):
        v,d,c = LI()
        v -= 1
        r[v] = c
        f = [False] * n
        f[v] = True
        q = [v]
        for __ in range(d):
            t = []
            for p in q:
                for vv in e[p]:
                    if f[vv]:
                        continue
                    f[vv] = True
                    t.append(vv)
                    r[vv] = c
            q = t

    return '\n'.join(map(str, r))



print(main())

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(M)]
Q = int(input())
vdc = [list(map(int, input().split())) for _ in range(Q)]

L = [[] for _ in range(N)]
for a, b in ab:
  a -= 1
  b -= 1
  L[a].append(b)
  L[b].append(a)

D = [[0] * 11 for _ in range(N)]
Ans = [0] * N

def check(v, d, c):
  if D[v][d] != 0: return
  if d == 0:
    D[v][d] = c
    return
  for i in range(d, -1, -1):
    if D[v][i] != 0: break
    D[v][i] = c
  for i in L[v]:
    pass

import queue
Que = queue.Queue
get = queue.Queue.get
put = queue.Queue.put
emp = queue.Queue.empty

for v, d, c in vdc[::-1]:
  v -= 1
  if D[v][d] != 0: continue
  t = (d << 18) + v
  S = Que()
  put(S, t)
  while not emp(S):
    t = get(S)
    dd = t >> 18
    vv = t & ((1 << 18) - 1)
    if Ans[vv] == 0: Ans[vv] = c
    if dd == 0:
      D[vv][dd] = c
      continue
    for i in range(dd, -1, -1):
      if D[vv][i] != 0: break
      D[vv][i] = c
    for i in L[vv]:
      if D[i][dd - 1] != 0: continue
      t = ((dd - 1) << 18) + i
      put(S, t)

for i in Ans:
  print(i)

Submission status: Accepted

Solution code:
from collections import deque
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)]

color = [0]*(n+1)
used = [-1]*(n+1)

for v,d,c in Q[::-1]:
    if used[v] > d:
        continue
    
    q = deque([[v,d]])
    while q:
        now, dis = q.popleft()
        if dis < 0:
            continue
        if color[now] == 0:
            color[now] = c
        for nex in e[now]:
            if used[nex] < dis-1:
                used[nex] = dis-1
                q.append([nex,dis-1])
    
for i in color[1:]:
    print(i)

Submission status: Accepted

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
    length[v] = d

    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))
                    length[vk] = dj-1

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

Submission status: Accepted

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()))

    dp = [[0] * 11 for _ in range(n + 1)]

    for v, d, c in mat[::-1]:
        if dp[v][d] != 0:
            continue
        que = deque()
        que.append((v, d, c))
        while que:
            cur, dist, color = que.popleft()
            for i in range(dist, -1, -1):
                if dp[cur][i] == 0:
                    dp[cur][i] = color
                else:
                    break
            if dist > 0:
                for nx in edge[cur]:
                    if dp[nx][dist - 1] != 0:
                        continue
                    else:
                        que.append((nx, dist - 1, color))

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
path = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    path[a - 1].append(b - 1)
    path[b - 1].append(a - 1)
q = int(input())
query = []
for i in range(q):
    v, d, c = map(int, input().split())
    query.append((i+1, v - 1, d, c))
dp = [[0] * 11 for i in range(n)]
def paint(v, d, i, dp, path):
    if dp[v][d] == 0:
        dp[v][d] = i
        if d > 0:
            paint(v, d - 1, i, dp, path)
            for u in path[v]:
                paint(u, d - 1, i, dp, path)
    return

for i, v, d, c in query[::-1]:
    paint(v, d, i, dp, path)
for i in range(n):
    if dp[i][0] == 0:
        print(0)
    else:
        print(query[dp[i][0]-1][3])

Submission status: Accepted

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(list)
for _ in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].append(v)
    ns[v].append(u)
    
dp = [[-1]*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)
    dp[d][v] = i
from itertools import product
for i,u in product(range(10,0,-1), range(n)):
    if dp[i][u]>=0:
        dp[i-1][u] = max(dp[i-1][u], dp[i][u])
        for v in ns[u]:
            dp[i-1][v] = max(dp[i-1][v], dp[i][u])

write("\n".join(map(str, ((qs[dp[0][u]][3] if dp[0][u]>=0 else 0) for u in range(n)))))

Submission status: Accepted

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)
'''
from random import randint as ri
import networkx as nx
N,M = 10**5,10**5
g = nx.gnm_random_graph(N,M)
g = nx.to_dict_of_lists(g)
g = {v+1:[nv+1 for nv in g[v]] for v in g}
Q = 20**3
vdc = [[ri(1,N),ri(0,10),ri(1,10**5)] for i in range(Q)]
'''

def dpinit(ps, val=0):
    import copy
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [copy.deepcopy(res) for k in [0]*i]
    return res

ans = [0]*(N+1)
visited = dpinit([N+1,11],False)

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def graph_input(N, M):
    G = [[] for _ in range(N + 1)]
    for _ in range(M):
        a, b = map(int, readline().split())
        G[a].append(b)
        G[b].append(a)
    ind = np.cumsum(list(map(len, G)), dtype=np.int32)
    G = np.concatenate(G).astype(np.int32)
    return G, ind

def main(N, G, ind, V, D, C):
    # 強さ n で塗った時刻
    dp = np.full((N + 1, 11), -1, np.int32)
    for t in range(len(V)):
        v, d = V[t], D[t]
        dp[v, d] = t
    for n in range(10, 0, -1):
        for v in range(1, N + 1):
            dp[v, n - 1] = max(dp[v, n - 1], dp[v, n])
            for i in range(ind[v - 1], ind[v]):
                w = G[i]
                dp[w, n - 1] = max(dp[w, n - 1], dp[v, n])
    dp = dp[:, 0]
    for v in range(1, N + 1):
        t = dp[v]
        c = C[t] if t != -1 else 0
        print(c)

signature = '(i8,i4[:],i4[:],i4[:],i4[:],i4[:])'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', signature)(main)
    cc.compile()

from my_module import main

N, M = map(int, readline().split())
G, ind = graph_input(N, M)
Q = int(readline())
nums = np.array(read().split(), np.int32)
V = nums[::3]
D = nums[1::3]
C = nums[2::3]

main(N, G, ind, V, D, C)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(4100000)
  
n,m = map(int, readline().split())
g = [[]*n for i in range(n)]
for i in range(m):
    u,v = map(int,readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
q = int(readline())
chk = []
for i in range(q):
  V,D,C = map(int,readline().split())
  chk.append((V,D,C))
  

memo = [[0]*11 for _ in range(n)]

def f(v,d,c):
  if memo[v][d] != 0:
    return
  else:
    memo[v][d] = c
    if d > 0:
      f(v,d-1,c)
      for nxt in g[v]:
        f(nxt,d-1,c)
    else:
      return

for V,D,C in chk[::-1]:
    f(V-1,D,C)

for v in range(n):
    print(memo[v][0])

Submission status: Accepted

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

def func(v, d, c):
    if memo[v][d]!=0:
        return
    
    memo[v][d] = c
    
    if d==0:
        return
    
    func(v, d-1, c)
    
    for nv in G[v]:
        func(nv, d-1, c)

N, M = map(int, input().split())
G = [[] for _ in range(N)]

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

Q = int(input())
q = [tuple(map(int, input().split())) for _ in range(Q)]
q.reverse()
memo = [[0]*11 for _ in range(N)]

for v, d, c in q:
    func(v-1, d, c)

for v in range(N):
    print(memo[v][0])

Submission status: Accepted

Solution code:
import heapq,sys
from collections import deque

input=sys.stdin.readline

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

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

ans=[0]*N
time=[-1]*N


for i in range(Q):
    v,d,c=query[i]
    que=deque([(0,v,d)])
    while que:
        val,v,di=que.popleft()
        time[v]=di
        if not ans[v]:
            ans[v]=c
        for nv in edge[v]:
            if di-1>time[nv]:
                time[nv]=di-1
                que.append((val+1,nv,di-1))

for i in range(N):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
from collections import deque

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def solve():
  n, m = nm()
  G = [list() for _ in range(n)]
  for _ in range(m):
    a, b = nm()
    a -= 1; b -= 1
    G[a].append(b)
    G[b].append(a)
  Q = int(input())
  color = [0]*n
  dist = [-1]*n
  queries = [tuple(nm()) for _ in range(Q)][::-1]
  for v, d, c in queries:
    v -= 1
    q = deque()
    q.append((v, d))
    while q:
      v, d = q.popleft()
      if dist[v] >= d:
        continue
      dist[v] = d
      if not color[v]: color[v] = c
      for x in G[v]:
        if d - 1 > dist[x]:
          q.append((x, d-1))
  print(*color, sep='\n')
  return

solve()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def solve():
  n, m = nm()
  G = [list() for _ in range(n)]
  for _ in range(m):
    a, b = nm()
    a -= 1; b -= 1
    G[a].append(b)
    G[b].append(a)
  Q = int(input())
  queries = [tuple(nm()) for _ in range(Q)][::-1]
  dp = [[Q]*11 for _ in range(n)]
  for i in range(Q-1, -1, -1):
    v, d, _ = queries[i]
    dp[v-1][d] = i
    
  for d in range(10, 0, -1):
    for v in range(n):
      for x in G[v] + [v]:
        if dp[x][d-1] > dp[v][d]:
          dp[x][d-1] = dp[v][d]
          
  queries.append((-1, -1, 0))
  color = [queries[dp[v][0]][2] for v in range(n)]
  print(*color, sep='\n')
  return

solve()

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, M = getlist()
	G = Graph()
	for i in range(M):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)

	DP = [[-1] * N for i in range(11)]
	Q_C = []
	Q = int(input())
	for i in range(Q):
		u, d, c = getlist()
		u -= 1
		Q_C.append(c)
		DP[10 - d][u] = i

	Q_C.append(0)

	#DP更新
	for i in range(10):
		for j in range(N):
			DP[i + 1][j] = max(DP[i + 1][j], DP[i][j])
			for k in G.graph[j]:
				DP[i + 1][k] = max(DP[i + 1][k], DP[i][j])
	
	for i in range(N):
		ind = DP[10][i]
		print(Q_C[ind])

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
edge=[[]for _ in range(n)]
color=[11*[0]for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
  edge[b].append(a)
q=int(input())
udc=[list(map(int,input().split()))for _ in range(q)][::-1]
for u,d,c in udc:
  x=u-1
  Q=[x]
  if color[x][d]:continue
  for k in range(d,-1,-1):
    if color[x][k]:break
    color[x][k]=c
  while Q and d!=-1:
    d-=1
    P=[]
    for i in Q:
      for j in edge[i]:
        if color[j][d]:continue
        for k in range(d,-1,-1):
          if color[j][k]:break
          color[j][k]=c
        P.append(j)
    Q=P
for i in color:print(i[0])

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*m]
    q = int(input())
    vdc = [list(map(int, input().split())) for _ in [0]*q]

    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]

    dist = [[0]*11 for _ in [0]*n]
    dist2 = [0]*n

    for v, d, c in vdc[::-1]:
        v -= 1
        if dist[v][d] != 0:
            continue
        dist[v][d] = c
        if dist2[v] == 0:
            dist2[v] = c
        if d > 0:
            q = [(v, d, c)]
            while q:
                v, d, c = q.pop()
                for i in g[v]:
                    if dist[i][d-1] == 0:
                        dist[i][d-1] = c
                        if dist2[i] == 0:
                            dist2[i] = c
                        if d > 1:
                            q.append((i, d-1, c))
    for i in dist2:
        print(i)


main()