Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×

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

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

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

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
  • Проголосовать: не нравится

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +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.

→ Ответить