|
|
you need to check, what element exist in your map Edited by author 28.02.2023 17:06 use unordered_map instead of map I used Dijkstra+heap optimized but still got TLE on #11.. Is there some better algorithm? help.. my email:caoyuan@mail.ustc.edu.cn thx. Try to use numbers instead of strings How to cope with the strings? I put all strings to a map, then for each string I construct all possible neighbours and then I check if they are in a map. So I have to deal with 50000 * 135 * 16 = 108 000 000 operations. It is too much. I can use a hash table. However, is there any simpler solution than using the hash table? You can use strings (because it's so conveniently), but you have to forget about std::map. Use unordered_map<string> (or your hash table) instead of it. I had TLE on test 11 with std::map, but when I changed map to unordered_map, I got AC with not bad time. I think it's easier than use numbers instead of strings. 47 times i had submitted a code with a small bug in heap... I'm sad... Guys, Can somebody give me a hint to avoid Memory Limit (I use C#)? I've tried a lot of algorithms: 1. Composing full graph by using digits tree for all numbers. Processing graph by using Dijkstra and PriorityQueue (SortedArray<ShortestDistance, Queue<VertexIndex>>). 2. Creating tree of digits for all numbers. Processing graph "on the fly": obtaining all neighbor vertexes for current vertex (from previously created tree). The Dijkstra and the same PriorityQueue were used. 3. Using Dictionary<PhoneNumber, VertexIndex> for storing all numbers and vertexes. Processing graph "on the fly": obtaining all possible neighbors (135) and filter them by real vertexes from dictionary. The same PriorityQueue was used. 4. The same as 3, but instead of PriorityQueue, I've used Heap<ShortestDistance, VertexIndex>. After distance to some vertex was updated, I remove this vertex from Heap (if it exists there) and add it again, but with new key (distance). I even replaced usage of all pointers to objects by UShort indexes, and now I'm in stuck. I've started work on this task because accidentally send solution of other task here, but now I already hate test #8 :) Any ideas? Just for your interesting: my mistake was in composing result path - it was composed for each vertex O_o. Hope my previous post help somebody! 50000 1 1 1 1 1 1 1 1 1 1 0000000000 0000000001 0000000002 0000000003 0000000004 . . . 0000049994 0000049995 0000049996 0000049997 0000049998 0000049999 Your test was added. Thank you. AC Edited by author 09.11.2010 02:11 TL9: Method remove(Object o) at Java PriorityQueue works's O(n). Don't use it ! Please Help me, i get WA #11 many times. My solution in Java 1) For each "phone number" get list neighbours 2) use PriorityQueue to find shortest path 3) print path For calculations with "phone number" use Long for init max_time use 10^12 I can send my solution on mail. Sorry for my english. You can send it to atush_1988@mail.ru I've got ac in java Got the same problem using c++((( Help sombody, please! Is it possible to solve it in Java without any special tricks? I got MLE #16 any time when I submitted it in Java. Of course, the same C++ code gets AC and uses 35 MB. I think that it is not good when equal solutions get different verdicts. Am I right? Admins, maybe you should increase memory limit? Edited by author 01.11.2010 10:11 Maybe you have problem with huge amount of strings while construct graph. std::string is mutable, but java.lang.String is immutable and you not call garbage collector for removing unnecessary copies. Java solution without strings require only 12MB http://acm.timus.ru/status.aspx?space=1&num=1806&author=38899I used strings only for reading input (not too much memory), then I used arrays of byte to store numbers and longs to keep them in map. Your 12 MB solution is too perfect :) Many other C++ solutions use about 40 MB and, rewritten in Java, they will be MLE. It means that C++ and Java are not equal in their opportunities for this problem. I don't like this. And you? By the way, Saratov provides programmers 256 MB for each problem. Why Timus can not do the same? Do not create the whole graph forward, just get the neighbours for the current vertex which is already removed from heap, this is the only trick :). I've got AC with standard java HashMap and PriorityQueue. wont it give tl if each step you go through 50000 neighbours. About n*n/2 in worth case Each vertex has at most 135 neighbours. ur right accepted. Thanks. Thanks to KALO too for the help. |
|
|