CSES - Datatähti 2023 alku - Results
Submission details
Task:Sadonkorjuu
Sender:Ihminen
Submission time:2022-11-13 21:32:16 +0200
Language:Python3 (PyPy3)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#1ACCEPTED0.05 s1, 2details
#2ACCEPTED0.05 s1, 2details
#3ACCEPTED0.05 s1, 2details
#4ACCEPTED0.05 s1, 2details
#5ACCEPTED0.05 s1, 2details
#60.13 s1, 2details
#7--2details
#8ACCEPTED0.90 s1, 2details
#9--2details
#10--1, 2details
#11--2details
#120.74 s2details
#13--2details
#14--2details
#150.11 s1, 2details
#16ACCEPTED0.43 s1, 2details
#17ACCEPTED0.59 s1, 2details
#18ACCEPTED0.99 s1, 2details
#19--1, 2details
#20ACCEPTED0.92 s1, 2details
#21--2details
#22--2details
#23--2details
#24--1, 2details
#25--2details
#26ACCEPTED0.97 s1, 2details
#27--2details
#28ACCEPTED0.12 s1, 2details
#29--2details
#30ACCEPTED0.15 s1, 2details
#31--2details

Code

from collections import defaultdict
import sys
pieninmatka = [9999] * 200000
satamat = []
class Heap():
def __init__(self):
self.array = []
self.size = 0
self.pos = []
def newMinHeapNode(self, v, dist):
minHeapNode = [v, dist]
return minHeapNode
def swapMinHeapNode(self, a, b):
t = self.array[a]
self.array[a] = self.array[b]
self.array[b] = t
def minHeapify(self, idx):
smallest = idx
left = 2 * idx + 1
right = 2 * idx + 2
if (left < self.size and
self.array[left][1]
< self.array[smallest][1]):
smallest = left
if (right < self.size and
self.array[right][1]
< self.array[smallest][1]):
smallest = right
if smallest != idx:
self.pos[self.array[smallest][0]] = idx
self.pos[self.array[idx][0]] = smallest
self.swapMinHeapNode(smallest, idx)
self.minHeapify(smallest)
def extractMin(self):
if self.isEmpty() == True:
return
root = self.array[0]
lastNode = self.array[self.size - 1]
self.array[0] = lastNode
self.pos[lastNode[0]] = 0
self.pos[root[0]] = self.size - 1
self.size -= 1
self.minHeapify(0)
return root
def isEmpty(self):
return True if self.size == 0 else False
def decreaseKey(self, v, dist):
i = self.pos[v]
self.array[i][1] = dist
while (i > 0 and self.array[i][1] <
self.array[(i - 1) // 2][1]):
self.pos[self.array[i][0]] = (i - 1) // 2
self.pos[self.array[(i - 1) // 2][0]] = i
self.swapMinHeapNode(i, (i - 1) // 2)
i = (i - 1) // 2;
def isInMinHeap(self, v):
if self.pos[v] < self.size:
return True
return False
class Graph():
def __init__(self, V):
self.V = V
self.graph = defaultdict(list)
def addEdge(self, src, dest, weight):
newNode = [dest, weight]
self.graph[src].insert(0, newNode)
newNode = [src, weight]
self.graph[dest].insert(0, newNode)
def dijkstra(self, src):
V = self.V
dist = []
minHeap = Heap()
for v in range(V):
dist.append(1e7)
minHeap.array.append(minHeap.
newMinHeapNode(v, dist[v]))
minHeap.pos.append(v)
minHeap.pos[src] = src
dist[src] = 0
minHeap.decreaseKey(src, dist[src])
minHeap.size = V;
while minHeap.isEmpty() == False:
newHeapNode = minHeap.extractMin()
u = newHeapNode[0]
for pCrawl in self.graph[u]:
v = pCrawl[0]
if (minHeap.isInMinHeap(v) and
dist[u] != 1e7 and \
pCrawl[1] + dist[u] < dist[v]):
dist[v] = pCrawl[1] + dist[u]
if pieninmatka[v] > dist[v]:
pieninmatka[v] = dist[v]
minHeap.decreaseKey(v, dist[v])
kaupunkiMäärä = int(input())
graph = Graph(kaupunkiMäärä)
rivi = input()
väli = rivi.split()
for i in range(len(väli)):
if int(väli[i]) == 0:
satamat.append(i)
for i in range(0, kaupunkiMäärä - 1):
väli = input()
rivi = väli.split()
graph.addEdge(int(rivi[0]) - 1, int(rivi[1]) - 1, int(rivi[2]));
for k in range(len(satamat)):
graph.dijkstra(satamat[k])
laskuri = 0
for j in range(0, kaupunkiMäärä):
ei = False
for t in range(len(satamat)):
if(j == satamat[t]):
ei = True
break
if ei == False:
laskuri += pieninmatka[j]
print(laskuri)

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
5506183

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:

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

correct output
3089

user output
(empty)

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
1999608787

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
9788123

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:

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: 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:

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: 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)