Submission #2373992


Source Code Expand

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

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

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

memo = [[0] * (10+1) for i in range(N+1)]


def paint(v, d, i):
    # すでに塗られていたらもう先は見ない
    if memo[v][d]:
        return

    # 塗られていなければ何番目の操作で色が塗られたかを覚えておく
    memo[v][d] = i

    # 距離-1は存在しないので終了ストッパー
    if d == 0:
        return

    # 何番目の操作で色が塗られたかを0まで伝播
    paint(v, d-1, i)

    # 今見ているところの隣接頂点について同じことをやりにいく
    # ただし離れるにつれて届く範囲は1ずつ減っていく
    for u in Adj[v]:
        paint(u, d-1, i)


# 逆順にクエリを処理
for q in range(Q-1, -1, -1):
    paint(v[q], d[q], q+1)


for i in range(1, N+1):
    # 操作が加わった形跡があれば、それが何番目の操作であるか確認し、その操作に該当する色を取りに行く
    if memo[i][0] != 0:
        print(c[memo[i][0]-1])
    else:
        print(0)

Submission Info

Submission Time
Task B - Splatter Painting
User AT274
Language Python (3.4.3)
Score 700
Code Size 1329 Byte
Status AC
Exec Time 1723 ms
Memory 47188 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 200 / 200 500 / 500
Status
AC × 2
AC × 19
AC × 35
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt
Subtask1 00_example_01.txt, 00_example_02.txt, 10_01.txt, 10_02.txt, 10_03.txt, 10_04.txt, 10_05.txt, 10_06.txt, 10_07.txt, 10_08.txt, 10_09.txt, 10_10.txt, 10_11.txt, 10_12.txt, 10_13.txt, 10_14.txt, 10_15.txt, 10_16.txt, 10_17.txt
All 00_example_01.txt, 00_example_02.txt, 10_01.txt, 10_02.txt, 10_03.txt, 10_04.txt, 10_05.txt, 10_06.txt, 10_07.txt, 10_08.txt, 10_09.txt, 10_10.txt, 10_11.txt, 10_12.txt, 10_13.txt, 10_14.txt, 10_15.txt, 10_16.txt, 10_17.txt, 20_01.txt, 20_02.txt, 20_03.txt, 20_04.txt, 20_05.txt, 20_06.txt, 20_07.txt, 20_08.txt, 20_09.txt, 20_10.txt, 20_11.txt, 20_12.txt, 20_13.txt, 20_14.txt, 20_15.txt, 20_16.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 17 ms 3064 KB
00_example_02.txt AC 17 ms 3064 KB
10_01.txt AC 22 ms 3064 KB
10_02.txt AC 17 ms 3064 KB
10_03.txt AC 17 ms 3064 KB
10_04.txt AC 17 ms 3064 KB
10_05.txt AC 23 ms 3064 KB
10_06.txt AC 17 ms 3064 KB
10_07.txt AC 21 ms 3704 KB
10_08.txt AC 42 ms 4184 KB
10_09.txt AC 43 ms 4184 KB
10_10.txt AC 42 ms 4188 KB
10_11.txt AC 42 ms 4208 KB
10_12.txt AC 42 ms 4212 KB
10_13.txt AC 33 ms 4052 KB
10_14.txt AC 30 ms 3956 KB
10_15.txt AC 28 ms 3928 KB
10_16.txt AC 44 ms 4212 KB
10_17.txt AC 46 ms 4212 KB
20_01.txt AC 1633 ms 46608 KB
20_02.txt AC 1670 ms 46500 KB
20_03.txt AC 1628 ms 46452 KB
20_04.txt AC 286 ms 8548 KB
20_05.txt AC 41 ms 3688 KB
20_06.txt AC 205 ms 26824 KB
20_07.txt AC 45 ms 3740 KB
20_08.txt AC 284 ms 7432 KB
20_09.txt AC 42 ms 3824 KB
20_10.txt AC 265 ms 6796 KB
20_11.txt AC 366 ms 9636 KB
20_12.txt AC 757 ms 36196 KB
20_13.txt AC 1250 ms 42876 KB
20_14.txt AC 1310 ms 43448 KB
20_15.txt AC 1713 ms 47188 KB
20_16.txt AC 1723 ms 47116 KB