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: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n, m = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]

ans = [0] * n
q = I()
Q = LIR(q)
dq = deque()
depth = [-1] * n

def dfs(u, d, c):
    if d <= depth[u]:
        return
    depth[u] = d
    if ans[u] == 0:
        ans[u] = c
    if d == 0:
        return
    for v in G[u]:
        dfs(v, d - 1, c)

for x, y, z in Q[::-1]:
    dfs(x - 1, y, z)

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n, m = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]

ans = [0] * n
q = I()
Q = LIR(q)
dq = deque()
depth = [-1] * n
for v, d, c in Q[::-1]:
    if depth[v - 1] >= d:
        continue
    if ans[v - 1] == 0:
        ans[v - 1] = c
    depth[v - 1] = d
    if d:
        dq += [v - 1]
    while dq:
        u = dq.popleft()
        for x in G[u]:
            if ans[x] == 0:
                ans[x] = c
            if depth[x] >= depth[u] - 1:
                continue
            depth[x] = depth[u] - 1
            if depth[x]:
                dq += [x]

print(*ans, sep="\n")

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n, m = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]

ans = [0] * n
q = I()
Q = LIR(q)
dq = deque()
depth = [-1] * n
for v, d, c in Q[::-1]:
    if depth[v - 1] >= d:
        continue
    if ans[v - 1] == 0:
        ans[v - 1] = c
    depth[v - 1] = d
    dq += [v - 1]
    while dq:
        u = dq.popleft()
        for x in G[u]:
            if depth[x] >= depth[u] - 1:
                continue
            depth[x] = depth[u] - 1
            if ans[x] == 0:
                ans[x] = c
            if depth[u] - 1 == 0:
                continue
            dq += [x]

print(*ans, sep="\n")

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n, m = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]

ans = [0] * n
q = I()
Q = LIR(q)
dq = deque()
depth = [-1] * n
for v, d, c in Q[::-1]:
    if depth[v - 1] >= d:
        continue
    if ans[v - 1] == 0:
        ans[v - 1] = c
    depth[v - 1] = d
    dq += [v - 1]
    while dq:
        u = dq.popleft()
        for x in G[u]:
            if depth[x] >= depth[u] - 1:
                continue
            depth[x] = depth[u] - 1
            if ans[x] == 0:
                ans[x] = c
            if depth[x]:
                dq += [x]

print(*ans, sep="\n")

Submission status: Accepted

Solution code:
#b
#上で再起の代わりにナイーブに配列内の値を埋めていく。
#aこのほうがちょい早い。

#b
#by using the condition d<=10, we should memorize V*d whether the pair is already searched.
#if searched, we can stop.
#まだ遅い。TLE.

n,m = [int(i) for i in input().split()]
edges = [[] for _ in range(n)]
colors = [0]*n

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

for _ in range(m):
    a,b = [int(i) for i in input().split()]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    

def dfs(d,v,c):
    if checker[v][d] != 0 or d<0:
        return
    #d>=0 and (v,d) is not checked
    if colors[v]==0: #not colored yet
        colors[v] = c
        
    #ここよ
    for j in range(d+1):
        checker[v][j] = 1
        
        
    nodes=edges[v]
    for u in nodes:
        dfs(d-1, u, c)

    
q = int(input())
info = []
for _ in range(q):
    v,d,c = [int(i) for i in input().split()]
    info.append((v-1,d,c))
    
info.reverse()
for tupple in info:
    v,d,c = tupple
    
    #not bfs but dfs
    dfs(d,v,c)
    
for i in range(n):
    print(colors[i])

Submission status: Accepted

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

def main():
  n, m = map(int, input().split())
  G = [[] for _ in range(n)]
  for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
  q = int(input())
  vdc = [list(map(int, input().split())) for _ in range(q)][::-1]
  dp = [[0]*11 for _ in range(n)]
  def dfs(v, d, c):
    if dp[v][d]:
      return dp[v][d]
    if d == 0:
      dp[v][d] = c
      return
    for u in G[v]:
      dfs(u, d-1, c)
    dfs(v, d-1, c)
    dp[v][d] = c
  for v, d, c in vdc:
    dfs(v-1, d, c)
  for i in range(n):
    print(dp[i][0])
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

def main():
  n, m = map(int, input().split())
  G = [[] for _ in range(n)]
  for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
  q = int(input())
  vdc = [list(map(int, input().split())) for _ in range(q)][::-1]
  dp = [[0]*11 for _ in range(n)]
  def dfs(v, d, c):
    if dp[v][d]:
      return dp[v][d]
    if d == 0:
      dp[v][d] = c
      return
    for u in G[v]:
      dfs(u, d-1, c)
    dfs(v, d-1, c)
    dp[v][d] = c
  for v, d, c in vdc:
    dfs(v-1, d, c)
  for i in range(n):
    print(dp[i][0])
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  G[a].append(b)
  G[b].append(a)
q = int(input())
vdc = [list(map(int, input().split())) for _ in range(q)][::-1]
dp = [[0]*11 for _ in range(n)]
def dfs(v, d, c):
  if dp[v][d]:
    return dp[v][d]
  if d == 0:
    dp[v][d] = c
    return
  for u in G[v]:
    dfs(u, d-1, c)
  dfs(v, d-1, c)
  dp[v][d] = c
for v, d, c in vdc:
  dfs(v-1, d, c)
for i in range(n):
  print(dp[i][0])

Submission status: Accepted

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


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]


graph = [[] for i in range(n)]
for a, b in info:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    
query = query[::-1]

dp = [-1] * (n * (10 + 1))
# dp = [[-1] * (10 + 1) for i in range(n)]
# [v][d] -> [v * 11 + d]
first = [0] * n

def solve(v, d, c):
    if d < 0 or dp[v * 11 + d] != -1:
        return
      
    dp[v * 11 + d] = c
    if first[v] == 0:
        first[v] = c

    solve(v, d - 1, c)
    for u in graph[v]:
        solve(u, d - 1, c)
    return
  

for v, d, c in query:
    v -= 1
    solve(v, d, c)

for i in range(n):
    print(first[i])

Submission status: Accepted

Solution code:
# 写経AC
N,M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
Q = int(input())
VDC = [[int(i) for i in input().split()] for _ in range(Q)]

for i in range(Q):
    VDC[i][0] -= 1

color = [0] * N
# visited[v][d]: 頂点vから距離d以下は塗装済みか
visited = [[False] * 11 for _ in range(N)]

for v,d,c in reversed(VDC):
    if visited[v][d]: # 既に塗装済み
        continue
    if color[v] == 0:
        color[v] = c
    for dist in range(d + 1):
        # 距離d以下は塗装済み
        visited[v][dist] = True
    
    q = [v]
    for t in range(d - 1, -1, -1):
        qq = []
        for v in q:
            for w in edge[v]:
                if visited[w][t]:
                    continue
                for dist in range(t + 1):
                    visited[w][dist] = True
                if color[w] == 0:
                    color[w] = c
                qq.append(w)
        q = qq

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

Submission status: Accepted

Solution code:
# 写経AC
N,M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
Q = int(input())
VDC = [[int(i) for i in input().split()] for _ in range(Q)]

for i in range(Q):
    VDC[i][0] -= 1

color = [0] * N
# dp[v][d]: 頂点vから距離dは塗装済みか
visited = [[False] * 11 for _ in range(N)]

for v,d,c in reversed(VDC):
    if visited[v][d]: # 既に塗装済み
        continue
    if color[v] == 0:
        color[v] = c
    for dist in range(d + 1):
        # 距離d以下は塗装済み
        visited[v][dist] = True
    
    q = [v]
    for t in range(d - 1, -1, -1):
        qq = []
        for v in q:
            for w in edge[v]:
                if visited[w][t]:
                    continue
                for dist in range(t + 1):
                    visited[w][dist] = True
                if color[w] == 0:
                    color[w] = c
                qq.append(w)
        q = qq

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)

for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
mxd = 0
res = [[-1] * 11 for _ in range(N + 1)]
Q = int(input())
qd = [0] * Q
qc = [0] * Q
for i in range(Q):
  v, d, c = map(int, input().split())
  qd[i] = d
  qc[i] = c
  res[v][d] = i
  mxd = max(mxd, d)
#print(qc)

#print(mxd)
for t in range(mxd):
  tres = [x[: ] for x in res]
  for x in range(1, N + 1):
    for y in e[x]:
      for i in range(t + 1, 11):
        res[y][i] = max(res[y][i], tres[x][i])

#print(res)
for r in res[1: ]:
  x = -1
  for i in range(11):
    if r[i] != -1: x = max(x, r[i])
  if x == -1: print(0)
  else: print(qc[x])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n)]
for a,b in ab:
  a -= 1
  b -= 1
  graph[a].append(b)
  graph[b].append(a)
q = int(input())
query = [list(map(int,input().split())) for i in range(q)]
query = query[::-1]
depth = [-1 for i in range(n)]
color = [0 for i in range(n)]
stack = []
for v,d,c in query:
  v -= 1
  if depth[v] < d:
    stack.append((v,d))
  while stack:
    x,dep = stack.pop()
    if color[x] == 0:
      color[x] = c
    for y in graph[x]:
      if depth[y] < dep-1:
        stack.append((y,dep-1))
        depth[y] = dep-1
print(*color,sep="\n")

Submission status: Accepted

Solution code:
from collections import deque

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

C = [0] * N
D = [-1] * N
for v, d, c in vdc[::-1] :
  q = deque([(v - 1, d, c)])
  while q :
    cv, cd, cc = q.popleft()
    if D[cv] >= cd :
      continue
    D[cv] = cd
    if C[cv] == 0 :
      C[cv] = cc
    for nv in ab[cv] :
      q.append((nv, cd - 1, cc))

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

Submission status: Accepted

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

INF = 10**14

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

maxd = 0
Q = int(input())
Query = []
Color = []
for _ in range(Q):
    v, d, c = map(int, input().split())
    if d > maxd:
        maxd = d
    Query.append((v-1, d))
    Color.append(c)

Query = Query[::-1]
Color = Color[::-1]

dp = [[INF]*(maxd+1) for _ in range(N)]
for i, (v, d) in enumerate(Query):
    if i < dp[v][d]:
        dp[v][d] = i

for d in reversed(range(maxd)):
    for v in range(N):
        if dp[v][d+1] < dp[v][d]:
            dp[v][d] = dp[v][d+1]
        for nv in graph[v]:
            if dp[v][d+1] < dp[nv][d]:
                dp[nv][d] = dp[v][d+1]

for v in range(N):
    seq = dp[v][0]
    if seq == INF:
        print(0)
    else:
        print(Color[seq])

Submission status: Accepted

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

INF = 10**14

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

maxd = 0
Q = int(input())
Query = []
Color = []
for _ in range(Q):
    v, d, c = map(int, input().split())
    if d > maxd:
        maxd = d
    Query.append((v-1, d))
    Color.append(c)

Query = Query[::-1]
Color = Color[::-1]

dp = [[INF]*(maxd+1) for _ in range(N)]
for i, (v, d) in enumerate(Query):
    if i < dp[v][d]:
        dp[v][d] = i

for d in reversed(range(maxd)):
    for v in range(N):
        if dp[v][d+1] < dp[v][d]:
            dp[v][d] = dp[v][d+1]
        for nv in graph[v]:
            if dp[v][d+1] < dp[nv][d]:
                dp[nv][d] = dp[v][d+1]

for v in range(N):
    seq = dp[v][0]
    if seq == INF:
        print(0)
    else:
        print(Color[seq])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[u].append(v)
        E[v].append(u)

    q=int(input())
    VDC=[None]*q
    for i in range(q):
        v,d,c=map(int,input().split())
        v-=1
        VDC[i]=(v,d,c)
    VDC.reverse()

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

    for v,d,c in VDC:
        Q=deque([(v,d)])
        dp[v][d]=1
        while(Q):
            v,d=Q.popleft()
            if(d>0):
                if(not dp[v][d-1]):
                    dp[v][d-1]=1
                    Q.append((v,d-1))
                for nv in E[v]:
                    if(dp[nv][d-1]): continue
                    dp[nv][d-1]=1
                    Q.append((nv,d-1))
            if(ans[v]==0):
                ans[v]=c

    print(*ans,sep='\n')
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[u].append(v)
        E[v].append(u)

    q=int(input())
    VDC=[None]*q
    for i in range(q):
        v,d,c=map(int,input().split())
        v-=1
        VDC[i]=(v,d,c)
    VDC.reverse()

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

    for v,d,c in VDC:
        Q=deque([(v,d)])
        dp[v][d]=1
        while(Q):
            v,d=Q.popleft()
            if(d>0):
                Q.append((v,d-1))
                for nv in E[v]:
                    if(dp[nv][d-1]): continue
                    dp[nv][d-1]=1
                    Q.append((nv,d-1))
            if(ans[v]==0):
                ans[v]=c

    print(*ans,sep='\n')
resolve()

Submission status: Accepted

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

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

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

Q = int(readline())
VDC = [map(int, readline().split()) for _ in range(Q)]
VDC.reverse()

table = [-1]*N
Col = [[0]*11 for _ in range(N)]
for v, d, c in VDC:
    v -= 1
    if table[v] >= d:
        continue
    Q = deque([(v, d)])
    while Q:
        vn, dn = Q.pop()
        Col[vn][dn] = c
        table[vn] = dn
        for vf in Edge[vn]:
            if table[vf] < dn-1:
                Q.appendleft((vf, dn-1))
Ans = [0]*N
for i in range(N):
    for j in range(11):
        if Col[i][j]:
            Ans[i] = Col[i][j]
            break
print('\n'.join(map(str, Ans)))

Submission status: Accepted

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


def main():
    n, m = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(m)]
    edges = [[] for _ in range(n)]
    for a, b in ab:
        edges[a - 1].append(b - 1)
        edges[b - 1].append(a - 1)
    
    q = int(input())
    ans = [0 for _ in range(n)]
    dd = [-1 for _ in range(n)]
    vdc = [tuple(map(int, input().split())) for _ in range(q)]
    for v, d, c in vdc[::-1]:
        if dd[v - 1] >= d:
            #  v - 1 から距離 d の部分は塗りつぶされているため無視
            continue
        
        node = set()
        node.add(v - 1)
        while d >= 0 and len(node) > 0:
            next_node = set()
            for u in node:
                if dd[u] >= d:
                    continue
                dd[u] = d
                if ans[u] == 0:
                    ans[u] = c
                for v in edges[u]:
                    if dd[v] < d - 1:
                        next_node.add(v)
            node = next_node
            d -= 1
    
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    n, m = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(m)]
    edges = [[] for _ in range(n)]
    for a, b in ab:
        edges[a - 1].append(b - 1)
        edges[b - 1].append(a - 1)
    
    q = int(input())
    ans = [0 for _ in range(n)]
    dd = [-1 for _ in range(n)]
    vdc = [tuple(map(int, input().split())) for _ in range(q)]
    for v, d, c in vdc[::-1]:
        if dd[v - 1] >= d:
            #  v - 1 から距離 d の部分は塗りつぶされているため無視
            continue
        
        node = []
        node.append(v - 1)
        while d >= 0 and len(node) > 0:
            next_node = []
            while len(node) > 0:
                u = node.pop()
                if dd[u] >= d:
                    continue
                dd[u] = d
                if ans[u] == 0:
                    ans[u] = c
                for v in edges[u]:
                    if dd[v] < d - 1:
                        next_node.append(v)
            node = next_node
            d -= 1
    
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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, M = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
Q = int(sys.stdin.buffer.readline())
VDC = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(Q)]

# 解説AC
graph = [[] for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

# dp[v, d]: v から距離 d の頂点を塗るタイミングと色
dp = [[None] * 11 for _ in range(N)]
for i, (v, d, c) in reversed(list(enumerate(VDC))):
    v -= 1
    if not dp[v][d]:
        dp[v][d] = i, c

for d in reversed(range(1, 11)):
    for v in range(N):
        if not dp[v][d]:
            continue
        for u in graph[v] + [v]:
            if not dp[u][d - 1] or (dp[u][d - 1] and dp[u][d - 1][0] < dp[v][d][0]):
                dp[u][d - 1] = dp[v][d]

for v in range(N):
    if dp[v][0]:
        print(dp[v][0][1])
    else:
        print(0)

# import numpy as np
# dp = np.array(dp)
# print(dp)

Submission status: Accepted

Solution code:
def main():
	n, m, *L = map(int, open(0).read().split())
	AB = L[:2 * m]
	Q = L[2 * m + 1:][::-1]
	G = [[] for _ in range(n)]
	C = [0] * n
	D = [-1] * n
	for a, b in zip(*[iter(AB)] * 2):
		a -= 1
		b -= 1
		G[a] += [b]
		G[b] += [a]
	for c, d, v in zip(*[iter(Q)] * 3):
		if D[v - 1] >= d:
			continue
		D[v - 1] = d
		q = [v - 1]
		while q:
			cur = q.pop()
			dd = D[cur]
			if not C[cur]:
				C[cur] = c
			if not dd:
				continue
			for nxt in G[cur]:
				if D[nxt] >= dd - 1:
					continue
				D[nxt] = dd - 1
				q.append(nxt)
	print("\n".join(map(str, C)))

if __name__=="__main__":
	main()

Submission status: Accepted

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

N, M = map(int, input().split())
adj = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)
Q = int(input())
qs = []
for _ in range(Q):
    v, d, c = map(int, input().split())
    qs.append((v, d, c))
qs.reverse()

seen = [-1] * (N+1)
ans = [0] * (N+1)
for v0, d0, c in qs:
    if d0 > seen[v0]:
        que = deque()
        que.append((v0, d0))
        seen[v0] = d0
        while que:
            v, d = que.popleft()
            if ans[v] == 0:
                ans[v] = c
            if d > 0:
                for u in adj[v]:
                    if d-1 > seen[u]:
                        que.append((u, d-1))
                        seen[u] = d-1

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
E = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
Q = int(input())
VDC = [list(map(int, input().split())) for _ in range(Q)]
Ans = [0] * (N+1)
D = [-1] * (N+1)

def dfs(v, d, c):
    if D[v] >= d:
        return
    D[v] = d
    if Ans[v]==0:
        Ans[v] = c
    for u in E[v]:
        dfs(u, d-1, c)

for v, d, c in VDC[::-1]:
    dfs(v, d, c)

print("\n".join(map(str, Ans[1:])))

Submission status: Accepted

Solution code:
from collections import deque

def main():
    N, M, *L = map(int, open(0).read().split())

    E = [[] for _ in range(N + 1)]
    for a, b in zip(*[iter(L[:2 * M])] * 2):
        E[a].append(b)
        E[b].append(a)

    colors = [0] * (N + 1)
    visited = [-1] * (N + 1)

    for v, d, c in reversed(tuple(zip(*[iter(L[2 * M + 1:])] * 3))):
        Q = deque([(d, v)])
        while Q:
            cnt, v = Q.popleft()
            if visited[v] >= cnt:
                continue
            if colors[v] == 0:
                colors[v] = c
            visited[v] = cnt
            if cnt > 0:
                Q.extend((cnt - 1, u) for u in E[v] if visited[u] < cnt - 1)

    for c in colors[1:]:
        print(c)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
    N, M, *L = map(int, open(0).read().split())

    E = [[] for _ in range(N + 1)]
    for a, b in zip(*[iter(L[:2 * M])] * 2):
        E[a].append(b)
        E[b].append(a)

    colors = [0] * (N + 1)
    visited = [-1] * (N + 1)

    for v, d, c in reversed(tuple(zip(*[iter(L[2 * M + 1:])] * 3))):
        Q = deque([(d, v)])
        while Q:
            cnt, v = Q.popleft()
            if visited[v] >= cnt:
                continue
            if colors[v] == 0:
                colors[v] = c
            visited[v] = cnt
            if cnt > 0:
                Q.extend((cnt - 1, u) for u in E[v])

    for c in colors[1:]:
        print(c)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

N, M, *L = map(int, open(0).read().split())
AB, VDC = L[:2 * M], L[2 * M + 1:]

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)
    E[b].append(a)

colors = [0] * (N + 1)
visited = [-1] * (N + 1)

for v, d, c in reversed(tuple(zip(*[iter(VDC)] * 3))):
    Q = deque([(d, v)])
    while Q:
        cnt, v = Q.popleft()
        if visited[v] >= cnt:
            continue
        if colors[v] == 0:
            colors[v] = c
        visited[v] = cnt
        if cnt > 0:
            Q.extend((cnt - 1, u) for u in E[v])

for c in colors[1:]:
    print(c)

Submission status: Accepted

Solution code:
from collections import deque

N, M, *L = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(L[:2 * M])] * 2):
    E[a].append(b)
    E[b].append(a)

colors = [0] * (N + 1)
visited = [-1] * (N + 1)

for v, d, c in reversed(tuple(zip(*[iter(L[2 * M + 1:])] * 3))):
    Q = deque([(d, v)])
    while Q:
        cnt, v = Q.popleft()
        if visited[v] >= cnt:
            continue
        if colors[v] == 0:
            colors[v] = c
        visited[v] = cnt
        if cnt > 0:
            Q.extend((cnt - 1, u) for u in E[v])

for c in colors[1:]:
    print(c)

Submission status: Accepted

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

N,M = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(M)]
Q = int(input())
VDC = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

color = [0] * (N+1)
visited = [[False] * 11 for _ in range(N+1)]
# 残り体力 x で訪れた
# 10で訪れたら、9,8,7も埋める

for v,d,c in VDC[::-1]:
    if visited[v][d]:
        continue
    if color[v] == 0:
        color[v] = c
    for i in range(d+1):
        visited[v][i] = True
    q = [v]
    for t in range(d-1,-1,-1):
        qq = []
        for v in q:
            for w in graph[v]:
                if visited[w][t]:
                    continue
                for i in range(t+1):
                    visited[w][i] = True
                if color[w] == 0:
                    color[w] = c
                qq.append(w)
        q = qq

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