Page **1** of **1**

### 11573 - Ocean Currents

Posted: **Sun Feb 15, 2009 10:49 am**

by **jurajz**

I have question about this problem.

During the contest, I tried solve it with Dijkstra with binary heap -> TLE.

Then I had better idea, using combination BFS and DFS in this way:

Initially, in queue1 is only starting point and result =0 and visited[rs,cs]=true (all another points visited[r,c]=false)

Then, repeat this steps while visited[rd,cd]=false:

1. For all points in queue1 run DFS (respecting flow of the lake) and give all this unvisited points to queue2

2. If visited[rd,cd]=true then end this loop and write result

3. queue3 = queue1+queue2

4. Increase result and for all points from queue3 give all unvisited points neighbouring to points from queue3 to queue4

5. queue1 := queue4

This is still TLE. I think, that this algorithm runs in O(n*m) for one test case, O(k*n*m) for k test cases. imho it should pass time limit 3 seconds for maximal value of variables (k=50, n=m=1000). But I am wrong.

Have someone better idea to pass the time limit?

Thanks in advance!

### Re: 11573 - Ocean Currents

Posted: **Sun Feb 15, 2009 1:45 pm**

by **kn**

What heap did you use?

Heap of (Dist, x, y) ?

I use Heap of (Dist, z) (using C++ STL - priority_queue)

where z is encoded by x and y

and got accepted in 2.9xx -_-

I tried using Heap of (Dist, x, y) and got TLE for several attempts.

Hope it helps.

### Re: 11573 - Ocean Currents

Posted: **Sun Feb 15, 2009 2:20 pm**

by **rio**

> junrajz

I used the same algorithm as you described. It got accepted in 0.65 s without any optimization.

Maybe some flaw in your code.

-----

Rio

### Re: 11573 - Ocean Currents

Posted: **Sun Feb 15, 2009 2:28 pm**

by **jurajz**

kn and rio, thank you for your answers.

>kn

I used Heap of (Dist, z). But not in C++ STL, I used "homemade" Heap and in Pascal. Maybe I have more complicated representation of graph.

>rio

Now I know, that my idea was OK. I try to see my code, maybe here are some flaws (wasting of time or infinite loop).

### Re: 11573 - Ocean Currents

Posted: **Sun Feb 15, 2009 2:48 pm**

by **kn**

rio wrote:> junrajz

I used the same algorithm as you described. It got accepted in 0.65 s without any optimization.

Maybe some flaw in your code.

-----

Rio

Rio, would you please describe your codes in details?

e.g. the graph representation, STL used, the while loop of Dijkstra...

I wonder why my code has such a long runtime

### Re: 11573 - Ocean Currents

Posted: **Sun Feb 15, 2009 6:09 pm**

by **Jan**

I think you can avoid heap easily. I avoided stl, and got accepted in .7 seconds.

### Re: 11573 - Ocean Currents

Posted: **Sun Feb 15, 2009 9:49 pm**

by **kn**

Thanks for your hint!

I finally got it AC in 1.0xx sec.

I use BFS in my final implementation

Complexity : O(1000*1000)

### Re: 11573 - Ocean Currents

Posted: **Sun Feb 15, 2009 11:40 pm**

by **jurajz**

Thanks one more time, finally I have AC.

By random-generated test cases I noticed really stupid mistake in my code - in my BFS I wrote "false" instead of "true" and that means, that I don't marked squares added to queue4 as visited. After this, I have WA, after fixing have AC in 1.060.

### Re: 11573 - Ocean Currents

Posted: **Sun Feb 15, 2009 11:46 pm**

by **jurajz**

Here are my random-testcases, when someone have WA, this may help:

Input:

Code: Select all

```
10 10
6051134354
2321601626
4333237711
7100435246
1073373445
7444061776
7570714166
2261637531
6527302645
2035001421
50
2 3 4 1
8 7 8 6
8 2 10 7
2 5 8 5
2 1 3 1
10 3 6 6
10 6 2 4
10 8 4 5
3 1 5 5
1 4 4 5
10 8 9 7
5 8 3 7
10 8 7 8
2 8 2 9
2 2 10 2
5 5 7 2
8 10 7 3
6 5 3 5
1 10 2 1
1 6 2 10
10 1 7 9
2 2 1 2
5 1 10 9
8 4 1 2
2 6 8 6
5 4 9 8
9 7 4 6
9 10 3 5
6 7 5 4
10 8 10 7
7 10 8 5
8 7 4 6
8 10 5 6
2 5 2 6
6 3 2 4
4 3 3 8
1 1 1 8
4 4 3 1
1 9 7 4
7 8 2 5
9 5 4 9
3 4 7 3
1 6 6 7
3 6 7 7
2 9 10 7
6 3 1 8
9 9 5 6
1 2 6 2
9 4 5 2
8 8 2 7
```

Output from my AC program:

Code: Select all

```
2
1
3
3
1
3
3
3
1
1
1
2
3
0
3
2
4
2
5
0
4
1
3
3
3
2
2
4
2
1
2
1
2
1
2
2
3
2
2
3
2
2
2
1
5
3
3
3
2
3
```

### Re: 11573 - Ocean Currents

Posted: **Thu Mar 19, 2009 5:47 pm**

by **vahid sanei**

i cant undrestand this problem

for this case

### Re: 11573 - Ocean Currents

Posted: **Tue May 26, 2009 4:01 am**

by **doxi**

### Re: 11573 - Ocean Currents

Posted: **Tue May 26, 2009 4:07 am**

by **doxi**

I just used BFS + priority_queue

7153693 11573 Ocean Currents Accepted C++ 1.112

but I think it's not very good ,

but I got TLE at

http://acm.jlu.edu.cn/joj/showproblem.php?pid=2558
look this massage : The input contains several test cases so My program is not very good .....

used another

7153702 11573 Ocean Currents Accepted C++ 0.376

and get ac now

U can visit map[x][y] just one time

first wolk to the place where there need no energy and then 1 energy ..... and so on ....

just a bfs /..

### Re: 11573 - Ocean Currents

Posted: **Mon Jun 16, 2014 10:12 pm**

by **prashantharshi**

i used dijkstra with heap

u can also use c++ stl priority queue

here is my AC code

http://ideone.com/EO771i