Toll TrollsProblem code: M4 |
All submissions for this problem are available.
The problem statement has been updated.
Johnny has gone on a short excursion to the island of Bitland, and found himself with plenty of time to spare for sight-seeing. As a matter of fact, he does really have any itinerary at hand. All he would like to do is to walk around a bit, without spending too much money in the process.
The cities of Bitland are connected by a network of one way streets. If there exists a road leading directly from city A to city B, then there also exists a road directly from city B to city A. There maybe any number (possibly zero) of parallel roads between any two cities. However, it is possible to reach any city starting from any other city (possibly indirectly, going through other cities on the way).
Now, the trouble is that all of the roads in Bitland are privately owned, and toll trolls have been hired to guard them and collect the dues. What's worse, the trolls are moody and will in some circumstances change the sum of the toll charged for using a road...
Johnny starts his sight-seeing tour from the capital of Bitland. He always leaves each city by the cheapest outgoing road, i.e. the one which currently has the lowest toll. However, as soon as Johnny has used the road from A to B, the toll troll in charge of it increases the toll for the road, setting it at exactly 1 Bitlandian dinar more than the toll currently being charged on the most expensive of the roads leaving city A.
Johnny has been walking around the towns of Bitland for a while, and he is getting a little bored. Help him answer the following question: what is the toll he is going to pay when traversing the k-th road of his tour?
Input
The first line of input contains two integers: n, the number of towns in Bitland and m, the number of pairs of roads connecting them (1 <= n <= 105, 0<= m <=105). Each of the m-th following lines contains four integers A B cAB cBA, denoting the identifier of city A, the identifier of city B, the initial toll on the road from A to B, and the initial toll on the road from B to A (1 <= A < B<= n, 1 <= cAB, cBA <= 109). All tolls are expressed in dinars. You may assume that the initial toll values for all of the roads are different, and that the city labeled 1 is the capital of Bitland.
The next line of input contains the number t of queries asked by Johnny, t <= 104. Each of the following t lines contains a single integer k (1 <= k <= 1012).
Output
For each of the values of k given at input, print a line containing the toll paid by Johnny when traversing the k-th road along his route.
Example
Input: 3 2 1 2 5 10 1 3 11 7 4 1 2 3 5 Output: 5 10 11 12
| Author: | admin |
| Date Added: | 15-01-2010 |
| Time Limit: | 1 - 3 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
The input specification says
The input specification says 1<=n and 0<=m, but how can poor Johnny go anywhere if there are no roads?
he can't, so anserw is 0
he can't, so anserw is 0
Why 0? He doesn't pay a toll
Why 0? He doesn't pay a toll of 0. The toll is nonexistent, so the output is unspecified.
The problem statement states
The problem statement states that "... it is possible to reach any city starting from any other city (possibly indirectly, going through other cities on the way)". Therefore, if there are no roads, then there must be only one city, and then "poor Johnny" will indeed be unable to go anywhere. The way I see it, in this case, the input would be invalid unless t = 0.
At least one test case seems
At least one test case seems to have repeated edges between vertices. According to the problem statement this is not allowed. Please check.
@Mark On what basis do you
@Mark On what basis do you claim that there seem to be repeated edges?
@Brian On the basis that my
@Brian On the basis that my solution fails with an assertion error if I make a test for repeated edges, and otherwise gets wrong answer.
I request the CodeChef team
I request the CodeChef team to check the test cases as suggested above
Checking.
Checking.
Also, m will not be 0.
Also, m will not be 0.
guys is thr a probem with the
guys is thr a probem with the test cases? or is thr some spl case i am missing ??
My program is giving the same output as my bruteforce solution in all my test cases. Pls give some comments
I am having the same
I am having the same problem.
Also Mark has said above that the test cases have repeated edges which is invalid.
Statement updated. Sorry for
Statement updated. Sorry for the inconvenience.
""There maybe any number
""There maybe any number (possibly zero) of parallel roads between any two cities.""
What does the updated statement signifies?
Is it means that input can be in the form of:
1 2 5 10
1 2 10 2
Please comment
Yes.
Yes.
Will the k queries in the end
Will the k queries in the end always be in ascending order as in the test problem??
@Shrikant You can test that
@Shrikant You can test that yourself. Submit a program that does nothing but read the input and check whether the queries are in ascending order, then depending on whether or not they are, either make the program crash (e.g. by dividing by zero) (so the judge will say Run-time Error) or exit normally (so the judge will say Wrong Answer).
Does anyone really trust the problem statements in this contest anymore?
It would still be good to get an answer from the admin/problem setter but don't count on it.
@Admin Will the k queries in
@Admin
Will the k queries in the end always be in ascending order as in the test problem??
IMPORTANT : The time limit
IMPORTANT :
The time limit for this problem has been increased for some of the test cases as we felt that it was too strict. A rejudge is in progress.
@Brian, @pankaj The input is
@Brian, @pankaj The input is exactly as specified in the problem statement. Don't make assumptions about anything else.
This is hilarious. I submit
This is hilarious. I submit on Overlapping disks. Time limit exceeded. A few hours later the time limit is increased and I pass the rejudge. I submit this problem. Time limit exceeded. A few hours later the exact same thing happens. I wonder what will happen on Motorbike Racing...
I strongly feel they would
I strongly feel they would increase motorbike racing also! I dont think they have checked the data enough before the contest. May be if pieguy submits a solution for motorbike racing and if he gets TLE , admin would increase time.
Which is why I wait until the
Which is why I wait until the constraints settle in the middle of the contest.
Nice tomek! I have seen many
Nice tomek! I have seen many top participants doing that and it makes perfect sense.
I am getting WA and I am
I am getting WA and I am officially frustrated now. Could someone please confirm whether while judging, in the input, there would be only one such network of roads or can it be more than one i.e. will there be only one test case or multiple test cases in one file?
I can't think of any other reason why I am getting WA :-(
The input section makes this
The input section makes this clear.
What is the current time
What is the current time limit? It says 2 seconds however I've seem successful submissions with more 3 seconds.
"He always leaves each city
"He always leaves each city by the cheapest outgoing road, i.e. the one which currently has the lowest toll."
What happen if two roads have the lowest same price? The decision may affect the final answer.
Read the FAQ. And the problem
Read the FAQ. And the problem statement.
m newbie hereits my first
m newbie here
its my first time
can u please tell me how to take input
whether as .txt file or somhw else???
@Admin Can you please check
@Admin
Can you please check why my every runtime is shown as RUNTIME ERROR( Other ) ?
Even if it has only
assert(false);
like in submission 185616
@Thiago The time limit is 2
@Thiago The time limit is 2 seconds per file; the time shown for a submission is the total time for all files that were processed (the remaining files will not be processed if there is a runtime error or the submission exceeds the time limit). However, the admin did say above that the time limit for some test cases was increased.