32152023-02-22 17:07:3512BotiMúzeumi őrökpython3Time limit exceeded 28/40680ms31092 KiB
import heapq
from bisect import bisect

n, e, u = map(int, input().split())
os = [list(map(int, input().split())) + [idx] for idx in range(n)]
os.sort()
done = [False] * n
parent = [-1] * n

heap = [(cost, end, idx) for idx, (start, end, cost, _) in enumerate(os) if start == e]
heapq.heapify(heap)

while len(heap) > 0:
    # print(heap)
    # print(parent)
    cost, end, idx = heapq.heappop(heap)
    if done[idx]:
        continue
    done[idx] = True
    if end >= u:
        print(cost)
        l = []
        while idx != -1:
            l.append(os[idx][3] + 1)
            # print(os[idx])
            idx = parent[idx]
        l.reverse()
        print(len(l), *l)
        exit()
    for i in range(idx + 1, n):
        if os[i][0] > end + 1:
            break
        if done[i] or parent[i] != -1:
            continue
        parent[i] = idx
        heapq.heappush(heap, (cost + os[i][2], os[i][1], i))

print("-1")
SubtaskSumTestVerdictTimeMemory
base28/40
1Accepted0/019ms11528 KiB
2Accepted0/0149ms17620 KiB
3Accepted1/118ms12076 KiB
4Accepted3/318ms12232 KiB
5Accepted2/218ms12596 KiB
6Accepted2/218ms12524 KiB
7Accepted2/218ms12644 KiB
8Accepted2/218ms13220 KiB
9Accepted2/218ms13404 KiB
10Time limit exceeded0/2680ms30404 KiB
11Time limit exceeded0/2667ms30636 KiB
12Accepted2/220ms14036 KiB
13Accepted2/278ms15972 KiB
14Partially correct1/3104ms18156 KiB
15Accepted3/3128ms18996 KiB
16Time limit exceeded0/2652ms30984 KiB
17Time limit exceeded0/2666ms31092 KiB
18Partially correct1/218ms14008 KiB
19Partially correct1/218ms14228 KiB
20Accepted2/218ms14388 KiB
21Accepted2/218ms14488 KiB