Discussion @ 1664. Pipeline Transportation @ Timus Online Judge

Time

Posted by [ksu] glTron::teal 20 Dec 2008 16:28

We have 10 000 station. And we have M<=100 000 000 pipelines between station. And we have only 0.5 seconds fo read 300 000 000 numbers. It is not possible!!!

Judges must do something with this problem!

Re: Time

Posted by tnu2 20 Dec 2008 16:36

There are much less than 300000000 pipelines. The graph is flat.

Re: Time

Posted by Sandro (USU) 20 Dec 2008 19:45

Flat graph with N vertices can have maximum 2*N-3 edges, so the problem input is not so large

Re: Time

Posted by Al.Cash 1 Feb 2009 22:25

Flat graph with N>2 vertices can have maximum 3*N-6 edges!

Re: Time

Posted by Sandro (USU) 2 Feb 2009 12:13

Oops... You are right! :)

Discussion of Problem 1664. Pipeline Transportation