Discussion @ 1610. Cactuses @ Timus Online Judge

TimeLimit Chmel_Tolstiy 1 Apr 2008 15:17

Why there so strict timelimit.
I solved this problem in OpenCup (where LT is 2 s). But for solve it there I need to make some optimization. Is it possible to increse timelimit to 2sec ?

My solution is O(NlogN).

Edited by author 01.04.2008 15:17

Re: TimeLimit Nick J 1 Apr 2008 16:33

I also needed some minor optimizations to pass 1616 here which was accepted in OpenCup.

Re: TimeLimit Chmel_Tolstiy 2 Apr 2008 01:54

AC 0.078 sec.

vector< vector<int> > and vector<int> get to big time ...

My solution is O(N) Vladimir Yakovlev (USU) 2 Apr 2008 03:36

Re: My solution is O(N) Chmel_Tolstiy 2 Apr 2008 14:11

I just delete edges with O(NlogN), but I understand how to do it with O(N). But I know O(M) solution for general but this solution don't use that we work with "cactus", I used it so have O(NlogN) solution.

Re: My solution is O(N) Cheryl Xie 29 Apr 2008 20:27

Who can tell me How to solve with O(n)?

Re: My solution is O(N) Vedernikoff Sergey (HSE: EconomicsForever!) 25 Oct 2008 04:30

Just one DFS - 0.171 sec. even on vector<int> g[50000]

Re: My solution is O(N) Tomislav Gudlek 17 Apr 2011 09:44

Could somebody provide some tricky test cases?

Edit: Or maybe provide TC 3 or 10?

Edited by author 17.04.2011 09:46

Re: My solution is O(N) mwh 16 Sep 2012 18:58

can you give me some tests i've got 'wrong answer' for several times,
thank you very much!

Discussion of Problem 1610. Cactuses