I have run my program on my own conputer (which is slower than the server) several times on the data N = 50000. It takes not more than 0.1 seconds every time.

My algo is DP with the Time Complexity O(N).
To make my program robust, I use QuickSort to sort the edges, and this might use O(N log N) time.

I don't know why I get TLE. Maybe there are some tricks?

Thanks in advance.

By the way, I have submitted my program many times, and tried to crash it many times.
I realised that test #17 has N = 50000, too. And my program use not more than 0.3 sec to pass it. Why do I get TLE at test #23?

Please help me, thx in advance.

Edited by author 15.09.2010 12:04

I have found the problem. The QuickSort procedure in my problem works quite slow in the OJ. I don't know why. First #23 then #25. At last, I use a random method in the QuickSort and get AC, only 0.078 sec.

BTW, this is the first time I got stuck in QuickSort in TIMUS. Congratulations...

> The QuickSort procedure in my problem works quite slow in the OJ. I don't know why.

It's not the matter of OJ environment but the matter of corner cases. Note that asymptotic complexity of QuickSort in worst case is O(n*n).

i dont use quick-sort and use one bfs only, why my program have 0.265 s, in time???