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

Code

#import math
#import numpy
import math
CityCount = int(input())
CityStates = input().split()
RoadList = []
#Build a nested array of roads
for n in range(0,CityCount-1):
temp = input().split()
RoadList.append(temp)
#Convert to numpy array
#RoadMatrix = numpy.array(RoadList)
RoadDict = {}
#Cycle through roads to find ones that connect to a given node, then build a dictionary which indexes each connected road
for a in range(0,CityCount):
tempList = []
#Roads
for b in range(0, CityCount-1):
if(int(RoadList[b][0]) == a+1):
tempList.append([int(RoadList[b][1])-1,int(RoadList[b][2])])
elif(int(RoadList[b][1]) == a+1):
tempList.append([int(RoadList[b][0])-1,int(RoadList[b][2])])
#Cycle them through again, rearraging them in ascending weight
for b in range(0, len(tempList)):
tempList.sort(key= lambda x: x[1])
RoadDict[a] = tempList
#Actually find something
currentNode = 0
nodeDistances = [0]+[math.inf]*(CityCount-1)
totalDistances = 0
unvisited_nodes = [x for x in range(CityCount)]
#shortest_path = {}
#previous_nodes = {}
#start_node = 0
def connection(node, target):
node = node
target = target
for con in RoadDict[node]:
if(int(con[0]) == target):
return int(con[1])
return 0
def Neighbors(node):
return RoadDict[node]
def Distance(nodeList):
totalDistance = 0
for nodeIndex in range(0,len(nodeList)-1):
totalDistance += connection(nodeList[nodeIndex], nodeList[nodeIndex+1])
return totalDistance
class Tree():
def __init__(self, parent, history):
self.parent = parent
self.children = []
self.history = history
def addChild(self, child):
self.children.append(child)
class Node():
def __init__(self, nodeVal) -> None:
self.value = nodeVal
self.root = None
def setParent(self, root):
self.root = root
def __repr__(self) -> str:
return
#Initialize nodes:
NodeList = []
for i in range(0, CityCount):
NodeList.append(Node(i))
bingus=[]
EndNode = [[] for _ in range(CityCount)]
sum = 0
for startingNode in NodeList:
#treeList = []
node = startingNode
startingNodevalue = startingNode.value
travelledNodes = [False]*CityCount
#nodeIterator = 0
Queue = []
Queue.append(startingNode)
NodeStates = {}
travelledNodes[startingNodevalue] = True
if CityStates[startingNodevalue] == "0":
EndNode[startingNodevalue].append(startingNode)
else:
while Queue:
node = Queue[0]
#root = Tree(node, None)
Queue.pop(0)
smallestWeight = math.inf
smallestWeightNode = 0
portNotFound = True
#newSmallest = False
#if CityStates[node.value] == "0":
#Found a port
#print(EndNode)
# portNotFound = False
for neighbor in RoadDict[node.value]:
neighborNode = NodeList[neighbor[0]]
if(not travelledNodes[neighbor[0]]):
# neighborNode.setParent(node)
travelledNodes[neighbor[0]] = True
Queue.append(neighborNode)
neighborNode.setParent(node)
if(CityStates[neighbor[0]] == "0"):
EndNode[startingNode.value].append(neighborNode)
DistanceIterator = 0
smallestDistance = math.inf
for leaf in EndNode[startingNodevalue]:
cahceNode = leaf
wtfdistance = 0
lastNode = cahceNode.value
Distances = []
distance = 0
while True:
if cahceNode.value == startingNodevalue:
#distance += connection(cahceNode.value, lastNode)
for con in RoadDict[cahceNode.value]:
if con[0] == lastNode:
distance += con[1]
break
break
#print(distance, " , for node ", startingNode.value)
else:
for con in RoadDict[cahceNode.value]:
if con[0] == lastNode:
distance += con[1]
break
lastNode = cahceNode.value
cahceNode = cahceNode.root
if smallestDistance > distance:
smallestDistance = distance
#DistanceIterator +=1
sum += smallestDistance
# print(smallestDistance)
print(sum)

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:

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

correct output
5506363

user output
(empty)

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:

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

correct output
293576

user output
(empty)

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:

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

correct output
126238345

user output
(empty)

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)

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)

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)

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)

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)

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:

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

correct output
291990

user output
(empty)

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:

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

correct output
990

user output
(empty)

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:

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

correct output
7987

user output
(empty)

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:

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

correct output
4657693

user output
(empty)

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)