Discussion @ 1035. Cross-stitch @ Timus Online Judge

My best time is 0.078 s. I'm interested if there are quicker solutions.

Posted by UXMRI: Sergey Baskakov, Raphail Akhmedisheff and Denis Nikonorov 12 Jun 2005 04:06

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

http://acm.timus.ru/status.aspx?space=1&pos=840027

Thank you! (-)

Posted by UXMRI: Sergey Baskakov, Raphail Akhmedisheff and Denis Nikonorov 12 Jun 2005 16:12

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

Discussion of Problem 1035. Cross-stitch