|
|
Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | Stack Overflow | Night | 1553. Caves and Tunnels | 17 июн 2021 20:27 | 3 | Please I got Crash(Stack Overflow), I implemented my first heavy-light descomposition and tried this problem, but I got this. I got AC, I had to convert the DFS to BFS, to evade the StackOverflow. Edited by author 02.11.2011 04:45 Edited by author 02.11.2011 07:20 Edited by author 02.11.2011 08:20 {$m 100000000000000000000} You can use "G++ 9.2 x64" language to avoid it | WA7, help please | Incognito | 1553. Caves and Tunnels | 5 июл 2020 01:59 | 1 | | Memory_Limit | Nodir | 1553. Caves and Tunnels | 14 ноя 2014 22:12 | 1 | I'm using Heavy light Decomposition an I'm getting ML in test 9 WHY ???? | AC with bruteforce | Spatarel Dan Constantin | 1553. Caves and Tunnels | 17 апр 2014 01:35 | 1 | I got AC with bruteforce. Perhaps the time limit should be reduced to 1 second or tests with very unbalanced trees should be added. | AC at least, but for me this problem very strange! | xurshid_n | 1553. Caves and Tunnels | 25 июн 2012 17:39 | 1 | Heavy-Light-Decomposition -> GOOD data structure! thank you all! | Why WA?... | Victor Barinov (TNU) | 1553. Caves and Tunnels | 28 апр 2012 07:02 | 13 | My algo is O(n * sqrt(n)) But i have WA on test 18. My solution gives same answers with brute force solution on my random tests. But what is 18-th test? Can anybody help me? Maybe, arithmetic overflow? Some answers may not fit in the standard 32-bit integer types... Really? Yes, I use usual int instead __int64. But in problem statement Q <= 10^5 and V <= 10^4 for all I queryes. So all values on nodes is <= 10^5*10^4. It is less than 2^31-1. But... maybe I misuderstud anything? BTW I will try submit with __int64 :) Thank You! Any more ideas? It fits in 32 bit integers. (I got AC using long). I also used O(n * sqrt(n)) (teoretically) but I can't think why you get WA on test 18... there must be a mistake someware. AC now! here it is program that generated contrary test for my solution: n = 10000; printf( "%d\n", n ); for (i = 0; i < n-1; ++i) { printf( "%d %d\n", random(i+1)+1, i+2 ); } m = 1000; printf( "\n%d\n", m ); k = random(m); for ( i = 0 ; i < k ; i++ ) printf( "I %d %d\n", random(n) + 1, random(10001) ); for ( i++ ; i < m ; i++ ) printf( "G %d %d\n", random(n) + 1, random(n) + 1 ); How can solve this problem in O(N * sqrt(N)) ?? Is it simple to implement ? My solution is O(N * log^2(N)). But it's very complex and slow ( 4.25s ) my program work about N*sqrt(N) but i have TL 17 any ideas about this test? why we have to use __int64? Can U tell me about ur method this is my email oybek_all@yahoo.com Edited by author 03.08.2008 14:40 No subject KantSU: Vashegin Roman 3 сен 2008 00:06 help me, please!! How solved? What algorithm? Tried through LCA and RSQ but could not....mail: Vashegin_roman@mail.ru Build clusters of O(sqrt(N)) in size using DFS-inside-DFS. Outer clusters tree will have O(sqrt(N)) diameter. Optimize by skipping a cluster completely when you find a way. When you increase radiation level, enumerate all "downward portals" to other clusters passing through incremented node, and update their skip-values (maximal radiation level on the path from downward portal towards upward portal to parent cluster). Keep separate list of in-cluster edges. Although outer cluster tree's diameter is O(sqrt(N)), its size is still O(N) (there can be a lot of tiny leaf clusters). You don't want to enumerate all of them if you want to stay at O(sqrt(N)) during increments :) Edited by author 09.09.2008 02:44 More simply: Divide Tree in sqrt(N) layers and in clusters. If cluster small jumping through layer when forming answer on 'G' query, but renewing for verteces of this cluster information on each 'I' query. If cluster big go through it by step by step but in this case renewing information only for one vertex in 'I' query. | Crash StackOverflow at Test#17,how can I fix it?thank you~~ | Fighting | 1553. Caves and Tunnels | 21 мар 2012 15:55 | 2 | Edited by author 20.08.2011 21:42 I have got an AC now, haha~~ I change my dfs to bfs,and its just OK~~~ So the dfs goes too deep leading to my stack overflow~~ best wishes~ Edited by author 20.08.2011 21:42 Edited by author 20.08.2011 23:07 | Radiaotion | Aleksandar Ralic | 1553. Caves and Tunnels | 5 апр 2011 03:52 | 2 | Is the radiation between two consecutive caves zero? Edited by author 05.04.2011 03:43 |
|
|
|