visheshgautam.official's blog

Nlogn code giving TLE,someone help this noob
By visheshgautam.official, history, 10 months ago, In English

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

i have checked everything but cant find the bug

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.)

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply