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

Автор rahulpkvij, история, 4 года назад, По-английски

https://codeforces.com/contest/1278/submission/75598239 Prob D DIV2 Educational Round 78.. https://codeforces.com/contest/1278/problem/D Can someone please help me figure out why my code gives TLE on TEST 49 ? It would be a huge help ! Thanks in advance!

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

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

Hello! From what I could tell by looking at your code, you seem to be iterating through every possible pair of segments, checking for intersections, and then checking to see if the resulting graph is a tree. The problem is that iterating through every pair of intersections takes $$$O(n^2)$$$ time, which is way too much for $$$n < 5 \cdot 10^5.$$$ Could you find a more efficient way to find all pairs of intersections?

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

    Hey ! Thank you for your reply !. I guess I am unable to understand how in the editorial we are finding all pairs of intersections in less than O(n^2) time.

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

      I think I finally got it !. We need to sort on the basis of starting points AND ending points in order to avoid unnecessary checks where one segment is contained inside the other. We break the process when we reach n intersections