CSES - Datatähti 2023 alku - Results
Submission details
Task:Sadonkorjuu
Sender:okkokko
Submission time:2022-11-05 02:16:45 +0200
Language:Python3 (PyPy3)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#10.07 s1, 2details
#20.07 s1, 2details
#30.07 s1, 2details
#40.07 s1, 2details
#50.07 s1, 2details
#60.07 s1, 2details
#70.07 s2details
#80.07 s1, 2details
#90.07 s2details
#100.07 s1, 2details
#110.07 s2details
#120.07 s2details
#130.07 s2details
#140.07 s2details
#150.07 s1, 2details
#160.07 s1, 2details
#170.07 s1, 2details
#180.07 s1, 2details
#190.07 s1, 2details
#200.07 s1, 2details
#210.07 s2details
#220.07 s2details
#230.07 s2details
#240.07 s1, 2details
#250.07 s2details
#260.07 s1, 2details
#270.07 s2details
#280.07 s1, 2details
#290.07 s2details
#300.07 s1, 2details
#310.07 s2details

Code

# test 1 succeeds
import math
import random
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)
def generate_test(n: int):
port_chance = 0.2
def text_gen():
yield str(n)
random.seed(1001)
yield " ".join(str(int(random.random() > port_chance)) for _ in range(n))
for i in range(2, n + 1):
yield " ".join(map(str, (i, random.randrange(1, i), random.randint(1, 100))))
return text_gen().__next__
# input = iter(a).__next__
# input = generate_test(100)
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
head.form_children(cities, connections)
while city is not None:
new = city.next()
if new is None:
# city is the root, and has finished.
break
elif city.marker == 0: # new is city's parent
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
distance = new.distance
if new.closest > city.closest + distance:
new.closest = city.closest + distance
city = new
if not new.checked:
city = new
new.checked = True
city.form_children(cities, connections)
total = 0
city = head
while city is not None:
new = city.next()
if not city.marker:
total += city.closest
city = new
# print(head.view())
print(total)
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):
if self.marker < len(self.children):
self.marker += 1
return self.children[self.marker - 1]
self.marker = 0
return self.parent
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:

input
1
0

correct output
0

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

Test 2

Group: 1, 2

Verdict:

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

correct output
0

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

Test 3

Group: 1, 2

Verdict:

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

correct output
60

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

Test 4

Group: 1, 2

Verdict:

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

correct output
80

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

Test 5

Group: 1, 2

Verdict:

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

correct output
6

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

Test 6

Group: 1, 2

Verdict:

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

correct output
5506363

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

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)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

Test 8

Group: 1, 2

Verdict:

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

correct output
293576

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

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)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

Test 10

Group: 1, 2

Verdict:

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

correct output
3089

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

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)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

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)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

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)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

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)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

Test 15

Group: 1, 2

Verdict:

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

correct output
126238345

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

Test 16

Group: 1, 2

Verdict:

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

correct output
278678

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

Test 17

Group: 1, 2

Verdict:

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

correct output
34929

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

Test 18

Group: 1, 2

Verdict:

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

correct output
1543963

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

Test 19

Group: 1, 2

Verdict:

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

correct output
39606

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

Test 20

Group: 1, 2

Verdict:

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

correct output
321598

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

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)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

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)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

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)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

Test 24

Group: 1, 2

Verdict:

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

correct output
291990

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

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)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

Test 26

Group: 1, 2

Verdict:

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

correct output
990

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

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)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

Test 28

Group: 1, 2

Verdict:

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

correct output
7987

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

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)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

Test 30

Group: 1, 2

Verdict:

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

correct output
4657693

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...

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)

Error:
Traceback (most recent call last):
  File "input/code.py", line 80, in <module>
    class...