ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1035. Cross-stitch

My best time is 0.078 s. I'm interested if there are quicker solutions.
I used a little different approach from the one mentioned on this board. It was based on weighted quick-union described by Sedgewick... I made a stupid logical mistake which caused my program to work the longest time possible, so first I got TLE#10 (solutionID=861144). Then I optimized my code with path compression (see Sedgewick once again) and got AC in 0.125 sec (solutionID=861147). Then I realized my error, removed path compression and got AC in 0.078 s (solutionID=861151). Adding path compression back slowed my solution a bit (0.109 s, solutionID=861153). All my solutions consume 449 KB of memory.

I'm interested in time and memory requirements of other possible algorithms. I haven't got their implementations, so I cann't submit them myself.

If somebody feels interested about my approach to this problem, just let me know - I'll explain.
Mine is 0.046. (+)
Posted by qwerty 12 Jun 2005 05:34
Re: My best time is 0.078 s. I'm interested if there are quicker solutions.
Posted by uuu 8 Apr 2010 14:00
I'm 0.015s
Re: Mine is 0.046. (+)
Posted by zslwyuan 1 Dec 2011 16:01
Mine is 0.031
Re: My best time is 0.078 s. I'm interested if there are quicker solutions.
Posted by Demenev Dmitriy 23 Dec 2015 15:07
ddfwf