Обсуждение @ 1553. Caves and Tunnels @ Timus Online Judge

coder AC at least, but for me this problem very strange! [2] // Задача 1553. Caves and Tunnels 25 июн 2012 17:39

Heavy-Light-Decomposition -> GOOD data structure! thank you all!

Solver Re: AC at least, but for me this problem very strange! [1] // Задача 1553. Caves and Tunnels 4 июн 2026 11:35

sqrt(n) decomposition also works here (0.5 sec) and easier to implement
it's actually does not differ much because heavy-light with segment/fenvick over chains will be something like Q*log^2(N) with bad constant over it

Solver Re: AC at least, but for me this problem very strange! // Задача 1553. Caves and Tunnels 4 июн 2026 12:33

Actually it was the other way around :) except for ram usage
SQRT: 0.437 11 532 KB
HLD: 0.296 14 784 KB

Обсуждение задачи 1553. Caves and Tunnels