E. Subordinates

Codeforces

IDCF729E

Time1000ms

Memory256MB

Difficulty—

constructive algorithmsdata structuresgraphsgreedysortings

English · Original

Chinese · Translation

Formal · Original

There are _n_ workers in a company, each of them has a unique id from 1 to _n_. **Exaclty** one of them is a chief, his id is _s_. Each worker except the chief has exactly one immediate superior. There was a request to each of the workers to tell how how many superiors (not only immediate). Worker's superiors are his immediate superior, the immediate superior of the his immediate superior, and so on. For example, if there are three workers in the company, from which the first is the chief, the second worker's immediate superior is the first, the third worker's immediate superior is the second, then the third worker has two superiors, one of them is immediate and one not immediate. The chief is a superior to all the workers except himself. Some of the workers were in a hurry and made a mistake. You are to find the minimum number of workers that could make a mistake. ## Input The first line contains two positive integers _n_ and _s_ (1 ≤ _n_ ≤ 2·105, 1 ≤ _s_ ≤ _n_) — the number of workers and the id of the chief. The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ ≤ _n_ - 1), where _a__i_ is the number of superiors (not only immediate) the worker with id _i_ reported about. ## Output Print the minimum number of workers that could make a mistake. [samples] ## Note In the first example it is possible that only the first worker made a mistake. Then: * the immediate superior of the first worker is the second worker, * the immediate superior of the third worker is the first worker, * the second worker is the chief.

公司中有 #cf_span[n] 名员工，每人有一个从 #cf_span[1] 到 #cf_span[n] 的唯一编号。*恰好* 一人是主管，其编号为 #cf_span[s]。除主管外，每位员工都有且仅有一位直接上级。公司向每位员工发出请求，要求他们报告自己有多少位上级（不仅限于直接上级）。员工的上级包括他的直接上级、直接上级的直接上级，依此类推。例如，如果公司中有三名员工，其中第一位是主管，第二位员工的直接上级是第一位，第三位员工的直接上级是第二位，则第三位员工有两位上级，其中一位是直接上级，另一位不是直接上级。主管是除自己以外所有员工的上级。部分员工因匆忙而报告错误。你需要找出最少可能有多少名员工出错。第一行包含两个正整数 #cf_span[n] 和 #cf_span[s]（#cf_span[1 ≤ n ≤ 2·105]，#cf_span[1 ≤ s ≤ n]）——员工数量和主管的编号。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai ≤ n - 1]），其中 #cf_span[ai] 表示编号为 #cf_span[i] 的员工报告的上级数量（不只限于直接上级）。请输出最少可能出错的员工数量。 ## Input 第一行包含两个正整数 #cf_span[n] 和 #cf_span[s]（#cf_span[1 ≤ n ≤ 2·105]，#cf_span[1 ≤ s ≤ n]）——员工数量和主管的编号。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai ≤ n - 1]），其中 #cf_span[ai] 表示编号为 #cf_span[i] 的员工报告的上级数量（不只限于直接上级）。 ## Output 请输出最少可能出错的员工数量。 [samples] ## Note 在第一个例子中，可能只有第一位员工出错。此时：第一位员工的直接上级是第二位员工，第三位员工的直接上级是第一位员工，第二位员工是主管。

**Definitions** Let $ n, s \in \mathbb{Z}^+ $ with $ 1 \leq s \leq n $. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of non-negative integers, where $ a_i $ is the reported number of superiors of worker $ i $. The chief is worker $ s $, and must have $ a_s = 0 $. The hierarchy is a tree rooted at $ s $, where each non-chief worker has exactly one immediate superior, and the number of superiors of a worker is the depth of the node in the tree (distance from root). **Constraints** 1. $ 1 \leq n \leq 2 \cdot 10^5 $ 2. $ 1 \leq s \leq n $ 3. $ 0 \leq a_i \leq n - 1 $ for all $ i \in \{1, \dots, n\} $ 4. The true number of superiors for the chief is $ 0 $. 5. The set of true superior counts must form a valid tree depth sequence rooted at $ s $: - Exactly one worker has depth $ 0 $ (the chief). - For each depth $ d \geq 1 $, the number of workers at depth $ d $ is at most the number of workers at depth $ d-1 $. - Depths are consecutive from $ 0 $ up to some maximum $ D $. **Objective** Find the minimum number of indices $ i $ such that $ a_i \neq \text{true depth of worker } i $, over all valid tree structures rooted at $ s $.

Samples

Input #1

3 2
2 0 2

Output #1

Input #2

5 3
1 0 0 4 1

Output #2

API Response (JSON)

{
  "problem": {
    "name": "E. Subordinates",
    "description": {
      "content": "There are _n_ workers in a company, each of them has a unique id from 1 to _n_. **Exaclty** one of them is a chief, his id is _s_. Each worker except the chief has exactly one immediate superior. The",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF729E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are _n_ workers in a company, each of them has a unique id from 1 to _n_. **Exaclty** one of them is a chief, his id is _s_. Each worker except the chief has exactly one immediate superior.\n\nThe...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "公司中有 #cf_span[n] 名员工，每人有一个从 #cf_span[1] 到 #cf_span[n] 的唯一编号。*恰好* 一人是主管，其编号为 #cf_span[s]。除主管外，每位员工都有且仅有一位直接上级。\n\n公司向每位员工发出请求，要求他们报告自己有多少位上级（不仅限于直接上级）。员工的上级包括他的直接上级、直接上级的直接上级，依此类推。例如，如果公司中有三名员工，其中第一位是主管，...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, s \\in \\mathbb{Z}^+ $ with $ 1 \\leq s \\leq n $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of non-negative integers, where $ a_i $ is the reported number of superiors...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments