F. Oil

Codeforces

IDCF72F

Time2000ms

Memory256MB

Difficulty—

greedymath

English · Original

Chinese · Translation

Formal · Original

After the nationalization of the oil industry, Dr. Mosaddegh wants to dig some oil wells to extract all the oil in Persian Gulf. But Persian Gulf is huge and has an infinite amount of oil. So Dr. Mosaddegh works only on a rectangular plane of size _n_ × _m_ of the Persian Gulf. Each of the cells in this rectangle either contains an infinite amount of oil or nothing. Two cells are considered adjacent if and only if they have a common edge, a path is a sequence _c_1, _c_2, ..., _c__x_ of cells so that all of them contain oil and for each _i_, _c__i_ is adjacent to _c__i_ - 1 and _c__i_ + 1 (if they exist). Two cells are considered connected to each other if and only if there exists a path between them. If we dig a well in a certain cell, we can extract oil from all the cells that are connected to it by oil paths. It is not allowed to dig wells on empty cells. Dr. Mosaddegh also knows that in Persian Gulf, the empty cells form rows and columns. I. e. if some cell is empty, then it's column is completely empty or it's row is completely empty, or both. Help Dr. Mosaddegh find out how many wells he has to dig to access all the oil in that region. ## Input In the first line there are two positive integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 100). In the second line there is an integer _t_ (0 ≤ _t_ ≤ _n_), the number of empty rows. _t_ distinct positive integers follow, these are the numbers of empty rows and are in range \[1, _n_\]. In the second line there is an integer _s_ (0 ≤ _s_ ≤ _m_) that shows the number of columns not having any oil. _s_ distinct positive integers follow, these are the numbers of empty columns and are in range of \[1, _m_\]. Note that rows are numbered from 1 to _n_ (from top to bottom) and columns are numbered from 1 to _m_ (from left to right). ## Output A single integer, the minimum number of wells that Dr. Mossadegh has to dig. This is actually finding how many regions are made by removing the given rows and columns. [samples]

在石油工业国有化之后，莫斯达格博士希望在波斯湾钻一些油井以提取所有石油。但波斯湾面积巨大，拥有无限量的石油。因此，莫斯达格博士仅在波斯湾的一个大小为 $n × m$ 的矩形区域内工作。该矩形中的每个单元格要么包含无限量的石油，要么为空。两个单元格被认为是相邻的，当且仅当它们有一条公共边；一条路径是单元格序列 $c_1, c_2, ..., c_x$，使得所有这些单元格都含有石油，且对于每个 $i$，$c_i$ 与 $c_{i-1}$ 和 $c_{i+1}$（如果存在）相邻。两个单元格被认为是连通的，当且仅当它们之间存在一条路径。如果我们在某个单元格钻井，就可以通过油路径从所有与之连通的单元格中提取石油。不允许在空单元格上钻井。莫斯达格博士还知道，在波斯湾中，空单元格形成完整的行和列。也就是说，如果某个单元格为空，则其所在列完全为空，或其所在行完全为空，或两者皆是。请帮助莫斯达格博士计算出他需要钻多少口井才能访问该区域的所有石油。第一行包含两个正整数 $n$ 和 $m$（$1 ≤ n, m ≤ 100$）。第二行包含一个整数 $t$（$0 ≤ t ≤ n$），表示空行的数量。接下来是 $t$ 个互不相同的正整数，这些是空行的编号，范围在 $[1, n]$ 内。第二行包含一个整数 $s$（$0 ≤ s ≤ m$），表示不含任何石油的列数。接下来是 $s$ 个互不相同的正整数，这些是空列的编号，范围在 $[1, m]$ 内。注意：行编号从 $1$ 到 $n$（从上到下），列编号从 $1$ 到 $m$（从左到右）。输出一个整数，表示莫斯达格博士必须钻的最少油井数量。这实际上就是求移除给定行和列后形成的连通区域数量。 ## Input 第一行包含两个正整数 $n$ 和 $m$（$1 ≤ n, m ≤ 100$）。第二行包含一个整数 $t$（$0 ≤ t ≤ n$），表示空行的数量。接下来是 $t$ 个互不相同的正整数，这些是空行的编号，范围在 $[1, n]$ 内。第二行包含一个整数 $s$（$0 ≤ s ≤ m$），表示不含任何石油的列数。接下来是 $s$ 个互不相同的正整数，这些是空列的编号，范围在 $[1, m]$ 内。注意：行编号从 $1$ 到 $n$（从上到下），列编号从 $1$ 到 $m$（从左到右）。 ## Output 输出一个整数，表示莫斯达格博士必须钻的最少油井数量。这实际上就是求移除给定行和列后形成的连通区域数量。 [samples]

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ denote the dimensions of the rectangular grid. Let $ R \subseteq \{1, \dots, n\} $ be the set of empty rows, with $ |R| = t $. Let $ C \subseteq \{1, \dots, m\} $ be the set of empty columns, with $ |C| = s $. The grid consists of cells $ (i, j) $ for $ i \in \{1, \dots, n\} $, $ j \in \{1, \dots, m\} $. A cell $ (i, j) $ contains oil if and only if $ i \notin R $ and $ j \notin C $. Two oil-containing cells are **connected** if they are adjacent (share an edge). A **connected component** is a maximal set of oil-containing cells such that any two are connected via a path of adjacent oil cells. **Constraints** 1. $ 1 \leq n, m \leq 100 $ 2. $ 0 \leq t \leq n $, $ 0 \leq s \leq m $ 3. All row indices in $ R $ and column indices in $ C $ are distinct and within bounds. **Objective** Compute the number of connected components of oil-containing cells in the grid after removing all cells in rows $ R $ and columns $ C $. That is, find the number of connected components in the subgrid induced by: $$ \{(i, j) \mid i \notin R,\ j \notin C\} $$

Samples

Input #1

2 3
1 2
1 2

Output #1

Input #2

4 4
2 2 3
3 2 3 1

Output #2

Input #3

2 3
1 1
0

Output #3

API Response (JSON)

{
  "problem": {
    "name": "F. Oil",
    "description": {
      "content": "After the nationalization of the oil industry, Dr. Mosaddegh wants to dig some oil wells to extract all the oil in Persian Gulf. But Persian Gulf is huge and has an infinite amount of oil. So Dr. Mosa",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF72F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "After the nationalization of the oil industry, Dr. Mosaddegh wants to dig some oil wells to extract all the oil in Persian Gulf. But Persian Gulf is huge and has an infinite amount of oil. So Dr. Mosa...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在石油工业国有化之后，莫斯达格博士希望在波斯湾钻一些油井以提取所有石油。但波斯湾面积巨大，拥有无限量的石油。因此，莫斯达格博士仅在波斯湾的一个大小为 $n × m$ 的矩形区域内工作。该矩形中的每个单元格要么包含无限量的石油，要么为空。\n\n两个单元格被认为是相邻的，当且仅当它们有一条公共边；一条路径是单元格序列 $c_1, c_2, ..., c_x$，使得所有这些单元格都含有石油，且对于每个 $...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the dimensions of the rectangular grid.  \nLet $ R \\subseteq \\{1, \\dots, n\\} $ be the set of empty rows, with $ |R| = t $.  \nLet $ C \\subseteq \\{1...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments