I've been debugging this for a while and I still can't tell why it exceeds the memory limit.
Can somebody help me?
Submission: 5723491
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
19:56:31
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
19:56:31
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 21:38:31 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
Turns out using
ArrayDequeinstead ofLinkedListmakes the problem pass.I have the same problem, what can I do? Submission : 5724820
I think it's because you do recursion and the stack can grow up to 4kk (essentially the longest path) keeping the state of all intermediates. You can generate that case easily.
By the way, your code gets accepted using MS C++ ( http://codeforces.net/contest/382/submission/5726207 ). I had the same problem, and got accepted with gnu compiler only with dfs on std::stack.
Some codes with the same recursion passed, but they were close to memory limit,
I just submitted the code with MS C++ and it used much lower memory!!
I have the same problem MLE:
Submissions:
(recursive dfs) 5735956
(iterative bfs) 5741952
(iterative bfs) 5746973
I first started with recursive dfs with excessive usage of
new(1st submission), so I kinda removed it, then found the longest path will overflow the stack. So, I went to iterative bfs, while storing the final nodes, and following back their path (2nd submission), it didn't go well. So, I removed all that and calculated the distances as I go through the BFS (3rd submission), and now I have no idea, what might have caused the MLE, given that I seen Java solutions similar to what I do. Any help?What if you change int[][] grid to char[][] grid or at least short[][]
Please Check my 1st comment :)
It worked, thanks! I better learn to watch out next time.