H. Hobsons' trains

Codeforces

IDCF10251H

Time5000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Mr. Hobson has retired from running a stable and has invested in a more modern form of transport, trains. He has built a rail network with $n$ stations. However, he has retained his commitment to free the passenger from the burden of too many choices: from each station, a passenger can catch a train to exactly one other station. Such a journey is referred to as a _leg_. Note that this is a one-way journey, and it might not be possible to get back again. Hobson also offers exactly one choice of ticket, which allows a passenger to travel up to $k$ legs in one trip. At the exit from each station is an automated ticket reader (only one, so that passengers do not need to decide which to use). The reader checks that the distance from the initial station to the final station does not exceed $k$ legs. Each ticket reader must be programmed with a list of valid starting stations, but the more memory this list needs, the more expensive the machine will be. Help Hobson by determining, for each station $A$, the number of stations (including $A$) from which a customer can reach $A$ in at most $k$ legs. Figure H.1: Illustration of Sample Input 1. Each circle represents a station. The numbers outside the circles are the station numbers loaded into the ticket readers when $k = 2$. The first line of input contains two integers $n$ and $k$, where $n$ ($2 <= n <= 5 dot.op 10^5$) is the number of stations and $k$ ($1 <= k <= n -1$) is the maximum number of legs that may be traveled on a ticket. Then follow $n$ lines, the $i^("th")$ of which contains an integer $d_i$ ($1 <= d_i <= n$ and $d_i != i$), the station which may be reached from station $i$ in one leg. Output $n$ lines, with the $i^("th")$ line containing the number of stations from which station $i$ can be reached in at most $k$ legs. ## Input The first line of input contains two integers $n$ and $k$, where $n$ ($2 <= n <= 5 dot.op 10^5$) is the number of stations and $k$ ($1 <= k <= n -1$) is the maximum number of legs that may be traveled on a ticket. Then follow $n$ lines, the $i^("th")$ of which contains an integer $d_i$ ($1 <= d_i <= n$ and $d_i != i$), the station which may be reached from station $i$ in one leg. ## Output Output $n$ lines, with the $i^("th")$ line containing the number of stations from which station $i$ can be reached in at most $k$ legs. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the number of stations, and $ k \in \mathbb{Z} $ the maximum allowed legs per ticket. Let $ f: \{1, \dots, n\} \to \{1, \dots, n\} $ be the function where $ f(i) = d_i $ denotes the unique station reachable from station $ i $ in one leg. For each station $ i $, define $ R_k(i) \subseteq \{1, \dots, n\} $ as the set of stations from which $ i $ is reachable in at most $ k $ legs (including $ i $ itself). **Constraints** 1. $ 2 \leq n \leq 5 \cdot 10^5 $ 2. $ 1 \leq k \leq n - 1 $ 3. $ f(i) \ne i $ for all $ i \in \{1, \dots, n\} $ 4. $ f $ is a function: each station has exactly one outgoing edge. **Objective** For each station $ i \in \{1, \dots, n\} $, compute: $$ | R_k(i) | = \left| \left\{ j \in \{1, \dots, n\} \mid \exists \, 0 \leq \ell \leq k \text{ such that } f^\ell(j) = i \right\} \right| $$ where $ f^0(j) = j $, and $ f^\ell(j) = f(f^{\ell-1}(j)) $ for $ \ell \geq 1 $.

API Response (JSON)

{
  "problem": {
    "name": "H. Hobsons' trains",
    "description": {
      "content": "Mr. Hobson has retired from running a stable and has invested in a more modern form of transport, trains. He has built a rail network with $n$ stations. However, he has retained his commitment to free",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10251H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Mr. Hobson has retired from running a stable and has invested in a more modern form of transport, trains. He has built a rail network with $n$ stations. However, he has retained his commitment to free...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of stations, and $ k \\in \\mathbb{Z} $ the maximum allowed legs per ticket.  \nLet $ f: \\{1, \\dots, n\\} \\to \\{1, \\dots, n\\} $ be the function whe...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments