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

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

https://codeforces.me/contest/1278/submission/75598239 Prob D DIV2 Educational Round 78.. https://codeforces.me/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
  • Проголосовать: не нравится

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 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 \lt 5 \cdot 10^5.$$$ Could you find a more efficient way to find all pairs of intersections?