when a problem says, memory limit : 256 MB. Does it stands for : every test case 256 MB or memory of sum of all testcases : 256 MB.
reason to ask : https://codeforces.net/contest/1472/submission/103587221
no way , i get MLE for test case 10 which has 121 vertices and 180 edges, while i passed 200000 vertices and 199999 edges case i.e test case 9 .
Any associated insight is much appreciated. Thanks in advance.
Note that here
you don't guarantee that the same j will not be added for each i. So imagine a part of the graph with several layers of 5 vertices in each layer, and each 5 in each layer are connected with each 5 in the next layer (total of 25 vertices and 100 edges). If 5 vertices from the first layer are in your vec, you will add j to temp 25 times. Next time you will iterate over 25 vertices (each will be encountered 5 times in vec), and add 125 times to temp (each vertex will be encountered 25 times), and so on, growing exponentially. Just add
vis[j] = 1
together withtemp.push_back(j)
, and it will do it. But better implement bfs with a queue or two-pointer array, you are doing a lot of expensive operations in this implementation.i feel so stupid now :(, I highly appreciate the help man. Thanks.