Обсуждение @ 1610. Нынче в моде кактусы @ Timus Online Judge

Показать все сообщения Спрятать все сообщения

TimeLimit Chmel_Tolstiy 1 апр 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 SF #1 1 апр 2008 16:33

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

Re: TimeLimit Chmel_Tolstiy 2 апр 2008 01:54

AC 0.078 sec.

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

My solution is O(N) Problemset Maintainer 2 апр 2008 03:36

Re: My solution is O(N) Chmel_Tolstiy 2 апр 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 апр 2008 20:27

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

Re: My solution is O(N) Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 25 окт 2008 04:30

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

Re: My solution is O(N) Tomislav Gudlek 17 апр 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) 109461RS 16 сен 2012 18:58

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

Обсуждение задачи 1610. Нынче в моде кактусы