|
|
back to boardShow all messages Hide all messagesI think 2 seconds is bad Time Limit. Also I don't know how many input
tests contains each test.
So I tried everything: like binary search and hash-function. But
always TLE.
Do you think 2 seconds is enough time? There is at least O(n*n) algorithm for 1003. I solved it in O(n*n) time and get AC in 0.125 sec. So, 2 seconds is enough timelimit for this problem. My algo is:
Each point have attibutes "parity" and "connectivity compontent number". When processing each segment, we check if it
- form a new connectivity component - O(1)
- extends existing connectivity components - O(1)
- connects existing CCs - O(N) for glue operation
- form a cycle in the existing CC - O(1)
This stage is O(n*n). It's quite enought for AC, but I'm still interested in more efficient algorithm :) Any ideas? :) |
|
|
