|
|
binsearch + dijkstra works but with naive dijkstra Can you send to me some test????????)) Give me some tests. PLEASE. 1 0 And what is the correct answer for this test? I'm using BS + Dijkstra but I'm getting TLE, why? I optimized solution by using edges that have capacity >= 3 * 10^6, implemented BS with iterations (without "while"), but keep getting TLE. I had TLE 46 when i was checking for time[N] <= 1440 only after my BFS was complete. But when i moved this condition inside my BFS, to check on it after getting every new wave of vertices, i got AC in 0.078! Truly surprising, wasn't expecting to make that much difference by moving a single line. My BFS shouldn't really be that bad either... I use bfs where a state is defined by node and time. Is my approach is wrong? please help me. ??? Edited by author 12.09.2005 15:55 Time is integer in 0..1440, We have about 500^2 edges, So 1440*500*500 ~ 4*10^8 (it's of course too big time :) And you think it can get not TLE? Try to invent faster algorithm. BFS is possible if you enhance it doing several tricks. My AC is 0.265 sec, 5421KB, 85 LOC I think you mean Ford-Bellman with queue. 0.625 AC. But i have many operations with vectors resize. I think this solve can work faster. Edited by author 30.05.2012 01:53 Have anybody had a WA at this test? I use BinarySearch and Delkstra, but it fails at this test... Explain, please, why do i have AC, searching from [0..(1<<24)] but WA#12 searching just those values that are present in the input? why wa? can somebody give me 10 test? i use binary search+dijkstra this is my general code: Procedure Solve; var L,R,M : LongInt; BeGiN L:=0; R:=10000001; While R - L > 1 do Begin M:=(L + R) shr 1; if Can(M) then L:=M else R:=M; End; While (Can(L + 1)) and (L < 10000000) do Inc(L); Answer:=L; EnD; Who see mistake??? --- Sorry my English is Bad:) [code deleted] Edited by moderator 05.12.2023 19:55 My reason for WA # 24 was a bug in code of reading data You need to change a(i,j) AND a(j,i). I didn't do that and had WA. What's more, here are some tests if anebody needs: 4 5 1 4 1000 3001000 1 2 440 3001200 1 3 449 3001500 3 2 1 3001500 2 4 990 3001500 answer 15 4 5 1 4 1000 3001000 1 2 440 3001200 1 3 450 3001500 3 2 1 3001500 2 4 990 3001500 answer 12 I don't understand why my program is wrong. Please help me. Give me some hints or tests. Thanks i had WA7 too try this test 2 1 1 1 0 0 answer 0 my binary search was going funny:) from (0 to -3000:))) ) good things can't come from this.... Please, give me some tests and/or hints!!! Thanks!!! Hey Denis!!! Its only dijkstra + binary search... [code deleted] Please give me your mail My : andrey_tk@tut.by Edited by moderator 08.08.2006 17:35 Ok! Thanks! I will try it. I sent my e-mail to you. This code: ... int l=0, h=10000000, mid; while (l+1<h) { mid=(l+h)/2; if (can(mid))l=mid; else h=mid; } ... gets WA #2 but this one: ... int l=0, h=10000001, mid; while (l+1<h) { mid=(l+h)/2; if (can(mid))l=mid; else h=mid; } ... gets AC! Feel the diference! TO ADMINS: Problem statement says road capacity < 10^9, so we'll never be able to deliver 10^7 cups, since truck weights 3*10^6 grammes. But obviously answer on TEST #2 is 10^7. Fix it, please. There is no number in the input files that exceeds 10^9. The tests are absolutely correct. The answer for the second test is 10^7. But it is possible when N=1. P.S. It is a common mistake. Always test your program on boundary tests. Well, technically you are right. But let's take a look at the problem statement... First, we can see phrase: "Of course, it is impossible to deliver 10000000 cups (this is the amount of cups ordered by organizing committee) in a ONE trip." And then the output format: "Print the only number: the total amount of the cups (it must be as much as possible), which can be delivered in the FIRST trip of the truck in a time of 24 hours." After that I don't think answer 10^7 is full of sense. And why to write all that story with delivering cups if N=1? IMO problem statement should not be tricky. Thanks for reply. Binary answer? |
|
|