Problems
Pick a problem and write your solution in the built-in editor. The judge runs it against real test cases while you watch, and the wider archive is open to read whenever you like.
Total results166 problems
| Title | Level | Topics | Solved | Time limit | Memory limit | Judge |
|---|---|---|---|---|---|---|
| NetworkingGiven points and weighted candidate cable routes, compute the minimum total cable length needed to connect all points (minimum spanning tree). | Easy3 | Minimum spanning treeGraph+1 | No attempts yet | 1s | 128 MB | Judgeable |
| ExploraceGiven a weighted undirected graph of checkpoints, find the minimum total length of edges that keeps every checkpoint connected. | Easy3 | Minimum spanning treeGraph+2 | No attempts yet | 3s | 512 MB | Judgeable |
| TreehousesConnect all treehouse points plus the first e ground access points by cables of minimum total length, given some cables already exist; output the added length as a MST problem. | Easy3 | Minimum spanning treeUnion-find+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Minimum Spanning TreeCompute the total edge weight of a minimum spanning tree for a weighted undirected graph with up to 10,000 vertices and 100,000 edges, allowing negative weights. | Medium4 | Minimum spanning treeUnion-find+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Cable DonationGiven an adjacency matrix of cable lengths between rooms encoded as letters, find a minimum spanning tree and output the maximum total cable length that can be donated, or -1 if the rooms cannot all be connected. | Medium4 | Minimum spanning treeGraph+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Network ConnectionGiven N computers and M weighted possible connections, compute the minimum total cost of edges to connect all computers into one network (minimum spanning tree). | Medium4 | Minimum spanning treeUnion-find+1 | No attempts yet | 2s | 256 MB | Judgeable |
| Jungle RoadsGiven a connected weighted graph of villages and roads, find the minimum total maintenance cost of a set of roads that keeps every village connected. | Medium4 | Minimum spanning treeGraph+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Underground CablesGiven up to 1000 points, connect them all with straight line segments of minimum total length, with no two segments crossing. | Medium4 | Minimum spanning treeGraph+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Bad CowtractorsGiven an undirected weighted graph, find a spanning tree of maximum total edge cost, or report -1 if no spanning tree exists. | Medium4 | Minimum spanning treeGreedy+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Watering the FieldsConnect all fields with pipes costing at least C while minimizing total squared distance, or report -1 when impossible. | Medium4 | Minimum spanning treeUnion-find+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Pangaea 1After each added road, compute the cheapest total length connecting all cities and XOR the m totals per test case. | Medium4 | Minimum spanning treeUnion-find+1 | No attempts yet | 20s | 256 MB | Judgeable |
| Troop MovementFind the route between two cities whose narrowest road is as wide as possible and report that width. | Medium4 | Minimum spanning treeUnion-find+1 | No attempts yet | 2s | 256 MB | Judgeable |
| Planet ConnectionGiven a complete symmetric cost matrix, find a minimum spanning tree connecting all planets and output its total maintenance cost. | Medium4 | Minimum spanning treeGraph+2 | No attempts yet | 1s | 256 MB | Judgeable |
| Watering FieldsGiven well-digging costs per field and pairwise pipe-connection costs, compute the minimum total cost to give every field water using an MST-style approach with a virtual water source. | Medium5 | Minimum spanning treeGraph+1 | No attempts yet | 2s | 128 MB | Judgeable |
| City Division PlanSplit a connected weighted graph into two connected subvillages by removing edges so that the total remaining maintenance cost is minimized. | Medium5 | Minimum spanning treeUnion-find+2 | No attempts yet | 2s | 256 MB | Judgeable |
| Communicating with the Space GodsGiven points with some already connected, find the minimum total length of new passages needed to connect all points into one network. | Medium5 | Minimum spanning treeUnion-find+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Designing a High-Speed Rail NetworkGiven a cost matrix where negative values mark already-built rail lines, compute the minimum spanning tree cost forcing existing lines and list the new lines to build. | Medium5 | Minimum spanning treeUnion-find+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Underground CablesGiven up to 1000 points in the plane, find the minimum total length of non-crossing straight cables that connect all points. | Medium5 | Minimum spanning treeGraph+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Building the ConstellationGiven n points in the plane, connect all of them with straight segments of Euclidean length so the total cost is minimized. | Medium5 | Minimum spanning treeGraph+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Tangled in CablesCompute the minimum spanning tree of a town map and compare its total length against the available spool of cable. | Medium5 | Minimum spanning treeGraph+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Time Is MoneyWe choose N-1 links forming a spanning tree minimizing SumTime*SumMoney, where each edge has a time and a money cost. | Medium5 | Minimum spanning treeGeometry+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Power ShortageGiven a connected weighted undirected graph, keep a subset of roads so every pair of houses stays connected while maximizing the total length of removed roads. | Medium5 | Minimum spanning treeGraph+2 | No attempts yet | 1s | 256 MB | Judgeable |
| Railway ConnectionGiven existing rail links and city flows, find the minimum cost to connect all cities, where an edge costs the product of its endpoint flows. | Medium5 | Minimum spanning treeUnion-find+2 | No attempts yet | 1s | 1024 MB | Judgeable |
| HighwaysConnect all towns with the cheapest new highways, where some links already exist, and report the summed squared lengths of the added edges. | Medium5 | Minimum spanning treeUnion-find | No attempts yet | 1s | 128 MB | Judgeable |
| Heavy TransportationFind the maximum weight that can travel from crossing 1 to crossing n, defined as the path whose smallest street limit is as large as possible. | Medium5 | GraphMinimum spanning tree+2 | No attempts yet | 1s | 128 MB | Judgeable |
| HighwaysFind a spanning tree of a connected weighted graph that minimizes the maximum edge weight, and report that weight. | Medium5 | Minimum spanning treeGraph+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Widest PathFind the path between two given nodes whose smallest edge weight is as large as possible. | Medium5 | Minimum spanning treeUnion-find+1 | No attempts yet | 1s | 128 MB | Judgeable |
| BridgeConnect all axis-parallel rectangular islands with bridges of minimum total squared shortest gap distance. | Medium5 | Minimum spanning treeGeometry | No attempts yet | 1s | 128 MB | Judgeable |
| CommunicationConnect all rooms in a 3D grid with the cheapest new links given some existing links and fixed horizontal and vertical costs. | Medium5 | Minimum spanning treeUnion-find+1 | No attempts yet | 1s | 128 MB | Judgeable |
| RoadDecide whether the road between p and q can belong to a cheapest network that connects all cities. | Medium5 | Minimum spanning treeUnion-find+1 | No attempts yet | 2s | 64 MB | Judgeable |
| Cross Country SkiingFind the smallest elevation gap D that keeps every waypoint mutually reachable through adjacent cells. | Medium5 | Minimum spanning treeUnion-find+1 | No attempts yet | 1s | 512 MB | Judgeable |
| SightseeingFrom node 1, route each destination along roads to make the weakest road on the path as strong as possible. | Medium5 | HeapMinimum spanning tree+1 | No attempts yet | 3.5s | 512 MB | Judgeable |
| Rat TunnelPick the cheapest lanes for cameras so every closed running route holds one, and report the total cost and the longest chosen lane. | Medium5 | Minimum spanning treeUnion-find+1 | No attempts yet | 1s | 256 MB | Judgeable |
| Not enough electricityConnect every city to exactly one of the given power plants with minimum total cable cost. | Medium5 | Minimum spanning treeUnion-find | No attempts yet | 1s | 256 MB | Judgeable |
| MoocastGiven N cow coordinates, find the smallest integer X such that the graph connecting pairs whose squared distance is at most X is connected. | Medium5 | GraphUnion-find+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Connecting Edges 2Given a weighted edge list, pick the order of adding edges that makes the total weight added up to the moment s and t first become connected as small as possible. | Medium5 | GraphSorting+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Love That Only Fails for MeFind the minimum spanning tree of a graph restricted to edges joining a men-majority school and a women-majority school, or report -1. | Medium5 | GraphMinimum spanning tree+2 | No attempts yet | 2s | 256 MB | Judgeable |
| Security System InstallationBuild a minimum spanning tree from the given network, then find the vertex minimizing the sum of shortest distances to all other vertices within that tree. | Medium6 | Minimum spanning treeGraph+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Grand CanalGiven a graph with edge widths, use maximum-spanning-tree logic to answer K queries for the widest ship that can travel between two given cities. | Medium6 | Union-findMinimum spanning tree+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Driving RangeGiven a weighted undirected graph, find the smallest range R such that using only edges of length at most R keeps the whole graph connected, or report IMPOSSIBLE. | Medium6 | GraphUnion-find+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Cables ... in Spaaace!Given a planet's diameter and up to 100 city coordinates, compute the minimum cable length of a strongly connected network and compare it to the available length L. | Medium6 | GraphMinimum spanning tree+2 | No attempts yet | 1s | 128 MB | Judgeable |
| TsunamiPlace a warning center and connect cities with cables so every city reaches the center, no city is warned from a city farther from the shore, and total cable length is minimized. | Medium6 | GraphMinimum spanning tree+2 | No attempts yet | 1s | 128 MB | Judgeable |
| WarfareGiven an undirected multigraph with per-edge cost as the sum of its endpoint weights, find the minimum total cost of edges whose removal destroys every cycle. | Medium6 | GraphMinimum spanning tree+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Will Indiana Jones Get There?Given axis-aligned wall segments, find the smallest board length such that a path from the first wall to the second keeps every gap no larger than that length. | Medium6 | GraphUnion-find+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Truck HistoryConnect all truck codes so the total Hamming distance is minimized, then print 1/Q. This is a minimum spanning tree on a complete graph. | Medium6 | Minimum spanning treeGraph+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Connect the CampusGiven N points in the plane and some already-built zero-cost edges, add edges connecting all points at minimum total Euclidean length. | Medium6 | Minimum spanning treeUnion-find+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Printed CircuitGiven a grid with some existing vertical and horizontal wires, add wires to connect all nodes, minimizing cost with vertical at 1 and horizontal at 2, then report the count and cost. | Medium6 | GraphMinimum spanning tree+1 | No attempts yet | 1s | 128 MB | Judgeable |
| The Shell GameBuy interval parity hints to fix every ball position while minimizing the worst-case total price. | Medium6 | Minimum spanning treeGraph | No attempts yet | 1s | 256 MB | Judgeable |
| Landline Telephone NetworkFind the cheapest network joining all buildings so no route between two buildings passes through a different insecure building. | Medium6 | Minimum spanning treeUnion-find+2 | No attempts yet | 2s | 256 MB | Judgeable |
| SuperbullPick N minus 1 pairings that connect all team IDs into one group so the sum of pairwise XOR values is as large as possible. | Medium6 | Minimum spanning treeGraph+1 | No attempts yet | 1s | 256 MB | Judgeable |
| Model RailroadDecide if the existing tracks can be replaced, within the same total length budget, so that all stations become connected. | Medium6 | Minimum spanning treeUnion-find+1 | No attempts yet | 2s | 512 MB | Judgeable |
| School TourChoose a spanning tree of the graph rooted at the entrance that contains the fixed edge to building 1, find the min and max possible number of uphill edges among its edges, and print (max)^2 - (min)^2. | Medium6 | Minimum spanning treeUnion-find+2 | No attempts yet | 1s | 256 MB | Judgeable |
| Paths in MultigraphFind the minimum number of edges to delete from an undirected multigraph so the remaining graph becomes disconnected. | Medium6 | GraphMinimum spanning tree+1 | No attempts yet | 2s | 512 MB | Judgeable |
| Cutting edges 2Given a weighted undirected graph and two vertices s and t, find the minimum total weight of edges to delete so that s and t end up disconnected, choosing the deletion order. | Medium6 | Minimum spanning treeGraph+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Frog PushersAfter channels are cut one by one in a fixed order, report the minimum spanning forest weight of the surviving graph before each cut, or FAIL if it is disconnected. | Medium6 | Union-findGraph+2 | No attempts yet | 5s | 512 MB | Judgeable |
| MST GameGiven an edge-weighted simple graph and a turn count K, find the MST cost each turn and delete the lightest MST edge after each turn, outputting 0 once the graph has no spanning tree. | Medium6 | Minimum spanning treeGraph+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Jurassic JigsawGiven n DNA strings of length k, build a spanning tree minimizing the total Hamming distance over its edges, and print the cost plus the edges. | Medium6 | Minimum spanning treeGraph+2 | No attempts yet | 1s | 512 MB | Judgeable |
| European TripChoose N-1 roads to keep every country connected, then find the closed tour that pays each road cost twice plus visit costs, and return the least total. | Medium7 | Minimum spanning treeGraph+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Architects' CountryConnect disjoint cities with new roads and pick an order to build required houses so total payments to participating architects are minimized. | Medium7 | Minimum spanning treeGreedy+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Stable NetworkGiven a star network from a hub plus some existing branch edges, add minimum-cost edges among branches so the whole network stays connected after any single edge or node fails (2-connectivity via biconnected components and MST on component graph). | Medium7 | Union-findMinimum spanning tree+1 | No attempts yet | 2s | 128 MB | Judgeable |
| RoadsDecide whether the graph has a spanning tree with exactly K gravel edges, where each road is gravel or concrete. | Medium7 | GraphMinimum spanning tree+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Arctic NetworkGiven P outposts and S satellite channels, find the minimum radio range D so that all outposts stay connected, where satellite-linked outposts communicate freely. | Medium7 | Minimum spanning treeUnion-find+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Power Cables to Sewer PipesFor each graph, remove a maximum-length set of edges while keeping the graph connected, then count the integer partitions of the removed length in meters. | Medium7 | GraphMinimum spanning tree+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Red-Blue Spanning TreeGiven a connected graph with red and blue edges, decide whether some spanning tree has exactly k blue edges. | Medium7 | Union-findGraph+2 | No attempts yet | 3s | 256 MB | Judgeable |
| Minimum Spanning TreeGiven a weighted graph and several spanning trees written as nested lists, decide for each whether it is a minimum spanning tree. | Medium7 | Minimum spanning treeUnion-find+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Connecting IslandsConnect all island polygons with bridges between vertices, each bridge crossing only water, minimizing the total length of the bridges. | Medium7 | GeometryMinimum spanning tree+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Animal FarmGiven M pens sharing walls, find the minimum total wall-removal cost so that all animals gather in one connected region, inside one pen or outside all pens. | Medium7 | GraphMinimum spanning tree+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Domino PuzzleAdd dominoes of minimum total pip-sum so that all pieces form one row with matching ends, an Eulerian path completion on values 1 to 6. | Medium7 | GraphShortest path+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Buy or BuildPick a subset of up to 8 subnetworks to buy and build edges so all n cities connect, minimizing total cost. | Medium7 | Minimum spanning treeGraph+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Railway NetworkGiven a connected edge-weighted graph and at most 8 terminals, find the minimum cost edge set that keeps all terminals mutually connected. | Medium7 | GraphShortest path+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Road RenovationChoose a cheapest set of directed roads so every city has at least one chosen road entering and one leaving it, or report impossibility. | Medium7 | GraphMinimum spanning tree+2 | No attempts yet | 1s | 128 MB | Judgeable |
| EvacuationFind the minimum number of directed edges to remove so that no path of length at most three remains from node 1 to node n. | Medium7 | GraphShortest path+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Highway Construction PlanChoose a spanning tree of a connected weighted graph that uses at most d edges incident to vertex 1, minimizing total cost. | Medium7 | GraphMinimum spanning tree+1 | No attempts yet | 1s | 192 MB | Judgeable |
| BytelandDecide for every proposed road whether some cheapest network connecting all towns can include it. | Medium7 | Minimum spanning treeUnion-find+1 | No attempts yet | 1s | 512 MB | Judgeable |
| Tour BeltFor each test case the program sums the sizes of connected island groups whose weakest inner synergy beats every outgoing synergy. | Medium7 | Minimum spanning treeUnion-find+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Safe Emergency Contact NetworkFor each road, report the cheapest total cost of a network connecting all villages without that road, or -1 when impossible. | Medium7 | Minimum spanning treeTree+1 | No attempts yet | 1s | 64 MB | Judgeable |
| There is No AlternativeCount the bridges that appear in every minimum-cost set connecting all islands and report their total cost. | Medium7 | Minimum spanning treeUnion-find+1 | No attempts yet | 3s | 256 MB | Judgeable |
| Hiking in the HillsFind a route from camp A to lookout B across the triangulated landscape whose highest point is as low as possible. | Medium7 | Union-findMinimum spanning tree+2 | No attempts yet | 2s | 256 MB | Judgeable |
| Minimum spanning tree after deleting one edgeFor each edge, report the MST weight of the graph with that edge removed, or -1 when it disconnects. | Medium7 | Minimum spanning treeTree+1 | No attempts yet | 3s | 256 MB | Judgeable |
| Minimum Median Spanning TreeFor each connected graph with an even node count, find the spanning tree whose median edge cost is smallest and report that median. | Medium7 | Minimum spanning treeUnion-find+1 | No attempts yet | 8s | 256 MB | Judgeable |
| Bridge Construction PlanningFind the cheapest spanning tree that uses exactly k edges from company A and the rest from company B, or report that none exists. | Medium7 | Minimum spanning treeBinary search | No attempts yet | 1s | 256 MB | Judgeable |
| Awkward GroupCount the subsets whose largest inner closeness is smaller than every closeness to the outside. | Medium7 | Minimum spanning treeUnion-find+1 | No attempts yet | 5s | 256 MB | Judgeable |
| AquariumFind the cheapest set of diagonal cell walls to remove so the whole R by C aquarium becomes one compartment. | Medium7 | Minimum spanning treeUnion-find+1 | No attempts yet | 3s | 256 MB | Judgeable |
| Fenced InRemove fence segments between adjacent field regions so every region connects with the smallest possible total removed length. | Medium7 | Minimum spanning treeGreedy+1 | No attempts yet | 2s | 512 MB | Judgeable |
| Fenced In (Gold)Remove fence segments of minimum total length so every region of the fenced grid connects to every other. | Medium7 | Minimum spanning treeGreedy+1 | No attempts yet | 2s | 512 MB | Judgeable |
| CitiesGiven a weighted undirected graph, pick a minimum-cost set of edges so that all k special cities (k at most 10) end up in one connected component. | Medium7 | Minimum spanning treeDynamic programming+2 | No attempts yet | 4s | 256 MB | Judgeable |
| Masonry BridgeGiven a connected undirected graph with edge weights, find the minimum over edge orderings of the earliest time island 1 and island N connect, and the maximum such time. | Medium7 | GraphMinimum spanning tree+2 | No attempts yet | 2s | 128 MB | Judgeable |
| The Sadness of DivisionSplit N members into two camps, respecting fixed members, to minimize the total weight of pairs split across camps, and output the lexicographically smallest camp A. | Medium7 | GraphMinimum spanning tree+2 | No attempts yet | 1s | 512 MB | Judgeable |
| Selecting the capitalGiven a connected multigraph where city i links to city R[i], merge adjacent cities the fewest times so that some city lies on every simple path between any two cities. | Medium7 | GraphMinimum spanning tree+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Jack EdmondsChoose at most n-1 Manhattan-distance roads so the round trip from the origin visiting all points (reusing edges freely) is shortest. | Medium7 | Minimum spanning treeGraph+1 | No attempts yet | 2s | 256 MB | Judgeable |
| TrucksGiven an undirected weighted graph, answer S queries asking for the maximum bottleneck (minimum edge on the best path) between two vertices. | Medium7 | GraphMinimum spanning tree+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Road ConstructionGiven a weighted bidirectional graph, find the minimum total building cost of a spanning subgraph that keeps every pairwise connection and preserves the shortest distance from the capital to every city. | Medium7 | GraphShortest path+2 | No attempts yet | 8s | 512 MB | Judgeable |
| Proving PropositionsChoose directed edges so all N propositions become mutually reachable, minimizing the difference between the hardest and easiest chosen proof difficulties. | Medium7 | GraphTwo pointers+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Wasting the Class FundEach friend gives one of two opposite demands on a Ppokppoki color and a Kkokkkoki model; choose buys to maximize satisfied friends and report the rest. | Medium7 | GraphMinimum spanning tree+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Delivering GoodsGiven a directed weighted graph and a set of client junctions, find the minimum number of trucks so each client is reached at its shortest-path time. | Medium7 | GraphShortest path+2 | No attempts yet | 5s | 512 MB | Judgeable |
| ConquerorConquer all cities from city 1, where the k-th city you take costs the edge cost plus (k-1)*t, and minimize the total. | Medium7 | Minimum spanning treeGreedy+2 | No attempts yet | 2s | 256 MB | Judgeable |
| How Many to Be Happy?For each edge find the fewest edges to delete so that it lies in some minimum spanning tree, then sum those counts. | Medium7 | Minimum spanning treeGraph+2 | No attempts yet | 0.5s | 512 MB | Judgeable |
| dgeu-learningGiven a connected weighted graph, answer queries for the maximum bottleneck path value between pairs of vertices. | Medium7 | Minimum spanning treeUnion-find+2 | No attempts yet | 4s | 512 MB | Judgeable |
| Red Blue Spanning Tree 2Given a connected undirected graph whose edges are red or blue, decide whether some spanning tree uses exactly k blue edges, and print one if it does. | Medium7 | GraphMinimum spanning tree+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Grid NetworkGiven a grid graph whose edge costs are 1 to 4 with distinct costs around every vertex, find the minimum spanning tree cost. | Medium7 | Minimum spanning treeGraph+2 | No attempts yet | 2s | 256 MB | Judgeable |