trang chủ / đề bài / icpc22_mb_f

Món quà

Đề bài

Mô tả

Tuấn tặng con trai một đồ thị có hướng không trọng số làm quà sinh nhật. Đồ thị có n đỉnh, đánh số từ 1 đến n, và m cạnh có hướng, đánh số từ 1 đến m.

Tuấn muốn kiểm tra IQ của con bằng một trò chơi. Trò chơi gồm Q lượt, ở mỗi lượt Tuấn yêu cầu con giải một trong hai loại câu hỏi sau:

  1. Xóa một cạnh khỏi đồ thị.
  2. Tìm độ dài đường đi ngắn nhất từ đỉnh 1 đến một đỉnh v.

Tuấn muốn con trả lời mỗi câu hỏi loại thứ hai ngay lập tức, không được biết trước bất kỳ câu hỏi nào phía sau.

Lưu ý:

  • Một đường đi độ dài t của đồ thị là một dãy đỉnh v1,v2,…,vt,vt+1 sao cho có cạnh từ vi đến vi+1 với mọi 1≤i≤t.
  • Một đường đi độ dài t là đường đi ngắn nhất từ a đến b nếu không tồn tại đường đi nào khác từ a đến b có độ dài nhỏ hơn t.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên n và m là số đỉnh và số cạnh của đồ thị (1≤n≤3500, 1≤m≤35000).
  • Dòng thứ i trong m dòng tiếp theo chứa hai số nguyên ui và vi, nghĩa là có một cạnh có hướng từ ui đến vi.
  • Dòng tiếp theo chứa một số nguyên Q là số câu hỏi (1≤Q≤5×105).
  • Q dòng còn lại mô tả các câu hỏi, mỗi câu hỏi có một trong hai dạng sau:
    • 1 x: xóa cạnh có chỉ số id=(x+last)modm+1, trong đó last là câu trả lời của câu hỏi loại 2 gần nhất trước đó. Trước câu hỏi loại 2 đầu tiên, last=0. Nếu không có đường đi từ 1 đến đỉnh được hỏi thì last=−1. Đảm bảo mỗi cạnh bị xóa nhiều nhất một lần.
    • 2 v: hỏi độ dài đường đi ngắn nhất từ đỉnh 1 đến đỉnh v.

Dữ liệu ra

Với mỗi câu hỏi loại thứ hai, in câu trả lời trên một dòng. Nếu không có đường đi từ 1 đến v, in ra −1.

Ràng buộc

  • 1≤n≤3500, 1≤m≤35000.
  • 1≤ui,vi≤n.
  • 1≤Q≤5×105.
  • Với câu hỏi loại 1: x≥0 và x+last≥0; mỗi cạnh bị xóa nhiều nhất một lần.
  • Với câu hỏi loại 2: 1≤v≤n.

Ví dụ

Input Output Giải thích
4 6
1 4
1 3
4 2
1 2
2 3
3 4
7
1 1
2 3
1 1
2 3
2 2
1 0
2 3
2
3
2
-1
Các cạnh thực sự bị xóa lần lượt là cạnh 2, 4 và 3. Ví dụ, câu hỏi thứ ba có x=1, last=2 nên xóa cạnh (1+2)mod6+1=4.
5 7
1 2
2 3
3 4
1 3
4 5
2 2
5 1
9
2 5
1 0
2 5
2 1
1 2
2 4
2 5
1 1
2 2
3
4
0
-1
-1
-1
Các cạnh bị xóa lần lượt là cạnh 4 (1→3), 3 (3→4) và 1 (1→2). Câu hỏi xóa cuối cùng có last=−1 nên xóa cạnh (1−1)mod7+1=1.

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