Curated sets
Graphs and traversal
BFS, DFS, shortest paths, and trees.
Total results3,710 problems
| Topics | Judge | |||||
|---|---|---|---|---|---|---|
| Revenge of the Endless BFSDecide whether a buggy BFS that forgets visited vertices ever terminates on a given directed graph, and if so output the loop count modulo 1e9+7. | Hard9 | GraphBFS+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Pipe Fitter and the Fierce DogsIn a grid where every odd row and column holds a house, cover all houses with downhill chains, minimizing the cost of pipes through dog blocks, using at most K chains. | Hard9 | Dynamic programmingGreedy+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Street TreesMaintain a minimum-cost coloring of N vertices with two colors under incremental equality/inequality constraints and point cost updates, reporting the optimum after each operation. | Hard9 | Union-findGraph+2 | No attempts yet | 2s | 256 MB | Judgeable |
| General graph matchingGiven an undirected graph with N vertices and M edges, print the size of a maximum matching. | Hard9 | GraphGreedy+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Maximum Weight Matching in a General GraphGiven a weighted undirected graph, find a matching with maximum total edge weight. | Hard9 | GraphGreedy+1 | No attempts yet | 2s | 512 MB | Judgeable |
| Voronoi DiagramGiven a connected weighted graph and a set of source vertices, assign every point on every edge to its nearest source (smallest index on ties) and report the total length each source owns. | Hard9 | GraphShortest path+2 | No attempts yet | 2s | 1024 MB | Judgeable |
| Xtreme NP-hard Problem?!Find the minimum-weight simple path from vertex 1 to vertex n that uses exactly k edges, or report -1; with n, m, k up to 10^6 this is explicitly NP-hard. | Hard9 | GraphShortest path+2 | No attempts yet | 5s | 1024 MB | Judgeable |
| Travelling MerchantGiven a directed weighted graph and per-market buy/sell prices for K items, find the maximum profit-to-duration ratio of a closed walk trading at most one item at a time, floor it. | Hard9 | GraphShortest path+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Tree EscapeOn a rooted tree where each leaf starts with one piece, players alternately move a piece to its parent and remove it at the root; decide if the first player wins. | Hard9 | Game theoryTree+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Tree and Queries 20Maintain a dynamic forest with link/cut and weighted edges, supporting toggling a vertex weight and querying the minimum weighted sum of tree distances from any vertex, with encrypted vertex indices. | Hard10 | TreeSegment tree+1 | No attempts yet | 5s | 512 MB | Judgeable |