In this submission :https://mirror.codeforces.com/contest/1775/submission/207782995 I am getting MLE i have scartched my head for hours and its still not resolving,can any comrade help this noob?
In this submission :https://mirror.codeforces.com/contest/1775/submission/207782995 I am getting MLE i have scartched my head for hours and its still not resolving,can any comrade help this noob?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 3 | Proof_by_QED | 147 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
(I think maybe you have read the tutorial and trying to do the same thing.)
I just take a quick look. The problem seems to be that there are too many edges. When you build the graph, it's enough to consider only prime factors instead of all the factors because if two numbers have the same common factor, they must have a common prime factor.
can you tell me in which cases MLE errors usually occur i have done that editorial thing still mle
With $$$n$$$ nodes, in the worst case your graph has $$$O(n^2)$$$ edges. This means you can potentially have over $$$10^{10}$$$ values in your adjacency list. Multiplying that by 4 bytes per int, this far exceeds the 256MB memory limit.
Try to implement an algorithm that does not construct this adjacency list.
(What you are going to do is to construct a bipartite graph that one part represents the really nodes and the other stands for prime factors.)
Ya, it seems you only add prime factors (Maybe you should check yourself again). However, you don't need an entry for composite numbers. I think it may pass after getting rid of it.
UPD: I have tried my own and got AC. Here is the code. https://mirror.codeforces.com/contest/1775/submission/207871816
Even if you just simply add 3e5 nodes, it'll still pass and is quite lower than the limit. https://mirror.codeforces.com/contest/1775/submission/207875652
I found another problem in your code. Why the number of entries is
(2*M)+1? What if M is small? Maybe it tried to use some unitializated memory as a vector due to out-of-bound access and caused a unexpected behavior which allocated a lot of memory. (I'm just guessing.)Just don't submit the code:)