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

Автор BERNARD, история, 5 лет назад, По-английски

Hello codeforces,

On this problem 1277E - Two Fairs, there is t test cases and I am using a vector<vector> ed(N) to store the edges of the graph, so in end of each test case I need to clear my vector ed so I created another one vector<vector> em(N) and it's empty all the running time, in the end of each test case I did ed = em to save time, but I were always getting a TLE on the 2nd test, and I don't know why. In the first submission 68468115, I did

vector<vector<int> > ed(N), em(N);
int main() {
  cin >> t;
  while(t--){
    ...
    ...
    ...
    ed = em;
  }
  return 0;
}

But when I did the following in this submission 68489443, I got an AC.

vector<vector<int> > ed(N);
int main() {
  cin >> t;
  while(t--){
    ...
    ...
    ...
    for(int i=0; i<n; i++) ed[i].clear();
  }
  return 0;
}

Can someone explain why I were getting a TLE on the first submission, even that in the first submission I were doing one operation but in the second one I were doing N operations.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
5 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

In the second submission, the number of times the ed[i].clear() funcion call is executed does not exceed 200,000 times as it is mentioned in the problem statement that the summation of n over all the test cases does not exceed this number. On the other hand, even though the ed = em statement in the first submission is executed at most 40,000 times, both operands are vector<vector<int>> with size 200,000 items. This is translated implicitly by the C++ compiler into up to 8,000,000,000 vector<int> assignment operations!