CSES - Datatähti 2023 alku - Results
Submission details
Task:Sadonkorjuu
Sender:zli0122
Submission time:2022-11-13 13:13:54 +0200
Language:Python3 (PyPy3)
Status:READY
Result:33
Feedback
groupverdictscore
#1ACCEPTED33
#20
Test results
testverdicttimegroup
#1ACCEPTED0.04 s1, 2details
#2ACCEPTED0.04 s1, 2details
#3ACCEPTED0.04 s1, 2details
#4ACCEPTED0.04 s1, 2details
#5ACCEPTED0.04 s1, 2details
#6ACCEPTED0.11 s1, 2details
#7--2details
#8ACCEPTED0.11 s1, 2details
#9--2details
#10ACCEPTED0.10 s1, 2details
#11--2details
#12--2details
#13--2details
#14--2details
#15ACCEPTED0.10 s1, 2details
#16ACCEPTED0.11 s1, 2details
#17ACCEPTED0.10 s1, 2details
#18ACCEPTED0.11 s1, 2details
#19ACCEPTED0.10 s1, 2details
#20ACCEPTED0.11 s1, 2details
#21--2details
#22--2details
#23--2details
#24ACCEPTED0.10 s1, 2details
#25--2details
#26ACCEPTED0.10 s1, 2details
#27--2details
#28ACCEPTED0.10 s1, 2details
#29--2details
#30ACCEPTED0.11 s1, 2details
#31--2details

Code

#kiitos harppi-festareiden Aleksi Suhoselle kuulin tästä algoritmista.
class Kaupunki:
def __init__(self, tyyppi):
self.tyyppi = tyyppi
self.naapurit = []
self.etaisyydet = []
self.matka = 10**9
class Tie:
def __init__(self):
self.pituus = 0
self.paadyt = []
def dist(x):
return x.matka
def syote():
global n
n = int(input())
tyypit = [int(tyyppi) for tyyppi in input().split(" ")]
tiet = []
for i in range(n - 1):
userinput = [int(luku) for luku in input().split(" ")]
tie = Tie()
tie.paadyt = [indeksi - 1 for indeksi in userinput[:2]]
tie.pituus = userinput[2]
tiet.append(tie)
return tyypit, tiet
def sievenna(tyypit, tiet):
global n
kaupungeittain = [[] for i in range(n)]
for indeksi in range(n-1):
kaupungeittain[tiet[indeksi].paadyt[0]].append([tiet[indeksi].paadyt[1], tiet[indeksi].pituus])
kaupungeittain[tiet[indeksi].paadyt[1]].append([tiet[indeksi].paadyt[0], tiet[indeksi].pituus])
kaupungit = []
kiinnostavat = []
for indeksi in range(n):
kaupunki = Kaupunki(tyypit[indeksi])
kaupunki.naapurit = [luvut[0] for luvut in kaupungeittain[indeksi]]
kaupunki.etaisyydet = [luvut[1] for luvut in kaupungeittain[indeksi]]
if tyypit[indeksi] == 0:
kaupunki.matka = 0
kiinnostavat.append(kaupunki)
kaupungit.append(kaupunki)
for kaupunki in kaupungit:
kaupunki.naapurit = [kaupungit[indeksi] for indeksi in kaupunki.naapurit]
return kaupungit, kiinnostavat
def algoritmi(kaupungit, kiinnostavat, summa):
tarkasteltava = min(kiinnostavat, key=dist)
for indeksi in range(len(tarkasteltava.naapurit)):
naapuri = tarkasteltava.naapurit[indeksi]
if naapuri not in kaupungit:
continue
naapuri.matka = min(naapuri.matka, tarkasteltava.matka + tarkasteltava.etaisyydet[indeksi])
if naapuri not in kiinnostavat:
kiinnostavat.append(naapuri)
summa = summa + tarkasteltava.matka
kaupungit.remove(tarkasteltava)
kiinnostavat.remove(tarkasteltava)
return kaupungit, kiinnostavat, summa
def main():
tyypit, tiet = syote()
kaupungit, kiinnostavat = sievenna(tyypit, tiet)
summa = 0
while kaupungit != []:
kaupungit, kiinnostavat, summa = algoritmi(kaupungit, kiinnostavat, summa)
print(summa)
if __name__ == "__main__":
main()

Test details

Test 1

Group: 1, 2

Verdict: ACCEPTED

input
1
0

correct output
0

user output
0

Test 2

Group: 1, 2

Verdict: ACCEPTED

input
5
0 0 0 0 0
1 2 1
2 3 2
3 4 3
...

correct output
0

user output
0

Test 3

Group: 1, 2

Verdict: ACCEPTED

input
4
1 0 1 1
1 2 10
2 3 20
2 4 30

correct output
60

user output
60

Test 4

Group: 1, 2

Verdict: ACCEPTED

input
5
0 1 1 1 0
1 2 10
2 3 20
3 4 30
...

correct output
80

user output
80

Test 5

Group: 1, 2

Verdict: ACCEPTED

input
5
0 1 0 1 1
1 2 1
2 3 5
3 4 3
...

correct output
6

user output
6

Test 6

Group: 1, 2

Verdict: ACCEPTED

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
5506363

user output
5506363

Test 7

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1795118520

user output
(empty)

Test 8

Group: 1, 2

Verdict: ACCEPTED

input
1000
0 0 1 0 1 1 0 1 0 1 1 0 0 0 1 ...

correct output
293576

user output
293576

Test 9

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
816932444

user output
(empty)

Test 10

Group: 1, 2

Verdict: ACCEPTED

input
1000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
3089

user output
3089

Test 11

Group: 2

Verdict:

input
200000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
40839

user output
(empty)

Test 12

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
5683983203973

user output
(empty)

Test 13

Group: 2

Verdict:

input
200000
0 1 1 1 1 1 1 0 0 0 1 1 0 1 0 ...

correct output
58572993

user output
(empty)

Test 14

Group: 2

Verdict:

input
200000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
32755

user output
(empty)

Test 15

Group: 1, 2

Verdict: ACCEPTED

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
126238345

user output
126238345

Test 16

Group: 1, 2

Verdict: ACCEPTED

input
1000
0 0 0 1 0 1 1 1 0 0 1 0 1 1 0 ...

correct output
278678

user output
278678

Test 17

Group: 1, 2

Verdict: ACCEPTED

input
1000
1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 ...

correct output
34929

user output
34929

Test 18

Group: 1, 2

Verdict: ACCEPTED

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1543963

user output
1543963

Test 19

Group: 1, 2

Verdict: ACCEPTED

input
1000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
39606

user output
39606

Test 20

Group: 1, 2

Verdict: ACCEPTED

input
1000
1 0 1 0 1 0 0 0 0 1 1 0 0 0 1 ...

correct output
321598

user output
321598

Test 21

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
978670626

user output
(empty)

Test 22

Group: 2

Verdict:

input
200000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
375218

user output
(empty)

Test 23

Group: 2

Verdict:

input
200000
1 1 1 1 0 0 0 0 0 1 0 1 0 1 1 ...

correct output
60422556

user output
(empty)

Test 24

Group: 1, 2

Verdict: ACCEPTED

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
291990

user output
291990

Test 25

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
59607954

user output
(empty)

Test 26

Group: 1, 2

Verdict: ACCEPTED

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
990

user output
990

Test 27

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
199982

user output
(empty)

Test 28

Group: 1, 2

Verdict: ACCEPTED

input
1000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
7987

user output
7987

Test 29

Group: 2

Verdict:

input
200000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
3137875

user output
(empty)

Test 30

Group: 1, 2

Verdict: ACCEPTED

input
1000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
4657693

user output
4657693

Test 31

Group: 2

Verdict:

input
200000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1652889357

user output
(empty)