Hái Hoa

Điểm: 1,00 (OI)

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

Python 3 5.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

Nông trại của Bác John là một đồ thị vô hướng liên thông gồm $N$ đỉnh và $M$ cạnh không trọng số. Bác John bắt đầu tại đỉnh $1$ .

Ban đầu, $K$ đỉnh $s_{1}, \dots, s_{K}$ có vườn hoa và $L$ đỉnh $d_{1}, \dots, d_{L}$ là đích đến.

Một đường đi từ đỉnh $1$ đến đích $x$ được gọi là đẹp nếu:

Đó là đường đi ngắn nhất từ $1$ đến $x$
Bác John đi qua tất cả các vườn hoa trên đường đi

Bác John có thể tạm thời thêm một vườn hoa tại đỉnh $f$ ( $2 \leq f \leq N$ ). Với mỗi đỉnh $f$ từ $2$ đến $N$ , xác định liệu có tồn tại đường đi đẹp sau khi thêm vườn hoa tại $f$ hay không.

Dữ liệu vào

Dòng 1: Số nguyên $T$ — số bộ test ( $1 \leq T \leq 100$ )
Với mỗi bộ test:
- Dòng 1: Bốn số nguyên $N, M, K, L$
- Dòng 2: $K$ số nguyên $s_{1}, \dots, s_{K}$ (bỏ trống nếu $K = 0$ )
- Dòng 3: $L$ số nguyên $d_{1}, \dots, d_{L}$
- $M$ dòng tiếp theo: Hai số nguyên $u, v$ mô tả cạnh

Tổng $N$ và $M$ trên tất cả bộ test không vượt quá $10^{6}$ .

Dữ liệu ra

Với mỗi bộ test, in chuỗi nhị phân độ dài $N - 1$ : ký tự thứ $i$ là 1 nếu đỉnh $i + 1$ thỏa mãn, 0 nếu không.

Ràng buộc

$2 \leq N \leq 2 \times 10^{5}$
$N - 1 \leq M \leq 2 \times 10^{5}$
$0 \leq K \leq N - 1$ , $1 \leq L \leq N - 1$

Ví dụ

Input	Output	Giải thích
1 7 7 0 1 5 1 2 2 3 3 4 4 5 5 6 6 7 3 6	111110	Không có vườn hoa sẵn ( $K = 0$ ). Đỉnh 2-6 đều nằm trên đường đi ngắn nhất đến đỉnh 5 (đích). Đỉnh 7 không nằm trên đường ngắn nhất nào.

Ghi chú

Test 2-5: $K = 0$ hoặc $L = 1$
Test 6-10: $K \leq 1$
Test 11-23: Không ràng buộc bổ sung

Bình luận

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