3283 Path

[kenneth]

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]

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]

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);
}