CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko
Sender:okkokko
Submission time:2021-10-11 16:23:22 +0300
Language:CPython3
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.03 s1, 2, 3details
#20.23 s2, 3details
#3--3details

Code


def GetInput():
    n = int(input())
    out=[(n,)]
    for i in range(n-1):
        a = input()
        out.append(tuple([int(b) for b in a.split()]))
    return out
# exampleInput="""4
# 1 2 5
# 2 3 1
# 2 4 2
# """.splitlines()
# exampleInput=[tuple([int(b) for b in a.split()]) for a in exampleInput]
I=GetInput()
# I=exampleInput
# print(I)
# print(exampleInput)
n=I[0][0]
# yhteys voidaan kuvata virtaavan vain yhteen suuntaan? parin suuremmassa yksilössä on referenssi pienempään, 
# ja kun mennään koneiden listan läpi, mennään pienimmästä suurimpaan.
# voidaan huomata että ei ole mahdollista olla ympyröitä, joten jokaisesta koneesta on vain yksi reitti
koneet={}

for i in range(1,n):
    yhteys = I[i]
    b,a=yhteys[0:2]
    koneet.setdefault(yhteys[0],{})[yhteys[1]]=yhteys[2]
    koneet.setdefault(yhteys[1],{})[yhteys[0]]=yhteys[2]

# print(koneet)

def Crossroads(kone,source,sourceSpeed):
    # sourceSpeed = koneet[kone][source]
    haarat=[]
    addTotal=0
    for i in koneet[kone].keys()-{source}:
        speed=koneet[i][kone]
        c = Crossroads(i,kone,speed)
        haarat.append(c[0])
        addTotal+=c[1]+speed

    yhteydet={sourceSpeed:1}
    for i in range(len(haarat)):
        yh=haarat[i]
        for j in yh.keys():
            if j<sourceSpeed:
                yhteydet.setdefault(j,0)
                yhteydet[j]+=yh[j]
            else:
                yhteydet[sourceSpeed]+=yh[j]
    
    for i in range(len(haarat)):
        for j in range(len(haarat)):
            if j<i:
                for k in haarat[i].keys():
                    # clampSpeeds_update(sisainen,haarat[j][0],k,)
                    multiplier=haarat[i][k]
                    yh=haarat[j]
                    for l in yh.keys():
                        addTotal+=yh[l]*min(l,k)*multiplier
    # yhteydet = {siirtonopeus:määrä}
    # addTotal = summaan lisättävä arvo joka tulee haaran välisistä yhteyksistä, + haarasta aiemmat addTotal
    return yhteydet,addTotal

# def clampSpeeds_update(out,yh:dict,maxSpeed,multiplier):
    # out.setdefault(maxSpeed,0)
    # for j in yh.keys():
    #     if j<maxSpeed:
    #         out.setdefault(j,0)+=yh[j]*multiplier
    #     else:
    #         out[maxSpeed]+=yh[j]*multiplier
    # return out


b1,b2,b3=0,0,0
for i in koneet.keys():
    if len(koneet[i])==1:
        b1=list(koneet[i].keys())[0]
        b2=i
        b3=koneet[i][b1]

an= Crossroads(b1,b2,b3)

# print(an)

a=an[0]

total=an[1]
for i in a.keys():
    total+=a[i]*i
print(total)#-(10**9)

Test details

Test 1

Group: 1, 2, 3

Verdict:

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

correct output
88687

user output
74925

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
1093202231400212

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)