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

Code

import math
def I():
return map(int, input().split())
a = """6
1 1 0 0 1 1
1 2 20
2 3 30
2 5 50
3 6 60
1 4 10
""".splitlines()
# print(a)
# input = iter(a).__next__
def main():
n, = I()
cities = list(I())
connections = [dict() for _ in range(n)]
for i in range(n - 1):
a, b, c = I()
connections[a - 1][b - 1] = c
connections[b - 1][a - 1] = c
head = Node(None, 0, math.inf, cities[0])
city = head
while city is not None:
city.form_children(cities, connections)
city, going_up = city.next()
city = head
while city is not None:
new, going_up = city.next()
if new is None:
# city is the root, and has finished.
break
elif city.marker == 0: # new is city's parent
assert going_up
distance = city.distance
if new.closest > city.closest + distance:
new.closest = city.closest + distance
new.marker = 0 # resetting the node
city = new
else: # city is new's parent
assert not going_up
distance = new.distance
if new.closest > city.closest + distance:
new.closest = city.closest + distance
new.checked = False
if not new.checked:
city = new
new.checked = True
city = head
while city is not None:
city.confirm()
city, going_up = city.next()
total = 0
city = head
while city is not None:
new, going_up = city.next()
if going_up:
total += city.closest
city = new
print(total)
# print(head.view())
class Node:
def __init__(self, parent: "Node|None", id: int, distance: float, city_type: bool):
self.parent = parent
# if parent is not None:
# parent.children.append(self)
self.children: list[Node] = []
self.distance = distance
self.city_type = city_type
self.id = id
self.closest = math.inf if city_type else 0
self.formed_children = False
self.checked = False
def form_children(self, cities: list[bool], connections: list[dict[int, float]]):
if self.formed_children:
return
for city_id, distance in connections[self.id].items():
if (not self.parent) or city_id != self.parent.id:
self.children.append(Node(self, city_id, distance, cities[city_id]))
self.marker = 0
self.formed_children = True
def next(self):
"returns the next node, and True if going up, False is going down"
if self.marker < len(self.children):
self.marker += 1
return self.children[self.marker - 1], False
self.marker = 0
return self.parent, True
def confirm(self):
assert all(self.closest <= c.closest + c.distance for c in self.children)
assert self.parent is None or self.closest <= self.parent.closest + self.distance
def view(self, indent: int = 0):
out = ""
out += " " * indent + f"{self.id}: {self.closest}, {self.distance}" + "\n"
for c in self.children:
out += c.view(indent + 4)
return out
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)