## 3283 Path

Do you want to discuss about these problems? Go now!
Users are shared (no need to re-register).

Moderator: Board moderators

kenneth
New poster
Posts: 24
Joined: Wed Mar 02, 2005 12:29 am

### 3283 Path

Hi There,

I am trying to solve 3283 by using DFS n times which means my algorithm is O(n ^ 2). However, I get timed out, does anyone have a suggestion on how to solve this problem efficiently?

http://acmicpc-live-archive.uva.es/nuev ... php?p=3283

Thanks

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

### Re: 3283 Path

kenneth wrote:Hi There,

I am trying to solve 3283 by using DFS n times which means my algorithm is O(n ^ 2). However, I get timed out, does anyone have a suggestion on how to solve this problem efficiently?

http://acmicpc-live-archive.uva.es/nuev ... php?p=3283

Thanks
dynamic programming from the leaves upwards
for each vertex compute the longest path going downwards
then, combine this information to get the result (note that each path has one topmost vertex and two paths going down from there)

kenneth
New poster
Posts: 24
Joined: Wed Mar 02, 2005 12:29 am
Thanks. That will be much more efficient then my current implementation.

However, now I am getting Memory Limit Exceeded. Would anyone have some suggestion? The following is my memory usage:

Code: Select all

``````typedef vector <map <int, int> > VMII;
typedef vector <int> VI;

int profit(VMII& graph)
{
int road = 0;
VI maxPath(graph.size(), 0);
}``````