trang chủ / đề bài / icpcwf19_h

Những chuyến tàu của Hobson

Đề bài

Mô tả

Ông Hobson đã thôi điều hành trại ngựa và chuyển sang đầu tư vào một loại hình giao thông hiện đại hơn: tàu hỏa. Ông xây dựng một mạng lưới đường sắt gồm n ga. Tuy vậy, ông vẫn giữ cam kết giải phóng hành khách khỏi gánh nặng có quá nhiều lựa chọn: từ mỗi ga, hành khách có thể đi tàu tới đúng một ga khác. Một chuyến đi như vậy được gọi là một chặng. Lưu ý rằng chặng là hành trình một chiều, và có thể không quay lại được.

Hobson cũng chỉ bán đúng một loại vé, cho phép hành khách đi tối đa k chặng trong một hành trình. Ở lối ra của mỗi ga có một máy đọc vé tự động (chỉ một máy, để hành khách không phải chọn dùng máy nào). Máy kiểm tra rằng khoảng cách từ ga xuất phát tới ga cuối cùng không vượt quá k chặng.

Mỗi máy đọc vé phải được nạp danh sách các ga xuất phát hợp lệ, nhưng danh sách càng tốn bộ nhớ thì máy càng đắt. Hãy giúp Hobson xác định, với mỗi ga A, số ga (tính cả chính A) mà từ đó hành khách có thể tới A bằng không quá k chặng.

Hình dưới minh họa ví dụ thứ nhất: mỗi đỉnh là một ga, nhãn cạnh mỗi đỉnh là danh sách các ga xuất phát được nạp vào máy đọc vé của ga đó khi k=2.

graph directed
1 2
2 3
3 4
4 5
5 4
6 3
label 1 {1}
label 2 {1,2}
label 3 {1,2,3,6}
label 4 {2,3,4,5,6}
label 5 {3,4,5}
label 6 {6}

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và k, trong đó n là số ga và k là số chặng tối đa được đi bằng một vé.

Tiếp theo là n dòng, dòng thứ i chứa một số nguyên di: ga có thể tới được từ ga i bằng một chặng.

Dữ liệu ra

In ra n dòng, dòng thứ i chứa số ga mà từ đó có thể tới ga i bằng không quá k chặng.

Ràng buộc

  • 2≤n≤5·105.
  • 1≤k≤n−1.
  • 1≤di≤n và di≠i.

Ví dụ

Input Output Giải thích
6 2
2
3
4
5
4
3
1
2
4
5
3
1
Mạng lưới trong hình trên. Ví dụ ga 4 tới được từ các ga 2,3,4,5,6 (ga 2 qua 3, ga 6 qua 3, ga 5 đi một chặng), còn ga 1 cần 3 chặng nên không được tính.
5 3
2
3
1
5
4
3
3
3
2
2
Hai vòng tách rời 1→2→3→1 và 4→5→4. Mỗi ga tới được từ mọi ga cùng vòng của nó.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0