CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko (Network)
Sender:Kirill_Akimov
Submission time:2021-10-17 20:18:22
Language:CPython3
Status:READY
Result:10
Feedback
groupverdictscore
#1ACCEPTED10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.03 s1, 2, 3details
#2--2, 3details
#3--3details

Code

from array import array

n = int(input())
graph = {}

s = 0
   

for _ in range(n-1):
    a, b, x = [int(e) for e in input().split()]
    if a in graph:
        graph[a][b] = x
    else:
        graph[a] = {b: x}
    if b in graph:
        graph[b][a] = x
    else:
        graph[b] = {a: x}




l = array('I', [])

def count(v, p):
    global s
    global graph
    global l

    length = len(l)
    d = {}
    for i in range(length):
        if l[i] > graph[v][p]:
            d[i] = l[i]
            l[i] = graph[v][p]

        
    if p > 0:
        l.append(graph[v][p])
        s += sum(l)

    
    for key in graph[v]:
        if key != p:
            count(key, v)

    for key in d:
        l[key] = d[key]

    current = len(l)
    if p > 0:
        for i in range(length + 1, len(l)):
            if l[i] > graph[v][p]:
                l[i] = graph[v][p]


count(1, 0)


print(s)


    

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
1 2 74
1 3 100
2 4 50
3 5 40
...

correct output
88687

user output
88687

Test 2

Group: 2, 3

Verdict:

input
5000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1103702320243776

user output
(empty)

Test 3

Group: 3

Verdict:

input
200000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1080549209850010931

user output
(empty)