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

[HELP] Getting TLE in Problem 747E Comments (round #387)

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

I have written an O(n) solution using DFS but still i am getting TLE on test number 29. I don't understand why and hence i am unable to resolve the issue. I also tried using fast cin and cout but still i am getting TLE. Here is the link to the problem and link to my solution.

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

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

The problem is word = word + s[i];.

The compiler interpret it as word.operator=(word.operator+(s[i]));, and both string::operator+ and string::operator= is O(n). So the loop

while(s[i]!=',') {
    word = word+s[i];
    ++i;
}

is O(n2). You can generate a very long comment "ccccccc...c,0" and test your program with it. To fix this use word += s[i]. It's amortized time complexity is O(1).

In C++, a += b is not exactly same as a = a + b. Actually they can be totally different.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thank you for the help. I did not know that. Got an AC after making that change.

    → Ответить