Kiểm Tra Bò

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho đồ thị vô hướng gồm $N$ đỉnh và $M$ cạnh, cùng xâu nhị phân $s$ có độ dài $N$ . Tại mỗi bước thời gian $t$ (từ $1$ đến $N$ ):

Nếu $s_{t} = 0$ : đỉnh $t$ bị xóa (cùng tất cả cạnh liên quan)
Nếu $s_{t} = 1$ : đỉnh $t$ bị xóa, nhưng trước khi xóa, thêm cạnh giữa mọi cặp hàng xóm của $t$

Hãy đếm số cặp đỉnh có thể đến được nhau (qua dãy cạnh) ngay trước mỗi bước thời gian $1, 2, \dots, N$ .

Input	Output	Giải thích
3 2 111 1 2 1 3	3 1 0	Ban đầu 3 đỉnh liên thông qua đỉnh 1 $\Rightarrow$ 3 cặp. Khi xóa đỉnh 1 ( $s_{1} = 1$ ), nối 2-3. Trước bước 2: 1 cặp (2,3). Trước bước 3: 0 cặp.
3 2 000 1 2 1 3	3 0 0	$s_{1} = 0$ nên xóa đỉnh 1 không nối hàng xóm. Sau đó đỉnh 2, 3 không liên thông.

Bình luận

Không có bình luận tại thời điểm này.