Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
DP with rerooting | strangequark0 | 1371. Грузоперевозки | 8 июл 2022 11:55 | 1 |
Can be solved using two DFS calls and tree rerooting in O(N) while maintaining a DP array where DP[node] = sum for all paths from node to all the nodes in its subtree (considering 1 as the initial root). Tree rerooting can be used to calculate the sum for all nodes. |
it is a tree!!! | >>> | 1371. Грузоперевозки | 8 ноя 2021 01:37 | 1 |
|
Is my idea right? | Lebedev_Nicolay[Ivanovo SPU] | 1371. Грузоперевозки | 27 фев 2021 15:17 | 3 |
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. u are late he got ac in 31 Jan 2009 |
WA 17 | Felix_Mate | 1371. Грузоперевозки | 27 фев 2021 14:28 | 2 |
WA 17 Felix_Mate 21 фев 2016 20:28 P.S. Нашёл баг, из-за которого был WA: если вы в Pascal пишите z:=n*(n-1), где z-int64, n-longint, то результат z будет типом longint; правильно так: z:=n; z:=z*(n-1). И ещё: лучше выводить не 4 знака в ответе, а все. Edited by author 03.08.2016 11:44 thnx a lot Felix_Mate i also face same situation. |
Get rid of WA#19 | Mahilewets | 1371. Грузоперевозки | 13 июл 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/(n-1) 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/(n-1). 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. Грузоперевозки | 11 фев 2017 17:09 | 1 |
WA3 💻Evgeny Nemtsev [UrFU]` 11 фев 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 |
Some tests | Zerolog1c [LNU] | 1371. Грузоперевозки | 21 фев 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 |
1371. Грузоперевозки | Felix_Mate | 1371. Грузоперевозки | 8 окт 2015 23:04 | 1 |
Кто решил,напишите пару тестов. |
- | Mickkie | 1371. Грузоперевозки | 8 янв 2014 19:23 | 1 |
- Mickkie 8 янв 2014 19:23 Resolved Edited by author 12.02.2014 21:04 |
Why WA5 ? | hliu20 | 1371. Грузоперевозки | 25 май 2013 15:11 | 1 |
|
if you crash #25, use this pragma can get AC | longmenwaideyu | 1371. Грузоперевозки | 30 июл 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. Грузоперевозки | 2 авг 2011 11:47 | 2 |
Or use #pragma comment(linker, "/STACK:16777216") |
Why I have WA#19... | BAron | 1371. Грузоперевозки | 2 авг 2011 11:46 | 2 |
Please help me? why I have wa??? |
WA #21 Why? | Vedernikoff Sergey | 1371. Грузоперевозки | 2 авг 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/(n-1) = res / 0?????????? No, from condition 2 <= N <= 50000 |
To ADMIN: There might be invisible tricks in Test #23. | 198808xc | 1371. Грузоперевозки | 7 дек 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 quick-sort and use one bfs only, why my program have 0.265 s, in time??? |
Invalid checker? | Fyodor Menshikov | 1371. Грузоперевозки | 13 май 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. Грузоперевозки | 8 май 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. Грузоперевозки | 8 май 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. Грузоперевозки | 28 янв 2009 01:58 | 4 |
Algo Sid 11 сен 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 янв 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. Грузоперевозки | 25 янв 2009 17:09 | 1 |
I find LCA with own stack! Why I have TLE? |