C. Polar map

Codeforces

IDCF10179C

Time8000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

See PDF statement in attachment. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of nodes. Let $ A = (a_1, a_2, \dots, a_n) $ be a permutation of $ \{1, 2, \dots, n\} $, where $ a_i $ denotes the parent of node $ i $ (with $ a_i = i $ indicating a root). **Constraints** 1. $ 1 \leq n \leq 2 \times 10^6 $ 2. $ a_i \in \{1, 2, \dots, n\} $ for all $ i \in \{1, \dots, n\} $ 3. All $ a_i $ are distinct. **Objective** Compute the number of roots in the forest, i.e., the number of nodes $ i $ such that $ a_i = i $.

API Response (JSON)

{
  "problem": {
    "name": "C. Polar map",
    "description": {
      "content": "See PDF statement in attachment. ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 8000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10179C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "See PDF statement in attachment.\n\n[samples]...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of nodes.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a permutation of $ \\{1, 2, \\dots, n\\} $, where $ a_i $ denotes the parent of node $ i $ (wi...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments