CSES - Datatähti 2023 alku - Results
Submission details
Task:Sadonkorjuu
Sender:Finnduino
Submission time:2022-11-02 18:34:31 +0200
Language:Python3 (PyPy3)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#1ACCEPTED0.04 s1, 2details
#2ACCEPTED0.04 s1, 2details
#3ACCEPTED0.04 s1, 2details
#4ACCEPTED0.04 s1, 2details
#50.04 s1, 2details
#6--1, 2details
#7--2details
#80.15 s1, 2details
#9--2details
#100.12 s1, 2details
#11--2details
#12--2details
#13--2details
#14--2details
#15ACCEPTED0.42 s1, 2details
#160.13 s1, 2details
#170.12 s1, 2details
#180.21 s1, 2details
#190.12 s1, 2details
#200.14 s1, 2details
#21--2details
#22--2details
#23--2details
#240.16 s1, 2details
#25--2details
#260.17 s1, 2details
#27--2details
#28ACCEPTED0.16 s1, 2details
#29--2details
#30ACCEPTED0.33 s1, 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 1
def Distance(nodeList):
totalDistance = 0
for nodeIndex in range(0,len(nodeList)-1):
totalDistance += connection(nodeList[nodeIndex], nodeList[nodeIndex+1])
return totalDistance
for i in range(0, CityCount):
#Checking if is a producer node, not a port node
totalDistance = 0
subPath = 0
pathDistances = {}
if(CityStates[i] == "1"):
visitingNode = i
nodeCache = i
#Loop stays true until port is found
portfound = False
visitedNodes = [False]*(CityCount)
nodeHistory = [i]
smallestWeight = math.inf
smallestWeightNode = 0
while(not portfound):
nothing = True
#Cycle through neighbors
for neighbor in RoadDict[visitingNode]:
unvisitedNodes = [x[0] for x in RoadDict[visitingNode]]
#If port is found, end the search
if(CityStates[int(neighbor[0])] =="0"):
#Port found!
nodeHistory.append(int(neighbor[0]))
portfound, nothing = True, False
elif(int(neighbor[1]) < smallestWeight and not visitedNodes[int(neighbor[0])]):
smallestWeight = int(neighbor[1])
smallestWeightNode = int(neighbor[0])
nothing = False
if(not portfound and not nothing):
smallestWeight = math.inf
visitedNodes[visitingNode] = True
nodeHistory.append(int(smallestWeightNode))
visitingNode = smallestWeightNode
elif(nothing):
visitedNodes[nodeHistory[-2]] = False
visitedNodes[nodeHistory[-1]] = True
smallestWeight = math.inf
visitingNode = nodeHistory[-1]
nodeHistory = nodeHistory[:-2]
totalDistances += Distance(nodeHistory)
print(totalDistances)

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:

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

correct output
6

user output
7

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
302341

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:

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

correct output
3089

user output
3094

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:

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

correct output
278678

user output
319350

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
35954

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
1782457

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
39699

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
335124

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
428875

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
4520

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)