King and the roads
All submissions for this problem are available.
There was a kingdom which had n cities numbered from 1 to n. The cities were connected in the form of a graph. Being very generous and just, he wanted to spread equality amongst all the things.He started with the roads.
The roads in his kingdom, were not necessarily same length and he wanted to make them equal.However there was a fixed cost of increasing roads per unit length and the treasury only had a certain amount of money. The roads could only be increased in length, but not decreased. Now help him to do so.
First line contains no of cities n and the total money available m.
Next n-1 lines contains description of the roads which contains 4 integers.
The first two integers are the cities which the road connects and the next two integers are their original length and cost per unit increase respectively,
If it is possible to make all the roads of equal length, then print "YES" followed by the maximum length that can be achieved. Otherwise print "NO".
- 1 ≤ n ≤ 105
- 1 ≤ money ≤ 1012
- 0 ≤ length < 104
- 0 ≤ cost < 104
cost of all the roads will never be 0 all together.
Input: 3 10 1 2 2 2 1 3 3 1 Output: YES 5
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.