Блог пользователя visheshgautam.official

Nlogn code giving TLE,someone help this noob
Автор visheshgautam.official, история, 2 месяца назад, По-английски

[submission:https://mirror.codeforces.com/contest/1774/submission/250501754]

i have checked everything but cant find the bug

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

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

set<int>&. I don't see you modifying the set in dfs2, so it is safe to pass it as a reference. If not, the complexity is raised to $$$N^2$$$ due to there are $$$N$$$ dfs calls and the set is copied each time. (The logn part grows slower than the set copy part.)

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

you're copying the set object -> O(n) -> O(n2 * log(n))

→ Ответить