CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko
Sender:EeliH
Submission time:2021-10-07 00:14:30 +0300
Language:Python3 (PyPy3)
Status:READY
Result:25
Feedback
groupverdictscore
#1ACCEPTED10
#2ACCEPTED15
#30
Test results
testverdicttimegroup
#1ACCEPTED0.05 s1, 2, 3details
#2ACCEPTED0.50 s2, 3details
#3--3details

Code

n = int(input())
yhteydet = []
naapurit = []
def maara(tietokone, pois):
m = 1
for naapuri in naapurit[tietokone]:
if naapuri != pois:
m += maara(naapuri, tietokone)
return m
for i in range(n+1):
naapurit.append([])
for i in range(n - 1):
arr = list(map(int, input().split()))
yhteys = {"a": arr[0], "b": arr[1], "nopeus": arr[2]}
yhteydet.append(yhteys)
naapurit[arr[0]].append(arr[1])
naapurit[arr[1]].append(arr[0])
yhteydet = sorted(yhteydet, key=lambda k: k['nopeus'])
summa = 0
for yhteys in yhteydet:
a = yhteys["a"]
b = yhteys["b"]
m1 = maara(b, a)
naapurit[b].remove(a)
naapurit[a].remove(b)
m2 = maara(a, b) - 1
r = m1 * (m2 + 1) * yhteys["nopeus"]
summa += r
print(summa)

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

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

correct output
1103702320243776

user output
1103702320243776

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)