Code Submission Evaluation System Login

Datatähti 2016 alku

Start:2015-09-28 00:00:00
End:2015-10-12 00:00:00
 

Tasks | Scoreboard | Statistics


CSES - Datatähti 2016 alku - Results
History
2015-10-11 23:55:1224
2015-10-11 23:52:090
2015-10-11 23:50:2961
2015-10-11 23:45:460
2015-10-10 19:51:3761
2015-10-10 19:50:470
2015-10-10 19:48:040
2015-10-10 18:54:0461
2015-10-10 16:10:3161
2015-10-10 16:09:550
2015-10-10 15:38:460
2015-10-10 15:07:5861
2015-10-10 12:10:1424
2015-10-10 12:09:1324
2015-10-10 12:08:270
2015-10-10 11:46:2424
2015-10-10 11:28:3961
2015-10-09 22:50:0761
2015-10-09 22:30:1561
2015-10-09 22:07:450
2015-10-04 15:53:3261
2015-10-04 15:28:140
2015-10-04 15:27:030
2015-10-04 15:23:500
2015-10-03 23:47:430
2015-10-03 23:33:050
2015-10-03 23:32:160
2015-10-03 21:42:070
2015-10-03 21:01:420
2015-10-03 20:23:290
2015-10-03 16:43:470
2015-10-03 16:34:590
2015-10-03 14:52:110
2015-10-03 14:37:050
2015-10-03 14:33:120
2015-10-03 14:26:220
2015-10-01 16:22:410
2015-09-29 21:15:440
2015-09-29 20:45:560
Task:Lennot
Sender:ollpu
Submission time:2015-10-11 23:50:29
Language:Python2
Status:READY
Score:61

Feedback

groupverdictscore
#1ACCEPTED24
#2ACCEPTED37
#3TIME LIMIT EXCEEDED0

Test results

testverdicttime (s)group
#1ACCEPTED0.06 / 1.001details
#2ACCEPTED0.06 / 1.001details
#3ACCEPTED0.06 / 1.001details
#4ACCEPTED0.07 / 1.001details
#5ACCEPTED0.07 / 1.001details
#6ACCEPTED0.06 / 1.002details
#7ACCEPTED0.06 / 1.002details
#8ACCEPTED0.06 / 1.002details
#9ACCEPTED0.06 / 1.002details
#10ACCEPTED0.06 / 1.002details
#11TIME LIMIT EXCEEDED-- / 1.003details
#12TIME LIMIT EXCEEDED-- / 1.003details
#13ACCEPTED0.95 / 1.003details
#14ACCEPTED0.79 / 1.003details
#15TIME LIMIT EXCEEDED-- / 1.003details
#16TIME LIMIT EXCEEDED-- / 1.003details
#17TIME LIMIT EXCEEDED-- / 1.003details

Code

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Epätoivoinen viimeinen yritys
import sys
from sys import stdin
maxint = sys.maxint
def readline():
    return stdin.readline().strip()
line1 = readline().split()
n = int(line1[0])
m = int(line1[1])
fl_from = 0
fl_to = 1
fl_price = 2
ct_total_price_even = 0
ct_even_price_set = 1
ct_total_price_odd = 2
ct_odd_price_set = 3
ct_total_price = 4
ct_calculated = 5
ct_con_to = 6
ct_in_uncalc = 7
ct_aid = 8
def minimum(a, b):
    if a < b:
        return a
    else:
        return b
def run():
    cities = map(lambda i: [maxint, False, maxint, False, maxint, False, [], False, i], xrange(n))
    int_ = int
    for f in xrange(m):
        row = readline().split()
        flight = (int_(row[0])-1, int_(row[1])-1, int_(row[2]))
        cities[flight[fl_from]][ct_con_to].append(flight)
    start = cities[0]
    end = cities[-1]
    current = start
    uncalculated = [current]
    append_to_uncalculated = uncalculated.append
    remove_from_uncalculated = uncalculated.remove
    current[ct_total_price_even] = 0
    current[ct_even_price_set] = True
    while True:
        if current[ct_aid] == end[ct_aid]:
            print(end[ct_total_price])
            break
        even_set = current[ct_even_price_set]
        even_cur = current[ct_total_price_even]
        odd_set = current[ct_odd_price_set]
        odd_cur = current[ct_total_price_odd]
        for flight in current[ct_con_to]:
            city = cities[flight[fl_to]]
            price_changed = False
            if even_set:
                new_odd_price = even_cur + flight[fl_price]
                if new_odd_price < city[ct_total_price_odd]:
                    city[ct_total_price_odd] = new_odd_price
                    city[ct_odd_price_set] = True
                    price_changed = True
            if odd_set:
                new_even_price = odd_cur
                if new_even_price < city[ct_total_price_even]:
                    city[ct_total_price_even] = new_even_price
                    city[ct_even_price_set] = True
                    price_changed = True
            if price_changed:
                city[ct_total_price] = minimum(city[ct_total_price_even], city[ct_total_price_odd])
                if city[ct_calculated]:
                    city[ct_calculated] = False
                    append_to_uncalculated(city)
                    city[ct_in_uncalc] = True
                elif not city[ct_in_uncalc]:
                    append_to_uncalculated(city)
                    city[ct_in_uncalc] = True
        remove_from_uncalculated(current)
        current[ct_calculated] = True
        smallest_price = maxint
        for city in uncalculated:
            cityprice = city[ct_total_price]
            if cityprice < smallest_price:
                smallest = city
                smallest_price = cityprice
        current = smallest
run()

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
10 20
2 1 3
7 6 4
1 6 7
1 6 1
...
view   save

correct output
8

view   save

user output
8

view   save

Test 2

Group: 1

Verdict: ACCEPTED

input
10 20
4 3 10
1 10 9
3 4 10
2 6 7
...
view   save

correct output
9

view   save

user output
9

view   save

Test 3

Group: 1

Verdict: ACCEPTED

input
10 20
5 7 4
6 1 1
7 3 8
8 4 2
...
view   save

correct output
8

view   save

user output
8

view   save

Test 4

Group: 1

Verdict: ACCEPTED

input
10 20
1 6 2
5 3 3
7 3 6
5 6 2
...
view   save

correct output
13

view   save

user output
13

view   save

Test 5

Group: 1

Verdict: ACCEPTED

input
10 20
10 8 5
2 4 7
9 4 7
9 4 1
...
view   save

correct output
4

view   save

user output
4

view   save

Test 6

Group: 2

Verdict: ACCEPTED

input
1000 2000
91 828 365044406
17 984 445675537
251 852 100987451
907 487 58830088
...
view   save

correct output
11893353673

view   save

user output
11893353673

view   save

Test 7

Group: 2

Verdict: ACCEPTED

input
1000 2000
722 939 530579090
404 606 268877348
133 750 760086153
506 46 582310443
...
view   save

correct output
30248963445

view   save

user output
30248963445

view   save

Test 8

Group: 2

Verdict: ACCEPTED

input
1000 2000
340 237 43690066
217 141 453160975
744 202 639037814
605 926 404985542
...
view   save

correct output
3126797692

view   save

user output
3126797692

view   save

Test 9

Group: 2

Verdict: ACCEPTED

input
1000 2000
88 312 190442306
480 402 411574469
29 901 397491243
636 459 323246996
...
view   save

correct output
18416073173

view   save

user output
18416073173

view   save

Test 10

Group: 2

Verdict: ACCEPTED

input
1000 2000
333 228 718389176
796 286 323493090
743 43 751876815
128 554 175625940
...
view   save

correct output
6399349335

view   save

user output
6399349335

view   save

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
100000 200000
28264 92686 186865663
92570 33956 925976418
87377 71249 644757113
16701 81203 922125505
...
view   save

correct output
518249578675

view   save

user output
(empty)

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
100000 200000
95740 71482 846654568
44131 16806 670712211
3967 49254 424174139
39369 53007 830346557
...
view   save

correct output
920862321580

view   save

user output
(empty)

Test 13

Group: 3

Verdict: ACCEPTED

input
100000 200000
79947 25489 71554257
59184 25577 328436360
82945 73554 4942918
22380 92385 874250042
...
view   save

correct output
399407698440

view   save

user output
399407698440

view   save

Test 14

Group: 3

Verdict: ACCEPTED

input
100000 200000
31139 12960 580545990
27744 95556 747296719
46969 42578 840321561
5638 28960 513805324
...
view   save

correct output
165235287505

view   save

user output
165235287505

view   save

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
99993 199980
1 3 1
3 2 1
1 4 1
4 2 1
...
view   save

correct output
2

view   save

user output
(empty)

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
100000 149994
93867 98509 1755709
85029 99843 1347591
10305 35305 6447
75638 80585 1829972
...
view   save

correct output
1124960

view   save

user output
(empty)

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
100000 200000
70413 71496 49
15963 40963 18635
81291 89420 1850028
8848 33848 17316
...
view   save

correct output
110298

view   save

user output
(empty)