I am getting MLE for this code https://codeforces.me/contest/1774/submission/186717963 Please Anyone Can help?
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
16:53:27
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
16:53:27
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | djm03178 | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 30.11.2024 00:41:33 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Hey man, i solved ur memory problem with the following submission: https://codeforces.me/contest/1774/submission/186734301
However, I got a time limit exceeded on the next test (22). Do u think u could give me a time complexity analysis for ur code to see what is the problem?
for my code the time complexity was O(n); where n is number of nodes
can u double check this please because my changes have not affected anything in your code but it is giving time limit exceeded on testcase 22.
The one thing more i have done is predefining the size of curr vector so to avoid mutliple times reallocation of size of the vector
Now i gets accepted by passing the visited vector by reference... !!
Thanks @TheOpChicken123 for pointing out.
https://codeforces.me/contest/1774/submission/186738592
Here is the revised code Link
alright man, good job
Pass the reference for
vistedandcurrvectors and make the necessary changes inupdate()andDFS()functions.This is ACCEPTED submission of your code.
In
update()you are not changing anything incurrvector, so better pass its reference, which will be faster [ O(1) compared to your O(N) passing] and also reduces memory usage in recursive calls.In
DFS()same thing.visitedandcurryou can pass the reference. But one change is required forcurr. As after every recursive function your lastly added element should be removed, add one extracurr.pop_back()at the end ofDFS()Hope you got it right :)