CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko
Sender:okkokko
Submission time:2021-10-14 18:22:43 +0300
Language:Python3 (PyPy3)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.04 s1, 2, 3details
#20.14 s2, 3details
#3--3details

Code

def GetInput(inp):
n = int(inp())
# out=collections.defaultdict(lambda:[])
out=[[] for i in range(n+1)]
for i in range(n-1):
c0,c1,c2=map(int,inp().split())
out[c0].append((c1,c2))
out[c1].append((c0,c2))
return out
###outputs 88
# testInput="""8
# 1 3 8
# 2 1 5
# 4 2 11
# 5 2 2
# 6 5 8
# 7 4 1
# 8 5 5
# """
deb=False
if deb:
import time
with open('C:\\Users\\Okko Heiniö\\Desktop\\Koulu\\Vuosi 3\\Datatähti\\Eexample.txt','r') as fr:
exampleInput=fr.read()
pass
ei = iter(exampleInput.splitlines()).__next__
print(time.perf_counter())
else:
ei=input
koneet=GetInput(ei)
totalHalf=0
# print(time.perf_counter())
# defa = collections.defaultdict(int)
# def combineFork(haarat):
# a=defa.copy()
# for h in haarat:
# for k,v in h.items():
# a[k]+=v
# return a
def addFork(original,haara):
for k,v in haara.items():
original[k]=original.get(k,0) + v
return original
def clampSelfValue(h):
addTotalHalf=0
# s=tuple(h.keys())
# for i in range(len(h)):
# for j in range(i):
# addTotal+=min(s[j],s[i])*h[s[j]]*h[s[i]]
s=sorted(h.keys())
ta=0
tb=sum(h.values())
for k in s:
# for j in range(i):
ta+=k*h[k]
tb-=h[k]
addTotalHalf+=(ta+tb*k)*h[k]
return addTotalHalf
def clampSelfValueDifference(h,sourceSpeed):
"max(h)<sourceSpeed ---> clampSelfValue(h)-clampSelfValue(h+{sourceSpeed:1}) = sourceSpeed"
# return sum((k*v for k,v in h.items()))*2
# addTotal=0
# for k in h:
# addTotal+=-k*h[k]
# return addTotal*2
# clampSelfValue(h)-clampSelfValue(h+{sourceSpeed:1})
# ta=sum((k*v for k,v in h.items()))
addTotalHalf=sourceSpeed
return addTotalHalf
def clampTo(h,sourceSpeed):
"""in pseudocode:
y = h[0:sourceSpeed]
y[sourceSpeed]=sum(h[sourceSpeed:]) + 1"""
y = {sourceSpeed:1}
for k,v in h.items():
if sourceSpeed<=k:
y[sourceSpeed]+=v
else:
y[k]=v
return y
def CombineHaarat(yhtyhaarat,sourceSpeed):
if not yhtyhaarat:
return {sourceSpeed:1},sourceSpeed
if True:# max(yhtyhaarat.keys())<sourceSpeed:
"addTotalHalf=clampSelfValueDifference(yhtyhaarat,sourceSpeed)"
yhtyhaarat[sourceSpeed]=1
return yhtyhaarat,sourceSpeed
else:
y=clampTo(yhtyhaarat,sourceSpeed)
addTotalHalf=clampSelfValue(yhtyhaarat)-clampSelfValue(y)+sum((k*v for k,v in y.items()))*2
return y,addTotalHalf
# def Crossroads(kone,source,sourceSpeed):
# haarat=[]
# for k,v in koneet[kone]:
# if k==source:
# continue
# haarat.append(Crossroads(k,kone,v))
# co=CombineHaarat(combineFork(haarat),sourceSpeed)
# global totalHalf
# totalHalf+=co[1]
# return co[0]
def CrossroadsLoop(kone):
addTotalHalf=0
path=[(0,0),(0,0),(kone,0)]
haaratPath=[{},{},{}]
# for k,v in koneet[kone]:
# if k==source:
# continue
# haarat.append(Crossroads(k,kone,v))
run=True
while len(path)>2:
while koneet[path[-1][0]]:
newPath,speed = koneet[path[-1][0]].pop()
if newPath==path[-2][0]:
pass
else:
path.append((newPath,speed))
haaratPath.append({})
co=CombineHaarat(haaratPath[-1],path[-1][1])
addFork(haaratPath[-2],co[0])
addTotalHalf+=co[1]
haaratPath.pop()
path.pop()
global totalHalf
totalHalf = addTotalHalf
CrossroadsLoop(1)
# print(time.perf_counter())
totalHalf=totalHalf//2
print(totalHalf)
# print("inaccuracy:",totalHalf-980176904750134603)

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
2485

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
1253900882303

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)