cho.sh

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 results839 problems
TitleLevelTopicsSolvedTime limitMemory limitJudge
Office RelocationGiven a weighted tree with marked query and leaf-coloured vertices, compute for every marked vertex the sum of squared weighted distances to coloured leaves (mod a prime).Hard8TreeDynamic programming+2No attempts yet2s512 MBJudgeable
Coloring RoadsColor every edge on a root path with a given color and then count colors used on exactly m edges, answering Q updates online.Hard8TreeSegment tree+2No attempts yet4s1024 MBJudgeable
Fake Plastic TreesBuild at most 125 balanced binary trees, reusing earlier trees as subtrees, so that one of them has exactly N nodes.Hard8TreeMath+2No attempts yet1s1024 MBJudgeable
UtilitarianismPick k tree edges with no shared endpoints to maximize total value; the answer is a matching-style DP with a slope-trick lambda search over edge weights.Hard8TreeDynamic programming+2No attempts yet5s1024 MBJudgeable
Baek ChaewonFind the homes where Baek Chaewon can always escape K equal-speed followers from node 1 along a shortest path in an undirected weighted graph.Hard8GraphShortest path+2No attempts yet2s512 MBJudgeable
Similar WordsGiven a set of distinct words, choose as many prefixes as possible so that no two chosen words differ by deleting one leading letter.Hard8TrieTree+2No attempts yet4s512 MBJudgeable
Masha and CactusChoose a maximum-weight subset of extra edges whose tree paths keep each vertex in at most one cycle, by a subtree DP with lazy updates on the path to the root.Hard8TreeDynamic programming+2No attempts yet4s512 MBJudgeable
Kingpin EscapeAdd as few edges as possible to a tree with root h so that destroying any one edge still leaves every node connected to h; output the new edges.Hard8TreeGreedy+2No attempts yet2s512 MBJudgeable
King's ColorsCount proper colorings of a rooted tree with n nodes using exactly k labeled colors, modulo 1000000007, where every color must appear at least once.Hard8TreeDynamic programming+2No attempts yet1s512 MBJudgeable
TreeChoose exactly m black vertices on a tree so that the maximum distance between any two chosen vertices is as small as possible.Hard8TreeBinary search+2No attempts yet1s512 MBJudgeable
Tree in TreeFor each vertex subset, count the edges in its minimal connecting subtree using Euler tour order and LCA checks.Hard8TreeDFS+2No attempts yet6s512 MBJudgeable
Prime Tree - 5Assign labels 1 to n to a tree's vertices so that as few edges as possible join two labels sharing a common divisor.Hard8GreedyNumber theory+2No attempts yet10s512 MBJudgeable
Prime Tree - 8Relabel the vertices of a tree with 1..n to minimize edges whose endpoints share a common divisor greater than 1. Output only, no fixed answer.Hard8TreeGreedy+2No attempts yet10s512 MBJudgeable
Metro LinesA tree is given, and for each query with two pairs of terminals, count the stations shared by the two paths between those pairs.Hard8TreeLinked list+2No attempts yet2s512 MBJudgeable
Decorating a Christmas TreeCount binary trees with exactly L levels and N distinct nodes, ordered by level and by a preorder placement rule, modulo 100030001.Hard8Dynamic programmingTree+2No attempts yet1s512 MBJudgeable
Hierarchical StructureGiven a rooted tree of employees and queries (a,b,l,r), compute the sum of ages in [l,r] over all vertices on the path from a to b.Hard8TreeBinary search+2No attempts yet3s512 MBJudgeable
Distance SumGiven a connected undirected unweighted graph with at most n+42 edges, compute the sum of shortest-path distances over all unordered vertex pairs.Hard8GraphBFS+2No attempts yet4s512 MBJudgeable
Katty and WonkiAdd 2 edges to an N-vertex tree to maximize vertices lying on created cycles; return that maximum for the worst case for the tree owner.Hard8TreeGraph+2No attempts yet1s256 MBJudgeable
Colorful TreeMaintain vertex colors on a tree under point updates and answer queries giving the number of edges in the minimal subtree spanning all vertices of one color.Hard8TreeDFS+2No attempts yet5s512 MBJudgeable
Tree and Queries 12Maintain a forest under edge insertions and deletions, and answer connectivity queries between two vertices.Hard8TreeUnion-find+2No attempts yet2s512 MBJudgeable
Heaps of FunGiven a rooted tree where each node i draws a uniform random real in [0, b_i], compute the probability that every parent's value is less than both its children's values, modulo 1e9+7.Hard8ProbabilityDynamic programming+2No attempts yet2s512 MBJudgeable
Cow LandOn a weighted tree, support point value updates and path XOR queries between any two nodes, returning the XOR of enjoyment values along the unique route.Hard8TreeDFS+2No attempts yet2s512 MBJudgeable
Dynamic CentroidFor each prefix tree formed by vertices 1..k, output the smallest centroid (the vertex whose removal leaves components of size at most k/2).Hard8TreeDFS+2No attempts yet1.5s512 MBJudgeable
Alpine ValleyGiven a weighted tree with shops and an exit, answer queries where one edge is removed and you need either the shortest distance to the exit or to the nearest shop from a village.Hard8TreeGraph+2No attempts yet3s512 MBJudgeable
The Valley OverflowsGiven a tree of valleys with heights, decide whether water starting from any non-K valley can reach valley K under the splash-up movement rule.Hard8TreeDFS+2No attempts yet1s512 MBJudgeable
Modified TreapAssign new distinct priorities to tree nodes so that the Cartesian-tree shape minimizes weighted depth plus K times the number of changed priorities.Hard8Dynamic programmingTree+2No attempts yet1s512 MBJudgeable
Circumcenter of a TreeGiven a tree and many triples of vertices, for each triple report the unique vertex equidistant from all three (with equal distances as small as possible) or -1 if none exists.Hard8TreeGraph+2No attempts yet2s512 MBJudgeable
Overflowing BanknotesFor each query, after updating one node, find the maximum banknotes that can be gathered at one safe when any node is chosen as root and the coins fall optimally.Hard8TreeDynamic programming+2No attempts yet2s512 MBJudgeable
Tree Colors and QueriesA rooted tree where edges are deleted over time; after each deletion, count distinct colors among vertices still reachable from a queried vertex.Hard8DFSTree+2No attempts yet2s256 MBJudgeable
Expression TreeGiven a binary expression tree with + and - operators, permute the operand values freely to maximize the evaluated result.Hard8TreeGreedy+2No attempts yet1s256 MBJudgeable
Denouncing the MafiaGiven a rooted tree at node 1 and a limit K, choose up to K nodes to seed interrogations so the total number of reachable ancestors is maximized.Hard8TreeGreedy+2No attempts yet1s512 MBJudgeable
Black StonesGiven a tree with some vertices marked black, count how many queries (i, j) admit a connected subtree with exactly i vertices and j black vertices.Hard8TreeDynamic programming+2No attempts yet1s512 MBJudgeable
SeparatorAppend values one at a time to a growing sequence and after each append report how many indices are separators, meaning every earlier element is smaller and every later element is larger.Hard8TreeImplementation+2No attempts yet1.2s512 MBJudgeable
SpyGiven a subordinate subtree for every leader in two rooted trees of N employees, count for each IOI employee how many of the M spy projects succeed, where spy b succeeds when the matching JOI employee lies in research project b's subtree.Hard8TreeDFS+2No attempts yet2s256 MBJudgeable
Inquiry IIGiven a connected simple graph with at most n+15 edges, output the size of its maximum independent set.Hard8TreeDFS+2No attempts yet5s512 MBJudgeable
Grand Central StationGiven a tree, find the minimum number of distinct map designs (rooted drawings) such that every vertex can be the center of one design after relabeling.Hard8TreeDFS+2No attempts yet2s512 MBJudgeable
DžumbusGiven a forest of N friends with drink thresholds, and Q queries each supplying a total drink S, find the maximum number of people who exchange solutions.Hard8Dynamic programmingTree+2No attempts yet1s512 MBJudgeable
Game on a TreeAlice places a chip on a white node of a rooted tree, then players alternately move it to an unvisited ancestor or descendant, blackening that node; the player who cannot move loses. Determine the winner.Hard8TreeGame theory+2No attempts yet1s256 MBJudgeable
EquilibriumGiven a tree, order its vertices to minimize the sum over vertices of the absolute difference between neighbors placed after and before them.Hard8TreeDFS+2No attempts yet1s512 MBJudgeable
Great GDPGiven a vertex-weighted tree and a value and weight per node, find the connected subtree containing the root that maximizes total value divided by total weight.Hard8Binary searchGreedy+2No attempts yet1s512 MBJudgeable
Jumping PathGiven a rooted tree with labels, find the length of the longest ancestor chain with nondecreasing labels, and count how many such chains of that length exist modulo 11092019.Hard8Dynamic programmingDFS+2No attempts yet10s512 MBJudgeable
Water Tanks of Seongdae CountryA tree of water tanks rooted at a capital. Adding water at city A adds 1,2,3,... along the root-to-A path. Answer queries about how much water a given city currently holds.Hard8TreeDFS+2No attempts yet1s256 MBJudgeable
VisitsGiven a tree, a visiting order, fuel prices, and tank capacities, compute the refueling cost of each trip in the order.Hard8TreePrefix sum+2No attempts yet2s512 MBJudgeable
Free EdgesGiven an undirected graph, find the minimum number of edges to paint black so that repeatedly blackening a white edge incident to a vertex with exactly one white edge turns every edge black.Hard8GraphDFS+2No attempts yet1s512 MBJudgeable
The Older We Are, The Worse It HurtsRoot the tree anywhere and order each node's children so that the weighted sum of DFS discovery times is minimized; output that minimum.Hard8TreeDFS+2No attempts yet2s512 MBJudgeable
ChallengeConstruct a tree with at most n vertices whose recursive center-removal decomposition puts some vertex in at least floor(sqrt(n)) different pieces.Hard8TreeGreedy+2No attempts yet2s512 MBJudgeable
Road NetworkGiven a tree, add one edge so that the number of bridges in the resulting graph is minimized, and report that minimum count.Hard8TreeDFS+2No attempts yet2s512 MBJudgeable
Awesome ShawarmaGiven a tree, count the unordered pairs of nodes whose added edge leaves the number of bridges in [L, R].Hard8TreeDFS+2No attempts yet14s512 MBJudgeable
Cost Of SubtreeGiven a tree with weighted edges, find a non-empty connected edge set maximizing its edge count times the minimum edge weight in it.Hard8TreeUnion-find+2No attempts yet1s512 MBJudgeable
Tree HullMaintain a set of tree vertices under insertions and deletions, and after each query report the total edge weight of the minimal subtree spanning the current set.Hard8TreeDFS+2No attempts yet3s256 MBJudgeable
Remove the TreeGiven a tree, repeatedly delete the vertices of any chosen path (and incident edges); find the minimum number of path-deletions needed to remove every edge.Hard8TreeGreedy+2No attempts yet2s256 MBJudgeable
MonkeysChoose K vertices of a tree and delete edges so every chosen monkey can reach another, minimizing the number of surviving edges.Hard8TreeDynamic programming+2No attempts yet4s512 MBJudgeable
Independent SetCount vectors of n nonnegative integers summing to m where positions flagged by a and parent-child pairs in the implicit binary heap cannot both be positive, modulo 1e9+7.Hard8Dynamic programmingTree+2No attempts yet2s512 MBJudgeable
Cleaning RobotsCount the ways to partition all vertices of a tree into vertex-disjoint paths such that no two paths can be merged into a longer path.Hard8TreeDynamic programming+2No attempts yet1s512 MBJudgeable
Infinite Binary EmbeddingCount the ways to embed a finite binary tree into the infinite binary tree so that each leaf lands at a prescribed height, modulo 1e9+7.Hard8TreeDynamic programming+2No attempts yet2s256 MBJudgeable
min-xorMaintain a dynamic set under insertions and deletions, and after each min-xor query report the smallest XOR of any two elements currently in the set.Hard8TrieBit manipulation+2No attempts yet0.4s8 MBJudgeable
Antennas On TreeFind the smallest set of tree vertices whose distance vectors distinguish every vertex from every other vertex.Hard8TreeDFS+2No attempts yet2s256 MBJudgeable
Cover the PathsGiven a tree and m simple paths, find a minimum-size vertex set that intersects every path, and output its size and members.Hard8TreeGreedy+2No attempts yet1s256 MBJudgeable
Median on Binary TreeGiven a heap-shaped binary tree with distinct weights, for every a find the largest a-median, defined as the element at position floor((k-a+1)/2) of a subtree sorted by weight.Hard8TreeDynamic programming+2No attempts yet2s512 MBJudgeable
Delivering FlyersOn a unit-weight tree, find the shortest closed walk from S that covers every node, given the rider can cover all nodes within distance D from any single stop.Hard8TreeGreedy+2No attempts yet1s1024 MBJudgeable
Second Diameter of a TreeGiven a weighted tree with up to 100,000 vertices, find the distance of the second farthest pair of vertices, allowing a tie with the diameter.Hard8TreeDFS+2No attempts yet1s1024 MBJudgeable
Roadside AdvertisementsOn a weighted tree, for each of Q queries with five distinct nodes, find the total weight of every edge lying on some shortest path between a pair of the five.Hard8TreeGraph+2No attempts yet1s512 MBJudgeable
Pandemic 2On a weighted tree where some vertices start infected and the infection spreads along edges at speed one, find the maximum number of uninfected connected components that ever exist at one moment.Hard8TreeDFS+2No attempts yet1s512 MBJudgeable
QuadtreeGiven a 2^n by 2^n binary matrix and a budget k, flip at most k entries so the resulting matrix has a quadtree with the fewest possible cells.Hard8TreeDynamic programming+2No attempts yet2s512 MBJudgeable
StationsLabel the stations of a tree so that a station holding a packet can pick the correct next hop knowing only its own label, the target label, and its neighbours' labels.Hard8TreeDFS+2No attempts yet20s1024 MBJudgeable
Cactus Graph AutomorphismsCount automorphisms modulo 1e9+3 of a given vertex cactus graph with up to 200 vertices.Hard9TreeCombinatorics+2No attempts yet2s128 MBJudgeable
Diameter of a CactusGiven a cactus graph (each edge in at most one cycle), compute the maximum shortest-path distance between any two vertices.Hard9GraphDFS+2No attempts yet1s128 MBJudgeable
Admiral Yi Sun-sinMaintain a dynamic graph of national roads (union-find) and acyclic expressways (link-cut style tree), updating region comfort values tied to region 1's component and answering path/sum queries online.Hard9Union-findTree+2No attempts yet1.216s512 MBJudgeable
WoodpeckersCount ways to place N woodpeckers into two height-ordered trees so every visiting pair lands in different trees and their connecting segments never cross, modulo K.Hard9TreeGraph+2No attempts yet10s128 MBJudgeable
Tree RotationCompute the minimum number of restricted tree rotations (at the root or root's right child) to transform one 0-2 binary tree's shape into another and output a valid rotation sequence.Hard9TreeGraph+2No attempts yet1s128 MBJudgeable
MoleGiven a tree, remove one edge and add one edge (keeping it connected) to minimize the tree's diameter, and output the resulting diameter with the edges swapped.Hard9TreeGraph+2No attempts yet1s128 MBJudgeable
SpellcastingGiven element costs, power rates, and a support tree, find the minimum time for the spell's total power to reach the target, given starting energy and continuous accumulation.Hard9MathGreedy+2No attempts yet1s128 MBJudgeable
Version-Controlled IDEMaintain a versioned text buffer under insert and delete operations, answering substring queries against any past version, with all commands encoded by a running counter.Hard9TreeImplementation+2No attempts yet1s128 MBJudgeable
Yin and YangOn a tree with each edge colored black or white, count paths that split at an internal vertex into two legs each having equal numbers of black and white edges.Hard9TreeDivide and conquer+2No attempts yet2s128 MBJudgeable
BottleneckGiven a tree of one-way paths toward field 1, each with a per-time-unit cow capacity, answer K queries for the most cows that can reach field 1 by time T.Hard9TreeGreedy+2No attempts yet1s128 MBJudgeable
Very Boring HomeworkInsert N keys into a BST, lay out its ASCII drawing, and report up to 5 small rectangular fragments of the picture.Hard9TreeImplementation+1No attempts yet2s128 MBJudgeable
Phylogenetic TreeGiven the graph of organisms joined when their tree distance is at most 3, find the fewest edges in any phylogenetic tree that produces it.Hard9GraphTree+2No attempts yet1s128 MBJudgeable
Longest Paths in a TreeA rooted tree has weighted edges. Handle point updates to edge weights and queries that ask for the maximum-weight downward path from a vertex inside its subtree.Hard9TreeSegment tree+2No attempts yet5s1024 MBJudgeable
Falling BallsGiven slanted platforms whose endpoints move over time, find the final x-coordinate reached by a ball dropped at a given x.Hard9Segment treeTree+2No attempts yet2s1024 MBJudgeable
JoggerGiven the distance matrix of a tree with houses as leaves, find the leaf pair whose weighted travel time (distance times r plus internal nodes crossed times t) is largest.Hard9TreeGraph+2No attempts yet1s128 MBJudgeable
Structural IsomersCount the number of distinct alkane carbon skeletons (free trees in which every node has degree at most 4) with n carbon atoms.Hard9Dynamic programmingCombinatorics+2No attempts yet1s128 MBJudgeable
AB-wordsGiven up to 1000 nice ab-words (balanced parentheses words), count the maximum subset of pairwise non-similar words under a recursive similarity relation.Hard9TreeHash map+2No attempts yet1s128 MBJudgeable
Milk MultidrinkDecide whether a tree with n nodes has a Hamiltonian path from 1 to n where consecutive vertices stay within distance two.Hard9TreeDFS+2No attempts yet1s128 MBJudgeable
HighwaysGiven a tree plus extra highway edges, count for each query (x,y) the main tree path plus alternative single-highway paths that touch the main path only at x and y.Hard9TreeDFS+2No attempts yet3s128 MBJudgeable
Aquarium 3Place K holes on distinct horizontal floor segments to maximize the area of water that drains out.Hard9TreeGreedy+2No attempts yet1s128 MBJudgeable
It Takes a VillageProcess online trading-post additions that spread through biconnected blocks and capital dominators, and answer revenue queries for single villages.Hard9GraphDFS+2No attempts yet20s128 MBJudgeable
Cactus AutomorphismsCount the automorphisms of a given cactus graph with up to 50000 vertices and print the count as a prime factorization.Hard9TreeDynamic programming+2No attempts yet5s256 MBJudgeable
FriendChoose a set of people with maximum total confidence so that no two chosen people are friends in the network grown by the three joining rules.Hard9GraphDynamic programming+1No attempts yet1s16 MBJudgeable
Maximum Transport ProfitPick two villages in the tree so the total profit of the given routes with both endpoints on the path between them is as large as possible.Hard9TreeDynamic programmingNo attempts yet3s256 MBJudgeable
Combinator ExpressionCount the fewest BCKI rewrite steps that reduce the given expression to its normal form.Hard9Dynamic programmingTree+1No attempts yet1s256 MBJudgeable
Hidden MazeCompute the expected median edge weight over all tree node pairs at odd distance, and print it as a reduced fraction.Hard9Divide and conquerTree+2No attempts yet2s256 MBJudgeable
Meeting in the Sierpinski LabyrinthTourists stand on cells of a grid that are free exactly when row and column share no binary 1 bit, and must meet in one cell with minimum total steps.Hard9TreeDivide and conquer+1No attempts yet3s512 MBJudgeable
Tree Edit DistanceCompute the minimum leaf insertions, leaf deletions, and relabels that turn one ordered labeled tree into another.Hard9Dynamic programmingTreeNo attempts yet2s256 MBJudgeable
FactoriesEach query gives two factory sets on a weighted tree and asks for the minimum distance between any factory in one set and any in the other.Hard9Divide and conquerTree+1No attempts yet6s512 MBJudgeable
WillowTwo players choose starting cities on a tree with coins and alternately collect cities, each road usable once, and Hanaa maximizes the final score difference.Hard9Game theoryTree+1No attempts yet5s512 MBJudgeable
Growing a Binary TreeFor each tree, pick a root and count the fewest vertices to add so that the result becomes a complete binary tree (every internal vertex has exactly two children, all leaves equidistant from the root), minimizing that count and then the vertex index; output the count mod 1e9+7.Hard9TreeDFS+2No attempts yet4s512 MBJudgeable
YATPGiven a node-weighted, edge-weighted tree, for each node find the minimum of dist(u,v) + p_u*p_v over all v, and sum these minima over all nodes.Hard9TreeDivide and conquer+2No attempts yet5s512 MBJudgeable
Tree TransformationCount the minimum-size sets of edges whose removal splits the tree into components of power-of-two sizes, modulo 1e9+7.Hard9TreeDynamic programming+2No attempts yet1s512 MBJudgeable
Tree and queries 5On a tree where vertices flip black and white, answer for each query the distance from a given vertex to the nearest white vertex.Hard9TreeDivide and conquer+2No attempts yet2s512 MBJudgeable
Trees and Queries 10Given a tree with vertex weights, answer path maximum-subarray-sum queries and path range-assign-weight updates.Hard9Segment treeTree+2No attempts yet2s512 MBJudgeable