Discussion @ 1664. Pipeline Transportation @ Timus Online Judge

[ksu] glTron::teal Time [4] // Problem 1664. Pipeline Transportation 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!

tnu2 Re: Time [3] // Problem 1664. Pipeline Transportation 20 Dec 2008 16:36

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

Sandro (USU) Re: Time [2] // Problem 1664. Pipeline Transportation 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

Al.Cash Re: Time [1] // Problem 1664. Pipeline Transportation 1 Feb 2009 22:25

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

Sandro (USU) Re: Time // Problem 1664. Pipeline Transportation 2 Feb 2009 12:13

Oops... You are right! :)

Discussion of Problem 1664. Pipeline Transportation