Блог пользователя lazywitt

Автор lazywitt, история, 4 года назад, По-английски

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://mirror.codeforces.com/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.

Теги mle
  • Проголосовать: нравится
  • -15
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Note that here

for( auto i: vec ){
    for( auto j :  g[i] ){
        if( !vis[j] ) temp.push_back( j );

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 with temp.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.