## DMOPC '14 Contest 2 P5 - Sawmill Scheme

View as PDF

Points: 15 (partial)
Time limit: 5.0s
Memory limit: 256M

Authors:
Problem types

Having nearly completed their logging scheme, The Logging Company now wants to ship all logs collected at their logging station to some sawmills in the region. However, shipping logs with trucks costs money which can be better spent elsewhere (like in cutting more trees). To this end, The Company has devised a scheme where they will utilize the region's unique geography and abundant river networks for free shipping.

The geography of the land consists of some lakes and some rivers connecting them. Curiously, the latitudes of all the lakes are unique, and they are numbered from to from north to south. Even more strange are the facts that all the rivers between lakes only flow south, and there may be multiple rivers between the same two lakes. But thanks to this, logs the Company collects from up north can be moved south to their sawmills, for free!

The Logging Company has strategically built their collection point and sawmills next to lakes, the collection point being next to the lake numbered and one sawmill next to each lake with no river flowing south from it.

The Company has built more than one sawmill because free transportation comes with a degree of unpredictability. At any lake which doesn't have a sawmill next to it, a log may randomly flow down one river that leads south, with all possible southbound rivers being chosen with uniform probability. Knowing this, The Company would like to know how many resources to allocate to each sawmill, based on the probability of a log reaching that sawmill. For this, they've hired you to calculate the probability of a log from the collection point arriving at each sawmill.

#### Input Specification

First line: two space-separated integers and .
Next lines: two space separated integers and , representing a river flowing south from lake to lake . There will always be at least one river flowing south from lake .

#### Output Specification

For each sawmill, output the probability of a log reaching it as a real number . Your answer will be accepted as correct if it is within an absolute or relative error of no more than .

#### Sample Input 1

6 5
1 2
2 3
2 4
4 5
4 6

#### Sample Output 1

0.5
0.25
0.25

#### Explanation of Output for Sample Input 1

The given scheme can be represented by the following image.

A log starting at has a 1/2 chance of going into the sawmill at lake 3, and a 1/4 chance of reaching sawmills at lake 5 or 6.

#### Sample Input 2

5 4
1 2
1 3
2 4
3 4

#### Sample Output 2

1
0

#### Explanation of Output for Sample Input 2

The lake network may be disconnected. In Sample Input 2, lake 5 has no incoming rivers and no outgoing rivers. However, there is a sawmill on lake 5. No wonder the Logging Company is losing money!

• Kevy3030  commented on Feb. 9, 2020, 2:59 p.m. edit 2

Hey,

Can someone please take a look at my code? I think i've optimized it similar to the editorial (I did it top down though) but for some reason a couple of cases still TLE...

Thanks a lot!

• 4fecta  commented on June 26, 2019, 10:03 a.m.

Can someone check why my code TLE's? I only ran 1 BFS so the complexity should be O(V + E), which is way less than the allotted time assuming around operations per second.

• rjamieson100  commented on May 24, 2019, 12:57 p.m.

Hello,

I'm having trouble optimizing my code. It already seems to resemble the editorial's algorithm. Can anyone please offer a suggestion?

Thanks

• Jonathan_Uy  commented on Sept. 8, 2019, 7:36 p.m. edited

Hello,

The code that you have commented out in your submission is optimized. Make an ArrayList for every lake at the start, instead of checking if it is null and then making one when getting input. When printing output for sawmills, check if ArrayList size is 0 instead of if the ArrayList is null.

Please visit the DMOJ Slack for further help on problems.

Hope this helps

• alexzhang  commented on July 6, 2018, 10:37 p.m.

Do the sawmills have to be in any specific order of output?

• max  commented on July 7, 2018, 6:19 a.m.

yes, output the probability of a log reaching the th sawmill on the th line

• renzo1805  commented on Jan. 13, 2018, 3:00 p.m.

Hello,

Can somebody tell me what is wrong with my code: https://ideone.com/JRDJrM

Thanks!

• Kirito  commented on Jan. 13, 2018, 4:09 p.m.

The problem's generator was broken due to a judge rewrite. It has been fixed and all affected submissions have been rejudged.

• aeternalis1  commented on Aug. 5, 2017, 12:28 p.m. edit 4

Why does my code raise a Value Error? It runs the sample cases just fine, but IRs in several of the test cases.

• wleung_bvg  commented on Aug. 5, 2017, 1:06 p.m.

An integer takes up 4 bytes (on C++ and Java). This means an array of (1e6)^2 will take up 4 TB, which is way over the memory limit. On Python, an integer is as much as 24 bytes.

• aeternalis1  commented on Aug. 5, 2017, 1:23 p.m.

The problems just keep on coming...

• anishmahto  commented on Aug. 22, 2016, 11:40 p.m.

For anyone solving this problem using C++ in the future, if you aren't already, it'll probably be useful to use scanf() AND printf() for this problem. RIP my 1 hour.

• Flowright  commented on March 24, 2016, 12:02 a.m.

This question takes an incredibly long time to judge :<

• Xyene  commented on March 24, 2016, 12:23 a.m.

The problem uses a generator to generate the input cases on the fly. It takes some time for the generator to run for all 10 cases.

• minecraftyugi  commented on Jan. 5, 2016, 2:00 p.m.

Is the output in order of increasing destination lake number?

• Xyene  commented on Jan. 5, 2016, 2:34 p.m.

Yes.

• kobortor  commented on Jan. 24, 2015, 11:41 a.m.

If there are lakes 1 2 and 3, then lake 1 has 2 connections to lake 2 but 1 connection to lake 1, then does lake 2 have 2/3 chance or 1/2 chance.

• kobortor  commented on Jan. 24, 2015, 11:42 a.m.

sorry I meant have lake 1 have 1 connection to lake 3

• awaykened  commented on Jan. 24, 2015, 12:08 p.m.

2/3 assuming connections 1-->2, 1-->2, 1--3