The Chase

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.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

Bessie cố gắng trốn thoát khỏi các nông dân trên $N$ trang trại được nối bởi đường một chiều. Mỗi trang trại $i$ có đúng một đường đi đến trang trại $a_{i}$ (với $a_{i} \neq i$ ).

$F$ nông dân bắt đầu tại các vị trí $s_{1}, s_{2}, \dots, s_{F}$ (đôi một khác nhau). Mỗi bước thời gian, tất cả nông dân đồng thời di chuyển theo đường đi duy nhất từ vị trí hiện tại.

Bessie chọn trang trại bắt đầu $b$ và mỗi bước có thể chọn nghỉ (ở yên) hoặc di chuyển (theo đường đi). Bessie di chuyển đồng thời với nông dân. Bessie bị bắt nếu cô ở cùng trang trại với bất kỳ nông dân nào tại bất kỳ thời điểm nào.

Với mỗi trang trại $b$ từ $1$ đến $N$ , hãy tìm số lần tối đa Bessie có thể chọn nghỉ.

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ ( $2 \leq N \leq 5 \times 10^{5}$ ) và $F$ ( $1 \leq F \leq N$ ).
Dòng 2: $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$ ( $a_{i} \neq i$ ).
Dòng 3: $F$ số nguyên $s_{1}, s_{2}, \dots, s_{F}$ (đôi một khác nhau).

Dữ liệu ra

In $N$ dòng, dòng thứ $b$ chứa một số nguyên:

Số lần nghỉ tối đa nếu hữu hạn.
$- 1$ nếu Bessie bị bắt ngay lập tức hoặc không thể tránh.
$- 2$ nếu Bessie có thể nghỉ vô hạn lần.

Ràng buộc

$2 \leq N \leq 5 \times 10^{5}$
$1 \leq F \leq N$
$a_{i} \neq i$
Các $s_{i}$ đôi một khác nhau

Ví dụ

Input	Output	Giải thích
4 1 2 1 4 3 1	-1 0 -2 -2	Nông dân ở trang trại 1, di chuyển 1->2->1->2... Trang trại 1: bị bắt ngay (-1). Trang trại 2: phải di chuyển ngay bước đầu để tránh nông dân đến (0 lần nghỉ). Trang trại 3,4: chu kỳ 3->4->3, nông dân không bao giờ đến (-2).

Bình luận

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