Show all threads Hide all threads Show all messages Hide all messages 
Get rid of WA#19  Mahilewets  1371. Cargo Agency  13 Jul 2017 10:37  1 
Let unsigned long long total_cost=0. For every edge E in tree total_cost +=cost_of_all_paths_lies_on_edge(E). double ans=2.0*total_cost/n/(n1) is overflow and and WA#19. ================ Let double ans = 0. For every edge E in tree ans+=2.0*cost_of_all_paths_lies_on_edge(E)/n/(n1). That is AC. =========== Maybe if not multiply by two in the first scenario there is also AC, I have not tested. 
WA3  💻Evgeny Nemtsev [UrFU]`  1371. Cargo Agency  11 Feb 2017 17:09  1 
WA3 💻Evgeny Nemtsev [UrFU]` 11 Feb 2017 17:09 Don't forget about cargo delivery time: 4 1 2 1 2 3 10 2 4 1  6 Edited by author 11.02.2017 17:10 
WA 17  Felix_Mate  1371. Cargo Agency  21 Feb 2016 20:28  1 
WA 17 Felix_Mate 21 Feb 2016 20:28 P.S. Нашёл баг, изза которого был WA: если вы в Pascal пишите z:=n*(n1), где zint64, nlongint, то результат z будет типом longint; правильно так: z:=n; z:=z*(n1). И ещё: лучше выводить не 4 знака в ответе, а все. Edited by author 03.08.2016 11:44 
Some tests  Zerolog1c [LNU]  1371. Cargo Agency  21 Feb 2016 17:17  3 
Can you give me the answers for:  3 1 2 1 2 3 1  6 1 2 1 2 3 1 2 5 1 3 4 1 3 6 1  Can you give plz some more test data..? 7 1 2 1 2 3 1 3 5 1 2 4 1 1 6 1 6 7 1 2.3810 
Is my idea right?  Lebedev_Nicolay[Ivanovo SPU]  1371. Cargo Agency  7 Sep 2015 22:39  2 
I try to solve this problem as "offline LCA problem" with recursive DFS, but I have TLE? Where is mistake? Maybe if you solved LCA problem effective you can get AC, but there is easier way to solve this problem. 
  Mickkie  1371. Cargo Agency  8 Jan 2014 19:23  1 
 Mickkie 8 Jan 2014 19:23 Resolved Edited by author 12.02.2014 21:04 
Why WA5 ?  hliu20  1371. Cargo Agency  25 May 2013 15:11  1 

if you crash #25, use this pragma can get AC  longmenwaideyu  1371. Cargo Agency  30 Jul 2012 09:17  1 
#pragma comment(linker,"/STACK:1000000000,1000000000") 
iif you crash #25, use bfs instead of bfs and got AC :D  hoan  1371. Cargo Agency  2 Aug 2011 11:47  2 
Or use #pragma comment(linker, "/STACK:16777216") 
Why I have WA#19...  BAron  1371. Cargo Agency  2 Aug 2011 11:46  2 
Please help me? why I have wa??? 
WA #21 Why?  Vedernikoff Sergey  1371. Cargo Agency  2 Aug 2011 11:39  6 
Because your solution is wrong! Probably arithmetic overflow or stack overflow. But why crash (stack_overflow)? My program shouldn't use so much memory! [code deleted] Edited by moderator 11.07.2006 23:07 You should manage your stack manually. if n = 1 > res/(n1) = res / 0?????????? No, from condition 2 <= N <= 50000 
To ADMIN: There might be invisible tricks in Test #23.  198808xc  1371. Cargo Agency  7 Dec 2010 22:16  5 
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 quicksort and use one bfs only, why my program have 0.265 s, in time??? 
Invalid checker?  Fyodor Menshikov  1371. Cargo Agency  13 May 2009 02:02  3 
out.println(answer);  output with maximal possible accuracy  WA24 out.printf("%.4f", answer);  output with exactly 4 digits after decimal point  AC. By the way, AC source 2369154 (3 Dec 2008) used println. Since then only Java 5>Java 6 changed. And maybe checker. So is this behaviour bug of println or checker? 
Memory limit  Fyodor Menshikov  1371. Cargo Agency  8 May 2009 15:18  2 
Is is possible to change memory limit for this problem from 16 Mb to 32 Mb? Problem is that 16 Mb is very uncomfortable for Java (and maybe C#) solutions. It is not enough for natural data structure (each vertex and each edge is separate object, each vertex has list of adjacent edges). Memory limit is 64 Mb now, all recent submits are rejudged. 
Incorrect limitation  Fyodor Menshikov  1371. Cargo Agency  8 May 2009 01:59  2 
In statement 1 <= n. There is no test where n = 1. And it is impossible because then according to formula in statement answer would be 0/0. Please update statement  change limitations to 2 <= n. 
Algo  Sid  1371. Cargo Agency  28 Jan 2009 01:58  4 
Algo Sid 11 Sep 2005 10:56 My algo is O(N) and it works 0.265 s... But there are solutions which work 0.06!! How? Can anybody tell me such algo. using dfs but own stack management My algo is normal recursion, and I have used pointer, too. It got AC in 0.093sec. Maybe I change the pro into unrecursion and unpointer,it could faster... Re: Algo Lebedev_Nicolay[Ivanovo SPU] 28 Jan 2009 01:58 Can anybode tell how to solve this problem? I had TLE #13 and I don't know what to do!!! 
Why TLE 13???  Lebedev_Nicolay[Ivanovo SPU]  1371. Cargo Agency  25 Jan 2009 17:09  1 
I find LCA with own stack! Why I have TLE? 
Precision question  Samsonov Alex [USU]  1371. Cargo Agency  19 Aug 2008 03:56  13 
What precision should we use in output? Could I have WA#17 because of it? Is double (long double) enough for us? with a precision of 4 decimal digits. double is always enough for calculatings on Timus. Then it (4 digits) should be written in russian statement. Fixed. () Vladimir Yakovlev (USU) 17 Sep 2005 00:29 To avoid precision problems it is possible to use only integer numbers in solving this task, but I have the same WA#17. Do you use int64? Check it. (50 000 * 50 000 = 2 500 000 000) Yes, of cause, I use unsigned __int64. I tried double, __in64 and long double and still WA17. That must be some other bug... Maybe problem with the following code: for ( i = 1; i <= m_N; ++i ) for ( j = 1; j <= m_N; ++j ) sum += t[ i ][ j ]; sum /= N * (N  1); It must be obviously changed to ... for ( i = 1; i <= m_N; ++i ) for ( j = 1; j <= m_N; ++j ) sum += t[ i ][ j ]) / ( N * (N  1)); overflow ... Maybe it will be usefull : ) And again I've tried both variants... Still WA17 Why both variants! First fragment implyies WA ( it`s obvious ) Did you convert N to __int64 ? It was noted that N*N > signed int. Hmmm ... Send me your code ( see email in my profile ) Yes. The bug what in these data types. I think I should love __int64 from this task and further. Thank you very much! I got AC. I used __int64 (signed) to get total sum of all paths. Then I casted it to double before division by n*(n1)/2. Got WA41. That happened because 'n' was 'int' and that multiplication overflowed. Then I casted 'n' to 'int64' inside that multiplication and got AC. 