ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1610. Cactuses

TimeLimit
Posted by 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
Posted by Nick J 1 Apr 2008 16:33
I also needed some minor optimizations to pass 1616 here which was accepted in OpenCup.
Re: TimeLimit
Posted by 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)
Posted by Vladimir Yakovlev (USU) 2 Apr 2008 03:36
Re: My solution is O(N)
Posted by 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)
Posted by Cheryl Xie 29 Apr 2008 20:27
Who can tell me How to solve with O(n)?
Re: My solution is O(N)
Just one DFS - 0.171 sec. even on vector<int> g[50000]
Re: My solution is O(N)
Posted by 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)
Posted by mwh 16 Sep 2012 18:58
can you give me some tests i've got 'wrong answer' for several times,
thank you very much!