Freaks City

Problem Overview Given a graph with (n) intersections ((n \le 10^3)) and (m) bidirectional roads ((m \le 10^4)), a person named T moves first along a predetermined path (c_1, c_2, \ldots, c_g). Each road has a travel time (f[u][v]). When T traverses a road, that road becomes blocked for the entire duration of T's crossing. Luka starts from inte ...

No difference between shortest paths in directed and undirected graphs (undirected graph are special cases of directed graphs) Graph storage: dense graphs (adjacency matrix) && sparse graphs (adjacency list) I. Single-Source Shortest Path 1. All edge weights are positive - Dijkstra's Algorithm Handling multiple edges and self-loops ...

Given a family tree, the task is to output the smallest generation (youngest descendants) and list all members belonging to that generation. Input Format: The first line contains an integer N (1 ≤ N ≤ 100,000), the total number of family members, each assigned a unique ID from 1 to N. The second line provides N integers where the i-th integer r ...

Contest preparation requires a structured approach to covering fundamental algorithms and optimizing problem-solving strategies. The following outlines core technical topics and execution practices essential for competitive programming. Core Algorithms and Data Structures Simulation and Mathematics High-precision arithmetic is critical for p ...

Prefix Matching and Keyboard Layout Reconstruction This problem involves identifying possible next characters based on a given prefix and mapping them to a specific $4 \times 8$ grid layout. The core task is to filter a list of strings that start with a specific sequence and mark the character that immediately follows that sequence. #include &l ...

Simple Graph Theory and Construction A Consider vertices with weight 2 as adding one to vertices with weight 1. Thus the problem is split into two parts: constructing the tree and adding one to vertices. In the first part, constructing the tree as balanced as possible is beneficial, as will be shown in the second step. Construction: Process DFS ...

Point and Edge Divide and Conquer Point and edge divide and conquer are algorithmic techniques that extend the concept of sequence divide and conquer to tree structures. The core idea involves selecting a "center" (a node or an edge) to partition the tree into smaller, independent sub-problems. To ensure efficiency and balance, we spe ...

Problem 1: Dumpling Purchase Optimization The problem reduces to a daily deciison: buy dumplings at the current price or rely on an earlier purchase plus storage cost. The total expense for day i if we buy on day j ≤ i is price[j] + c*(i - j). This can be rewritten as (price[j] - c*j) + c*i. Thus we can maintain the minimum value of price[j] - ...

The following C++ implementation demonstrates a complete Heavy-Light Decomposition (HLD) framework integrated with a lazy propagation segment tree to support efficient path updates and queries on trees. It passes the standard template problem on Luogu. #include <bits/stdc++.h> using namespace std; using i64 = long long; int MOD; struct ...

Definition of Degree The degree of a vertex (v) in a graph (G), denoted by (d_G(v)), is the number of edges of (G) incident with (v), with each loop counting as two edges. (J.A. Bondy, Graph Theory) Two fundamental results follow from this definition: Handshaking Theorem: For any graph (G), [ \sum_{v \in V} d(v) = 2m ] where (m) is the number ...