Submission #50596739

---

Source Code Expand

import os
import sys
import gc
import heapq

sys.setrecursionlimit(210000)
gc.disable()


def debug(func):
    def wrapper(*args, **kwargs):
        if os.getenv('TEST'):
            return func(*args, **kwargs)
    return wrapper


@debug
def eprint(*args, **kwargs):
    print('[EPRINT]', *args, file=sys.stderr, **kwargs)


def main() -> None:
    N, M = map(int, input().split())
    schedules = [[] for _ in range(N)]
    for _ in range(M):
        L, D, K, C, A, B = map(int, input().split())
        schedules[B - 1].append((L, D, K, C, A - 1))

    departs = [-1 for _ in range(N)]
    queue = [(-10**20, N - 1)]
    heapq.heapify(queue)

    while len(queue) > 0:
        time, pos = heapq.heappop(queue)
        time = -time
        for schedule in schedules[pos]:
            l, d, k, c, a = schedule
            index = min((time - c - l) // d, k - 1)
            depart = l + index * d
            if depart < departs[a]:
                continue

            departs[a] = depart
            heapq.heappush(queue, (-depart, a))

    for depart in departs[:-1]:
        print(depart if depart > -1 else 'Unreachable')


if __name__ == '__main__':
    main()

Submission Info

Judge Result