Winter Roads: Revision history

Jump to navigation Jump to search

Diff selection: Mark the radio buttons of the revisions to compare and hit enter or the button at the bottom.
Legend: (cur) = difference with latest revision, (prev) = difference with preceding revision, m = minor edit.

1 March 2024

  • curprev 16:2616:26, 1 March 2024 Kmk21 talk contribs 594 bytes +594 Created page with "MST is only 1k nodes, so most operations are cheap. S is just a bfs in O(n), R is similar...bfs from the two endpoints of the repaired road (if not on the tree) and swap out if the repaired edge is higher than the min on that path in O(n). B is harder, but max 2k B operations, so can rebuild the MST each time. Don't rebuild the heap in kruskal, so you don't eat the extra log...just update the heap for each B and R. Only rebuild if B operation is for an edge on the curre..."
Retrieved from "https://wiki.speedyguy17.info/index.php/Winter_Roads"