Task: | Tietoverkko |
Sender: | okkokko |
Submission time: | 2021-10-14 18:22:43 +0300 |
Language: | Python3 (PyPy3) |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | WRONG ANSWER | 0 |
#3 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | WRONG ANSWER | 0.04 s | 1, 2, 3 | details |
#2 | WRONG ANSWER | 0.14 s | 2, 3 | details |
#3 | TIME LIMIT EXCEEDED | -- | 3 | details |
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=Falseif deb:import timewith open('C:\\Users\\Okko Heiniö\\Desktop\\Koulu\\Vuosi 3\\Datatähti\\Eexample.txt','r') as fr:exampleInput=fr.read()passei = iter(exampleInput.splitlines()).__next__print(time.perf_counter())else:ei=inputkoneet=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 adef addFork(original,haara):for k,v in haara.items():original[k]=original.get(k,0) + vreturn originaldef 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=0tb=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 addTotalHalfdef 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=sourceSpeedreturn addTotalHalfdef 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]+=velse:y[k]=vreturn ydef CombineHaarat(yhtyhaarat,sourceSpeed):if not yhtyhaarat:return {sourceSpeed:1},sourceSpeedif True:# max(yhtyhaarat.keys())<sourceSpeed:"addTotalHalf=clampSelfValueDifference(yhtyhaarat,sourceSpeed)"yhtyhaarat[sourceSpeed]=1return yhtyhaarat,sourceSpeedelse:y=clampTo(yhtyhaarat,sourceSpeed)addTotalHalf=clampSelfValue(yhtyhaarat)-clampSelfValue(y)+sum((k*v for k,v in y.items()))*2return 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=0path=[(0,0),(0,0),(kone,0)]haaratPath=[{},{},{}]# for k,v in koneet[kone]:# if k==source:# continue# haarat.append(Crossroads(k,kone,v))run=Truewhile len(path)>2:while koneet[path[-1][0]]:newPath,speed = koneet[path[-1][0]].pop()if newPath==path[-2][0]:passelse: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 totalHalftotalHalf = addTotalHalfCrossroadsLoop(1)# print(time.perf_counter())totalHalf=totalHalf//2print(totalHalf)# print("inaccuracy:",totalHalf-980176904750134603)
Test details
Test 1
Group: 1, 2, 3
Verdict: WRONG ANSWER
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: WRONG ANSWER
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: TIME LIMIT EXCEEDED
input |
---|
200000 1 2 613084013 1 3 832364259 2 4 411999902 3 5 989696303 ... |
correct output |
---|
1080549209850010931 |
user output |
---|
(empty) |