trang chủ / đề bài / icpcwf21_i

Nhện đi dạo

Đề bài

Mô tả

Cô nhện Charlotte ngồi ở tâm mạng nhện của mình. Mạng nhện gồm một số sợi tơ thẳng (gọi là các tia) đi từ tâm ra tới biên ngoài của mạng. Mạng nhện còn có các cầu, mỗi cầu nối hai tia kề nhau. Hai đầu mút của một cầu luôn cách tâm mạng nhện cùng một khoảng.

Sau một bữa tiệc đêm ở tâm mạng, khi muốn lui về một góc nào đó, Charlotte đi ra biên theo chế độ tự động. Cô chọn một tia xuất phát và đi dọc theo tia đó (ra xa tâm) cho tới khi gặp cầu đầu tiên trên tia. Cô đi qua cầu sang tia bên kia, rồi tiếp tục đi ra xa tâm cho tới khi gặp một cầu khác. Cô lại đi qua cầu đó, và cứ lặp lại như vậy cho tới khi trên tia hiện tại không còn cầu nào phía trước, khi đó cô đi tới đầu mút ngoài của tia hiện tại. Lưu ý rằng Charlotte bắt buộc phải đi qua mọi cầu mà cô gặp. Hình dưới minh họa một đường đi của Charlotte.

Đường đi (màu đỏ) xuất phát từ tia 4 trên mạng nhện của ví dụ 1.

Góc ngủ ban ngày ưa thích của Charlotte là đầu mút ngoài của tia s. Với mỗi tia xuất phát có thể, cô muốn biết số cầu ít nhất cần thêm vào mạng nhện ban đầu để cô kết thúc tại tia s. Charlotte có thể thêm cầu tại bất kỳ vị trí nào dọc theo các tia, miễn là cầu thêm vào không chạm vào bất kỳ cầu nào khác. Hai đầu mút của mỗi cầu thêm vào phải cách tâm mạng nhện cùng một khoảng, và cầu phải nối hai tia kề nhau.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên n, m và s: n là số tia, m là số cầu, s là tia ưa thích của Charlotte. Các tia được đánh số từ 1 tới n theo chiều ngược chiều kim đồng hồ.

Mỗi dòng trong m dòng tiếp theo chứa hai số nguyên d và t mô tả một cầu: d là khoảng cách từ cầu tới tâm mạng nhện, t là tia đầu tiên của cầu theo chiều ngược chiều kim đồng hồ. Cụ thể, nếu 1≤t<n thì cầu nối tia t và tia t+1; nếu t=n thì cầu nối tia 1 và tia n.

Dữ liệu ra

In ra n dòng, dòng thứ i là số cầu ít nhất Charlotte cần thêm vào để kết thúc tại tia s khi đi tự động bắt đầu từ tia i.

Ràng buộc

  • 3≤n≤200000, 0≤m≤500000, 1≤s≤n.
  • 1≤d≤109, 1≤t≤n.
  • Các khoảng cách d của các cầu đôi một khác nhau.

Ví dụ

Input Output Giải thích
7 5 6
2 1
4 3
6 3
8 7
10 5
2
1
1
1
0
1
2
Đây là mạng nhện trong hình. Từ tia 5, Charlotte gặp cầu ở khoảng cách 10 nối tia 5 và 6, sang tia 6 và đi ra biên, nên không cần thêm cầu. Từ tia 4, cô sang tia 3 (cầu khoảng cách 4), quay lại tia 4 (cầu khoảng cách 6) rồi đi ra biên tia 4; thêm một cầu nối tia 4 và 5 ở khoảng cách 7 thì cô đi sang tia 5, rồi qua cầu khoảng cách 10 sang tia 6.
4 4 2
1 1
2 2
3 3
4 4
1
1
0
1
Từ tia 3, Charlotte qua cầu khoảng cách 2 sang tia 2; phía trước trên tia 2 không còn cầu nào nên cô kết thúc tại tia 2. Từ tia 1, cô lần lượt đi qua cả bốn cầu và kết thúc tại tia 1, nên cần thêm một cầu.

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