H. Long Path

Codeforces

IDCF10256H

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Peter is captive in W's maze which can be represented as a tridimensional matrix with lengths $N$, $M$ and $K$. Initially, Peter is in cell (1,1,1) and he needs to get to cell ($N$,$M$,$K$) to escape. From a cell, he can move to any other cell that has a wall in common with your cell (maximum $6$ other cells). Now, everyone expects Peter to escape in the minimum number of steps, but he can do better than that. He thinks of getting out with the maximum number of steps, such that he doesn't visit a cell more than once in his path. Help Peter find the length of this path! The first line of the input contains a number $1 <= T <= 200. 000$, the number of tests. The next $T$ lines each contain the description of a test, 3 positive integers $1 <= N, M, K <= 10^6$. The output should contain $T$ lines, each containing an answer to a test. ## Input The first line of the input contains a number $1 <= T <= 200. 000$, the number of tests. The next $T$ lines each contain the description of a test, 3 positive integers $1 <= N, M, K <= 10^6$. ## Output The output should contain $T$ lines, each containing an answer to a test. [samples]

**Definitions** Let $ T = (V, E) $ be a tree with $ |V| = n $, $ |E| = n - 1 $. Let $ \mathcal{P} $ denote the set of all simple paths in $ T $. **Constraints** $ 2 \leq n \leq 200000 $ **Objective** Find the minimum number of paths $ P_1, P_2, \dots, P_k \in \mathcal{P} $ such that: $$ \bigcup_{i=1}^k P_i = V \cup E $$ That is, the union of the vertex and edge sets of the chosen paths covers all vertices and edges of $ T $.

API Response (JSON)

{
  "problem": {
    "name": "H. Long Path",
    "description": {
      "content": "Peter is captive in W's maze which can be represented as a tridimensional matrix with lengths $N$, $M$ and $K$. Initially, Peter is in cell (1,1,1) and he needs to get to cell ($N$,$M$,$K$) to escape.",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10256H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Peter is captive in W's maze which can be represented as a tridimensional matrix with lengths $N$, $M$ and $K$. Initially, Peter is in cell (1,1,1) and he needs to get to cell ($N$,$M$,$K$) to escape....",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T = (V, E) $ be a tree with $ |V| = n $, $ |E| = n - 1 $.  \nLet $ \\mathcal{P} $ denote the set of all simple paths in $ T $.\n\n**Constraints**  \n$ 2 \\leq n \\leq 200000 $\n\n**Obje...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments