F. Pathwalks

Codeforces

IDCF960F

Time1000ms

Memory256MB

Difficulty—

data structuresdpgraphs

English · Original

Chinese · Translation

Formal · Original

You are given a directed graph with _n_ nodes and _m_ edges, with all edges having a certain weight. There might be multiple edges and self loops, and the graph can also be disconnected. You need to choose a path (possibly passing through same vertices multiple times) in the graph such that the weights of the edges are in strictly increasing order, and these edges come in the order of input. Among all such paths, you need to find the the path that has the maximum possible number of edges, and report this value. Please note that the edges picked don't have to be consecutive in the input. ## Input The first line contains two integers _n_ and _m_ (1 ≤ _n_ ≤ 100000,1 ≤ _m_ ≤ 100000) — the number of vertices and edges in the graph, respectively. _m_ lines follows. The _i_\-th of these lines contains three space separated integers _a__i_, _b__i_ and _w__i_ (1 ≤ _a__i_, _b__i_ ≤ _n_, 0 ≤ _w__i_ ≤ 100000), denoting an edge from vertex _a__i_ to vertex _b__i_ having weight _w__i_ ## Output Print one integer in a single line — the maximum number of edges in the path. [samples] ## Note The answer for the first sample input is 2: . Note that you cannot traverse because edge appears earlier in the input than the other two edges and hence cannot be picked/traversed after either of the other two edges. In the second sample, it's optimal to pick 1\-st, 3\-rd and 5\-th edges to get the optimal answer: .

你被给定一个有 #cf_span[n] 个节点和 #cf_span[m] 条边的有向图，所有边都具有特定的权重。图中可能存在多重边和自环，图也可能不连通。你需要在图中选择一条路径（可以多次经过同一顶点），使得边的权重严格递增，并且这些边必须按照输入顺序出现。在所有满足条件的路径中，你需要找到边数最多的那条路径，并报告这个最大值。请注意，所选的边不必在输入中连续。第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 100000]，#cf_span[1 ≤ m ≤ 100000]）— 分别表示图中的顶点数和边数。接下来 #cf_span[m] 行。第 #cf_span[i] 行包含三个用空格分隔的整数 #cf_span[ai]、#cf_span[bi] 和 #cf_span[wi]（#cf_span[1 ≤ ai, bi ≤ n]，#cf_span[0 ≤ wi ≤ 100000]），表示一条从顶点 #cf_span[ai] 指向顶点 #cf_span[bi]、权重为 #cf_span[wi] 的边。请在一行中输出一个整数 — 路径中边的最大数量。第一个样例输入的答案是 #cf_span[2]：。注意你不能遍历，因为边在输入中出现在其他两条边之前，因此不能在其他两条边之后被选取/遍历。在第二个样例中，最优策略是选取第 #cf_span[1] 条、第 #cf_span[3] 条和第 #cf_span[5] 条边，以获得最优答案：。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 100000]，#cf_span[1 ≤ m ≤ 100000]）— 分别表示图中的顶点数和边数。接下来 #cf_span[m] 行。第 #cf_span[i] 行包含三个用空格分隔的整数 #cf_span[ai]、#cf_span[bi] 和 #cf_span[wi]（#cf_span[1 ≤ ai, bi ≤ n]，#cf_span[0 ≤ wi ≤ 100000]），表示一条从顶点 #cf_span[ai] 指向顶点 #cf_span[bi]、权重为 #cf_span[wi] 的边。 ## Output 请在一行中输出一个整数 — 路径中边的最大数量。 [samples] ## Note 第一个样例输入的答案是 #cf_span[2]：。注意你不能遍历，因为边在输入中出现在其他两条边之前，因此不能在其他两条边之后被选取/遍历。在第二个样例中，最优策略是选取第 #cf_span[1] 条、第 #cf_span[3] 条和第 #cf_span[5] 条边，以获得最优答案：。

**Definitions** Let $ G = (V, E) $ be a directed multigraph with: - $ V = \{1, 2, \dots, n\} $: set of vertices, - $ E = \{e_1, e_2, \dots, e_m\} $: sequence of directed edges, where each $ e_i = (a_i, b_i, w_i) $, with $ a_i, b_i \in V $, $ w_i \in \mathbb{Z}_{\geq 0} $. A *valid path* is a subsequence of edges $ e_{i_1}, e_{i_2}, \dots, e_{i_k} $ with $ 1 \leq i_1 < i_2 < \dots < i_k \leq m $, such that: 1. $ b_{i_j} = a_{i_{j+1}} $ for all $ j \in \{1, \dots, k-1\} $ (consecutive edges are adjacent in the graph), 2. $ w_{i_1} < w_{i_2} < \dots < w_{i_k} $ (edge weights are strictly increasing). **Constraints** 1. $ 1 \leq n \leq 100000 $ 2. $ 1 \leq m \leq 100000 $ 3. $ 1 \leq a_i, b_i \leq n $ 4. $ 0 \leq w_i \leq 100000 $ **Objective** Find the maximum length $ k $ of any valid path, i.e., $$ \max \left\{ k \in \mathbb{Z}_{\geq 1} \mid \exists \text{ a valid path of } k \text{ edges} \right\} $$ If no edge can be selected, return 0.

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "F. Pathwalks",
    "description": {
      "content": "You are given a directed graph with _n_ nodes and _m_ edges, with all edges having a certain weight. There might be multiple edges and self loops, and the graph can also be disconnected. You need to",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF960F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a directed graph with _n_ nodes and _m_ edges, with all edges having a certain weight.\n\nThere might be multiple edges and self loops, and the graph can also be disconnected.\n\nYou need to...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你被给定一个有 #cf_span[n] 个节点和 #cf_span[m] 条边的有向图，所有边都具有特定的权重。\n\n图中可能存在多重边和自环，图也可能不连通。\n\n你需要在图中选择一条路径（可以多次经过同一顶点），使得边的权重严格递增，并且这些边必须按照输入顺序出现。在所有满足条件的路径中，你需要找到边数最多的那条路径，并报告这个最大值。\n\n请注意，所选的边不必在输入中连续。\n\n第一行包含两个整数 ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be a directed multigraph with:  \n- $ V = \\{1, 2, \\dots, n\\} $: set of vertices,  \n- $ E = \\{e_1, e_2, \\dots, e_m\\} $: sequence of directed edges, where each $ e_i ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments