Обсуждение @ 1664. Нефтепроводы @ Timus Online Judge

Time

Послано [ksu] glTron::teal 20 дек 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

Послано tnu2 20 дек 2008 16:36

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

Re: Time

Послано Sandro (USU) 20 дек 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

Послано Al.Cash 1 фев 2009 22:25

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

Re: Time

Послано Sandro (USU) 2 фев 2009 12:13

Oops... You are right! :)

Обсуждение задачи 1664. Нефтепроводы