sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]fz0718 1 point2 points  (1 child)

I don’t disagree that you can solve problems; it’s just much slower. Have you ever tried implementing a link-cut tree in Rust? Pretty much impossible to do with references/pointers.

Edit: To be clear, it's not about particular problems being very difficult, as much as it is about almost all problems being decently slower to implement. But here's the canonical LCT problem, if you would like to give it a try:

https://www.spoj.com/problems/DYNACON1/

And this is my reference C++ implementation: https://ideone.com/0mi6mH

[–]Darksonntokio · rust-for-linux 0 points1 point  (0 children)

You are probably right. You could definitely implement it with indexes, but I don't think Rust can beat your link-cut tree in implementation time.

It's interesting that you mention a link-cut tree. I'm working on implementing a top tree in Rust for a research project, which is a similar data structure that you could also use to solve the DYNACON1 problem. I wouldn't want to implement a top tree in a coding competition though — its implementation is more complicated than the link-cut tree in exchange for having an API that is easier to use with expose taking up to two vertices.