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

[ksu] glTron::teal Time [4] // Задача 1664. Нефтепроводы 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!

tnu2 Re: Time [3] // Задача 1664. Нефтепроводы 20 дек 2008 16:36

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

Sandro (USU) Re: Time [2] // Задача 1664. Нефтепроводы 20 дек 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] // Задача 1664. Нефтепроводы 1 фев 2009 22:25

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

Sandro (USU) Re: Time // Задача 1664. Нефтепроводы 2 фев 2009 12:13

Oops... You are right! :)

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