DMOPC '14 Contest 2 P5 - Sawmill Scheme

View as PDF

Submit solution


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 N (2 \le N \le 1\,000\,000) lakes are unique, and they are numbered from 1 to N from north to south. Even more strange are the facts that all the M (1 \le M \le 2\,000\,000) 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 1 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 N and M.
Next M lines: two space separated integers i and j (1 \le i < j \le N), representing a river flowing south from lake i to lake j. There will always be at least one river flowing south from lake 1.

Output Specification

For each sawmill, output the probability of a log reaching it as a real number p_{i} (0 \le p_{i} \le 1). Your answer will be accepted as correct if it is within an absolute or relative error of no more than 10^{-9}.

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 C 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!


Comments


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

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


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

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


  • 0
    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!


    • 0
      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.


  • 0
    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.


    • 0
      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.


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

        The problems just keep on coming...


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

    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.


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

    This question takes an incredibly long time to judge :<


    • 2
      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.


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

    Is the output in order of increasing destination lake number?


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

      Yes.


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

    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.


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

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


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

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