#1156 · Thao tác trên bảng ô vuông

Mức độ vừa 1s 128MB

Đăng nhập

MÔ TẢ BÀI TOÁN

Cho một bảng ô vuông gồm $n$ dòng và $m$ cột. Các dòng được đánh số từ $1$ đến $n$ , các cột được đánh số từ $1$ đến $m$ . Ô nằm ở dòng $i$ và cột $j$ được gọi là ô $(i, j)$ . Có $k$ ô màu đen trên bảng, ô đen thứ $i$ nằm ở vị trí $(x_i, y_i)$ . Các ô còn lại trong bảng đều có màu trắng.

Bạn có thể thực hiện một trong hai loại thao tác sau (mỗi thao tác có thể được thực hiện nhiều lần hoặc không lần nào).

Chọn một dòng chỉ gồm các ô màu trắng, và xóa dòng đó khỏi bảng
Chọn một cột chỉ gồm các ô màu trắng, và xóa cột đó khỏi bảng

Hãy tìm cách thực hiện các loại thao tác trên, sao cho số ô còn lại trong bảng là nhỏ nhất có thể.

Dữ liệu vào

Dòng đầu tiên gồm ba số nguyên $n, m, k (1 \leq n, m, k \leq 10^5)$ - số dòng, số cột của bảng và số ô đen.
$k$ dòng tiếp theo, dòng thứ $i$ gồm hai số nguyên $x_i, y_i$ $(1 \leq x_i \leq n, 1 \leq y_i \leq m)$ - vị trí của ô đen thứ $i$ . Dữ liệu vào đảm bảo không có hai ô đen nào ở cùng vị trí.

Dữ liệu ra

In ra số ô còn lại nhỏ nhất có thể sau khi thực hiện hai loại thao tác trên.

Ràng buộc

BẢNG TỔNG QUAN KẾT QUẢ

#	Tài khoản	Kết suất	Lúc nộp
1	T Nguyễn Tri Bão Thắng @2180601452	6 ms 2872 KB 5968 Bytes	15/01/2023 20:41
2	T Nguyễn Tri Bão Thắng @2180601452	6 ms 2876 KB 5966 Bytes	16/01/2023 01:28
3	T Nguyễn Tri Bão Thắng @2180601452	22 ms 1840 KB 1543 Bytes	15/01/2023 19:48
4	H Nguyễn Đan Huy @2280601170	25 ms 1836 KB 792 Bytes	15/01/2023 21:41
5	H Trương Phước Hưng @2280601329	32 ms 492 KB 661 Bytes	21/04/2024 00:40
6	B Nguyễn Hữu Ngự Bình @2280600266	34 ms 512 KB 561 Bytes	16/04/2024 22:25
7	Lê Duy Hải @2280600799	36 ms 500 KB 553 Bytes	22/02/2024 17:57
8	B Trần Gia Bảo @2380600172	36 ms 1004 KB 1277 Bytes	10/10/2024 18:12
9	S Nguyễn Võ Hoàng Sơn @2280618566	39 ms 1864 KB 615 Bytes	04/03/2024 21:50
10	T Nguyễn Trung Tuyến @2011064511	40 ms 496 KB 621 Bytes	11/10/2025 03:26
11	H Nguyễn Viết Hiến @2280600923	41 ms 496 KB 584 Bytes	21/07/2025 08:45
12	Đỗ Chí Thành @24800600886	41 ms 1080 KB 848 Bytes	25/02/2025 21:08
13	Nguyễn Tri Bão Thắng @25807700104	41 ms 1864 KB 1543 Bytes	23/12/2025 15:26
14	Đỗ Chí Thành @24800600886	43 ms 1080 KB 830 Bytes	25/02/2025 21:08
15	H Clb Olympic Tin Học Hutech @olympictinhoc	47 ms 272 KB 610 Bytes	14/01/2023 20:02
16	Triệu Hoàng Đại Việt @25800600781	47 ms 1008 KB 628 Bytes	27/04/2026 20:21
17	T Phạm Đức Tài @2080601324	47 ms 1816 KB 446 Bytes	15/01/2023 19:58
18	Đ Huỳnh Thành Đô @2180600307	55 ms 1820 KB 379 Bytes	15/01/2023 20:35
19	Lê Duy Hải @2280600799	58 ms 1828 KB 1224 Bytes	08/09/2023 23:04
20	D Đậu Hoàng Diễn @2180607356	64 ms 1820 KB 467 Bytes	03/06/2023 13:47