### visheshgautam.official's blog

By visheshgautam.official, history, 4 months ago,

In this submission :https://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?

 » 4 months ago, # | ← Rev. 3 →   0 (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.
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 can you tell me in which cases MLE errors usually occur i have done that editorial thing still mle
•  » » » 4 months ago, # ^ |   0 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.
•  » » » 4 months ago, # ^ | ← Rev. 3 →   0 (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://codeforces.com/contest/1775/submission/207871816
•  » » » 4 months ago, # ^ |   0 Even if you just simply add 3e5 nodes, it'll still pass and is quite lower than the limit. https://codeforces.com/contest/1775/submission/207875652I 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.)
•  » » » » 4 months ago, # ^ | ← Rev. 4 →   0 I forgot the line if (par[x] != -1) continue; in the bfs method, added it and it got ac:https://codeforces.com/problemset/submission/1775/207884247thanks for all your suggestions
 » 4 months ago, # |   +2 Just don't submit the code:)