C. Subordinates

Codeforces

IDCF737C

Time1000ms

Memory256MB

Difficulty—

graphsgreedy

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 \in \mathbb{Z}^+ $ be the number of workers, $ s \in \{1, \dots, n\} $ the id of the chief. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers where $ a_i $ is the reported number of superiors by worker $ i $. **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 superior hierarchy is a tree rooted at $ s $, with each non-chief worker having exactly one immediate superior. 5. The chief $ s $ has 0 superiors; all other workers have at least 1 superior. **Objective** Find the minimum number of workers $ i $ for which $ a_i $ does not equal the true number of superiors in the hierarchy. The true number of superiors for a worker is the depth of that worker in the tree (distance from root $ s $). Let $ d_i $ denote the true depth of worker $ i $, with $ d_s = 0 $, and $ d_i \geq 1 $ for $ i \ne s $. We may assign depths $ d_i $ consistently with a tree structure to minimize $ |\{ i \mid a_i \ne d_i \}| $.

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": "C. 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": "CF737C"
  },
  "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 \\in \\mathbb{Z}^+ $ be the number of workers, $ s \\in \\{1, \\dots, n\\} $ the id of the chief.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers where $ a_i $ is th...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments