Biến hữu ích

Điểm: 6,00 (OI)

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

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

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho một chương trình gồm $n$ trạng thái và $m$ phép chuyển có hướng giữa các trạng thái. Trong mỗi trạng thái, biến $V$ được thực hiện một trong ba thao tác sau:

$0$ — bỏ qua (không làm gì với $V$ ).
$1$ — gán giá trị mới cho $V$ .
$2$ — sử dụng giá trị của $V$ .

Một đường đi là dãy trạng thái $p_{1}, p_{2}, \dots, p_{k}$ sao cho tồn tại phép chuyển từ $p_{i}$ đến $p_{i + 1}$ với mọi $1 \leq i < k$ .

Giá trị của $V$ trong trạng thái $v$ được gọi là hữu ích nếu tồn tại đường đi $p_{1}, p_{2}, \dots, p_{k}$ với $p_{i} = v$ ở vị trí nào đó ( $1 \leq i \leq k$ ) thỏa mãn:

Tại $p_{1}$ , biến $V$ được gán giá trị (thao tác $1$ ).
Tại $p_{k}$ , biến $V$ được sử dụng (thao tác $2$ ).
Không có trạng thái $p_{j}$ nào với $j > 1$ thực hiện thao tác $1$ (giá trị gán tại $p_{1}$ tồn tại cho đến khi được sử dụng tại $p_{k}$ ).

Hãy tìm tất cả các trạng thái mà tại đó giá trị của $V$ là hữu ích.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $m$ — số trạng thái và số phép chuyển.
Dòng thứ hai chứa $n$ số nguyên $f_{1}, f_{2}, \dots, f_{n}$ ( $0 \leq f_{i} \leq 2$ ) mô tả thao tác tại từng trạng thái.
$m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_{i}, b_{i}$ ( $a_{i} \neq b_{i}$ ) mô tả phép chuyển từ trạng thái $a_{i}$ đến trạng thái $b_{i}$ . Giữa hai trạng thái có thể có nhiều phép chuyển.

Dữ liệu ra

In ra $n$ số $r_{1}, r_{2}, \dots, r_{n}$ , mỗi số trên một dòng. $r_{i} = 1$ nếu giá trị của $V$ tại trạng thái $i$ là hữu ích, ngược lại $r_{i} = 0$ .

Ràng buộc

$1 \leq n, m \leq 10^{5}$
$0 \leq f_{i} \leq 2$
$1 \leq a_{i}, b_{i} \leq n$ , $a_{i} \neq b_{i}$

Ví dụ

Input	Output	Giải thích
4 3 1 0 0 2 1 2 2 3 3 4	1 1 1 1	Đường đi $1 \to 2 \to 3 \to 4$ bắt đầu bằng phép gán tại trạng thái $1$ và kết thúc bằng phép sử dụng tại trạng thái $4$ . Tất cả các trạng thái nằm trên đường đi này nên đều có giá trị hữu ích.
3 1 1 0 2 1 3	1 0 1	Đường đi duy nhất thỏa mãn là $1 \to 3$ . Trạng thái $2$ không nằm trên đường đi nào hợp lệ.
3 1 2 0 1 1 3	0 0 0	Trạng thái $1$ chỉ có thao tác "sử dụng" trước khi có phép gán nào, và trạng thái $3$ chỉ có thao tác "gán" mà không có phép sử dụng phía sau. Không tồn tại đường đi hợp lệ nào.

Bình luận

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