| Show all threads Hide all threads Show all messages Hide all messages |
| Test Case | এসো নবীন দলে দলে, ছাত্রলীগের পতাকাতলে। | 1505. Oil Transfer | 31 May 2018 14:51 | 2 |
Test Case এসো নবীন দলে দলে, ছাত্রলীগের পতাকাতলে। 16 Sep 2016 13:44 4
2 3 2 11.
.
2 3 0 10, 4 3 0 19.
. Answer: Impossible
Source: AC program |
| tests | Slobodan | 1505. Oil Transfer | 31 May 2018 14:50 | 3 |
tests Slobodan 16 Jun 2008 04:40 4
2 0 0 47, 3 17 17 25, 4 0 0 38.
1 17 17 31, 3 0 0 23, 4 0 0 96.
1 0 0 96, 2 0 0 48, 4 17 17 91.
.
=
69
2 0, 3 17, 4 1.
1 18, 3 0, 4 0.
1 0, 2 0, 4 17.
.
8
.
1 0 0 39, 5 13 13 21.
5 0 0 87, 8 41 41 92.
5 38 38 85.
6 41 41 14, 8 10 10 49.
2 10 10 69, 3 41 41 58, 4 0 0 73.
6 3 3 59.
.
=
49
.
1 0, 5 13.
5 0, 8 41.
5 38.
6 40, 8 11.
2 10, 3 41, 4 0.
6 3.
.
Edited by author 16.06.2008 04:40 Why not
4
2 0 0 47, 3 17 17 25, 4 0 0 38.
1 17 17 31, 3 0 0 23, 4 0 0 96.
1 0 0 96, 2 0 0 48, 4 17 17 91.
.
=
61
2 0, 3 16, 4 1.
1 17, 3 1, 4 0.
1 0, 2 0, 4 17.
. For those confused by this test case.
I believe svr's answer is right as my AC program outputs this very result. Slobodan has AC as well though. |
| Can I decrease flow on some pipeline? (-) | Ilya Rasenstein (Lyceum #40) | 1505. Oil Transfer | 3 Jul 2013 21:03 | 2 |
Yes. We can decrease flow on some pipeline( if the flow on some pipeline is greater zero ). And this operation is free!!! =) |
| WA 6. What is wrong? | Programmer | 1505. Oil Transfer | 16 May 2010 14:35 | 1 |
|
| WA31 | Alex Tolstov (Vologda STU) | 1505. Oil Transfer | 25 Sep 2009 01:05 | 2 |
WA31 Alex Tolstov (Vologda STU) 16 Sep 2009 13:15 Re: WA31 Alex Tolstov (Vologda STU) 25 Sep 2009 01:05 What is fucking test 31?? Does anybody know?
I use Dijkstra on residue network from several sources to sink.
For every edge (u, v):
1) if flow < capacity then cost = 0
2) if flow > 0 then graph contains back edge (v, u) with cost = 0.
Dijkstra initialize sources (nodes of the graph, where excess of flow > 0) with cost = 0. We find shortest path from one of sources to the sink. Then we make changes with edges used in shortest path and out results.
What's wrong?? |
| Clarification request | Slobodan | 1505. Oil Transfer | 6 Jul 2008 21:22 | 2 |
Please someone explain sample test case. I don't understand how we can push flow 2 through 1->2 (output shows that) if in the input there is flow capacity 1? In the second line of the input there is
2 1 1 1, 3 1 1 3.
that means there is pipeline between 1 and 2 with max flow 1, but there is already 1 flow, so we can't push anything more or something else...?
Thank you in advance. read carefully what "d" means. |
| WA 26 | Lomir | 1505. Oil Transfer | 12 Apr 2008 18:36 | 2 |
WA 26 Lomir 6 Nov 2007 03:18 First i had WA 20, because of wrong apporach, now WA 26...
Maybe somebody have some test ar now something similar to this testcase.
Btw, I am using dijkstra from source to sink with backegde cost of zero. Or this is also wrong? I was getting WA26 when use this declaration for "INFINITE" constant:
const __int64 INF = (__int64)1e17;
... when I change it for next one:
const __int64 INF = 10000....... ;
I get AC! |
| Test #6 incorrect. | pperm | 1505. Oil Transfer | 18 Sep 2007 01:24 | 2 |
In test#6 from station N oil is transported to other station.
Edited by author 18.09.2007 00:48 Test #6 is correct, read the problem statement more carefully. |
| Clarification request | it4.kp | 1505. Oil Transfer | 9 Mar 2007 23:11 | 6 |
What is the output for the following test?
4
2 3 3 1.
3 3 3 1, 4 1 0 1.
4 4 4 1.
.
Is minimum sufficient amount of money 0 or 1 ??? How can it be equal to 0? I think correct answer is:
1
2 3.
4 0, 3 3.
4 5.
. Well, the problem statement is not clear.
Obviously, nodes 1 and 3 can produce oil, so
technically we can reorganize whole network as follows:
1. Substract one item of flow from 2 to 3, since 3 can produce oil itself and easily can increase it's output by 1
2. Add flow of value 1 from node 2 to 4
Thus, to increase flow by one we need not to increase any
capacities and answer is 0.
Edited by author 12.01.2007 13:05 Hm, I think, you can be right... I'll try to implement it... Yes, the idea described above is really right... But this idea means that we must find min cost flow
with value 1 unit greater from 0-flow initial flow
not as additional flow,or make absolute new
flow distribution.
It seems that there is additional difficulty
that cost per- unit is 0 before capacity and c[i] after
capacity, or discontinious.
Thus problem seems non-standard.Don't say us secret,
best celebration to find ourselves. |
| Deikstra | svr | 1505. Oil Transfer | 11 Jan 2007 20:51 | 3 |
Why Deikstra from N-th node to sources backwards get WA20?
Transfer of one indivisible unit of the flow obiously is Deikstra best. What trick may be in test 20?
May be excess of the bound 10000 is forbidden for any money?
AC after year!
Djkstra of course, but in residue net.
Action of "zaem" just is equal to going along residue net.
Beside this the problem actually is not linear, just
piecewise linear. There is classical method of adding additional edge in this situation.
During a long time I could not understand why we may diminish flow along edges but sourses production no.
This becaurse in statement there are not words about
such diminishing but about increasing there are but only in limits from 0 to 1.
Edited by author 30.11.2008 22:06 Dijkstra - you should spell surnames properly
Edited by author 06.01.2007 14:03 I've checked all the numbers in the input - they are correct. But Dijkstra still gets WA #20...
May be, problem in some tricky cases like N = 1? I output "Impossible" in such a case... |
| What is the... | Vedernikoff Sergey | 1505. Oil Transfer | 11 Jan 2007 14:54 | 1 |
In the former statement of the problem number of quadruples was not exceed 1000000. Now - not more than 100000. VERY bad fact - I think many people (including me) don't solve this problem due to it...
When problemsetters will stop such an idiotism? |
| Memory limit exceeded for Test nr. 4 | TesterTest | 1505. Oil Transfer | 31 Dec 2006 01:07 | 1 |
I always get stuck at test nr.4 due to an exceeded memory limit. Can't figure out why, tried to tune all structures and algorithm for low consumption. Is it possible to get a test input file to check this ?
Regards,
Christian |
| Clarification request | Deftone | 1505. Oil Transfer | 7 Nov 2006 18:43 | 1 |
Is it guaranteed that there is station, where incoming flow is less than outgoing flow?
Could I output pairs in any order, or they should be sorted by vertex? |
| I don't understand rejudge! | EfremovAleksei | 1505. Oil Transfer | 7 Nov 2006 14:58 | 3 |
First submit: WA #6, I print information about all pipes.
Second submit: AC,I thought, that, if flow at pipe=0, then we don't print information about it at output.
Rejudge - WA #2 at Second Submit.
Third submit: AC, I print information about all pipes.
I don't understand why my first submit is not AC after rejudge.
Is it true, that ALL submits rejudged?
Edited by author 06.11.2006 23:20
Edited by author 06.11.2006 23:20 Your submission 1378260 has WA#6 because it didn't output all edges. I can send you this submission and simple fail-test. Thanks!
I thought, that only last submit was rejudged. |
| What should I output if N = 1? | White Bear, White Dew, White Clouds | 1505. Oil Transfer | 28 Oct 2006 18:03 | 1 |
And where does the oil come from? Station 1? |
