| Show all threads Hide all threads Show all messages Hide all messages |
| hint | -`~ | 1379. Cups Transportation | 28 May 2024 23:12 | 1 |
hint -`~ 28 May 2024 23:12 binsearch + dijkstra works but with naive dijkstra |
| WA #8 | Maxim | 1379. Cups Transportation | 30 Dec 2023 20:03 | 1 |
WA #8 Maxim 30 Dec 2023 20:03 Can you send to me some test????????)) |
| WA#2 | Zubyk Taras(Khmelnitsky) | 1379. Cups Transportation | 24 Jul 2017 14:21 | 5 |
WA#2 Zubyk Taras(Khmelnitsky) 7 May 2006 02:33 Give me some tests. PLEASE. Re: WA#2 Georgiy Savchenko 29 Oct 2006 12:06 And what is the correct answer for this test? |
| TLE on #46 | Talgat | 1379. Cups Transportation | 18 Apr 2016 05:37 | 2 |
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... |
| why TLE using bfs | rushel | 1379. Cups Transportation | 30 May 2012 01:42 | 5 |
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 |
| WA#37 | A-shot | 1379. Cups Transportation | 4 Oct 2011 00:51 | 1 |
WA#37 A-shot 4 Oct 2011 00:51 Have anybody had a WA at this test? I use BinarySearch and Delkstra, but it fails at this test... |
| WA#12 | wRabbits_AlMag(VNTU) | 1379. Cups Transportation | 14 Jul 2011 04:28 | 1 |
WA#12 wRabbits_AlMag(VNTU) 14 Jul 2011 04:28 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? |
| WA10 | Baurzhan | 1379. Cups Transportation | 26 Oct 2009 16:53 | 1 |
WA10 Baurzhan 26 Oct 2009 16:53 why wa? can somebody give me 10 test? i use binary search+dijkstra |
| WA24 who can give me tests or say where was mistake in you? | Alexander_Yakubenko | 1379. Cups Transportation | 23 Apr 2008 20:12 | 3 |
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 |
| WA#7 | ExPerT | 1379. Cups Transportation | 27 Oct 2007 02:31 | 2 |
WA#7 ExPerT 16 Jun 2007 20:20 I don't understand why my program is wrong.
Please help me. Give me some hints or tests.
Thanks Re: WA#7 marius dumitran 27 Oct 2007 02:31 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.... |
| WA #4 | Novopolotsk Lyceum | 1379. Cups Transportation | 7 Aug 2006 15:32 | 3 |
WA #4 Novopolotsk Lyceum 7 Aug 2006 02:15 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 Re: WA #4 Novopolotsk Lyceum 7 Aug 2006 15:32 Ok! Thanks!
I will try it.
I sent my e-mail to you. |
| For those who gets WA #2 AND ADMINS! | it4.kp | 1379. Cups Transportation | 23 Jul 2006 05:36 | 3 |
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. |
| Can someone give me a hint?I think minimum cost maximum flow is wrong. | semiconductor | 1379. Cups Transportation | 23 Dec 2005 17:37 | 4 |
Thanks for reply.
Binary answer? |
| are the roads bidirectional? | Barnaul_School42_4 | 1379. Cups Transportation | 11 Sep 2005 22:35 | 2 |
|
