oj.uz

Submission #559053

# Submission time Handle Problem Language Result Execution time Memory
559053 2022-05-09T10:11:33 Z jh05013 Price List (POI13_cen) Python 3
40 / 100
 4000 ms 65276 KB 
from heapq import *
import sys;input=lambda:sys.stdin.readline().strip('\n')
MIS = lambda: map(int,input().split())
 
n, m, source, c1, c2 = MIS()
adj = [set() for i in range(n+1)]
adj2 = [set() for i in range(n+1)]
for i in range(m):
    a, b = MIS()
    adj[a].add(b); adj[b].add(a)
    adj2[a].add(b); adj2[b].add(a)
 
dist = [10**18]*(n+1); dist[source] = 0
PQ = [(0, source)]
while PQ:
    d, u = heappop(PQ)
    if dist[u] != d: continue
    for v in adj[u]:
        # edge type 1
        nd = d+c1
        if dist[v] > nd:
            dist[v] = nd; heappush(PQ, (nd, v))
        # edge type 2
        nd = d+c2
        to_remove = []
        for v2 in adj2[v]:
            if v2 in adj[u] or dist[v2] <= nd: continue
            dist[v2] = nd; heappush(PQ, (nd, v2))
            to_remove.append(v2)
        for v2 in to_remove: adj2[v].remove(v2)
print(*dist[1:], sep='\n')

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2976 KB Output is correct
2 Correct 20 ms 2920 KB Output is correct
3 Correct 16 ms 2896 KB Output is correct
4 Correct 17 ms 2912 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2972 KB Output is correct
2 Correct 15 ms 3040 KB Output is correct
3 Correct 17 ms 3036 KB Output is correct
4 Correct 19 ms 3032 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3276 KB Output is correct
2 Correct 21 ms 3324 KB Output is correct
3 Correct 24 ms 3360 KB Output is correct
4 Correct 21 ms 3356 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 10424 KB Output is correct
2 Correct 168 ms 10360 KB Output is correct
3 Correct 141 ms 11624 KB Output is correct
4 Correct 137 ms 11440 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4062 ms 30132 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4094 ms 47292 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4075 ms 55384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4097 ms 63304 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1907 ms 60400 KB Output is correct
2 Correct 1994 ms 60484 KB Output is correct
3 Correct 995 ms 57556 KB Output is correct
4 Correct 934 ms 51220 KB Output is correct
5 Execution timed out 4061 ms 65020 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 914 ms 62804 KB Output is correct
2 Correct 947 ms 62268 KB Output is correct
3 Correct 1092 ms 62808 KB Output is correct
4 Correct 952 ms 51316 KB Output is correct
5 Execution timed out 4075 ms 65276 KB Time limit exceeded
6 Halted 0 ms 0 KB -