trang chủ / đề bài / icpc26_mt_m

Vành đai Aegis

Đề bài

Mô tả

Trong vành đai phòng thủ không gian Aegis, một hệ thống gồm N trạm tiền tiêu được bố trí thành một vòng khép kín, đánh số từ 1 đến N theo chiều kim đồng hồ.

Giữa hai trạm kề nhau trên vòng có một dây cáp điện hai chiều:

  • Dây cáp thứ i nối trạm i và trạm i+1 (với 1≤i≤N−1); ngắt dây này tiết kiệm được lượng năng lượng Bi.
  • Dây cáp thứ N nối trạm N và trạm 1; ngắt dây này tiết kiệm được lượng năng lượng BN.

Bộ chỉ huy quân sự thiết lập M liên kết chiến lược khẩn cấp. Liên kết thứ j yêu cầu hai trạm uj và vj (uj≠vj) phải giữ được liên lạc với nhau theo mạng các dây cáp còn hoạt động.

Để hỗ trợ điều phối, bộ chỉ huy đề xuất Q phương án bảo trì độc lập. Trong phương án thứ k, bộ chỉ huy chỉ định một khu vực chiến lược gồm các dây cáp có chỉ số liên tiếp từ Lk đến Rk (1≤Lk≤Rk≤N):

  • Mọi dây cáp nằm ngoài khu vực [Lk,Rk] phải tiếp tục hoạt động.
  • Trong khu vực [Lk,Rk], bộ chỉ huy muốn ngắt một tập con các dây cáp sao cho tổng năng lượng tiết kiệm được là lớn nhất, đồng thời mọi liên kết trong M liên kết chiến lược trên toàn vành đai vẫn không bị gián đoạn.

Hãy xác định tổng năng lượng tiết kiệm lớn nhất có thể đạt được trong khu vực của mỗi phương án bảo trì.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên N, M và Q (3≤N≤2·105, 1≤M≤2·105, 1≤Q≤2·105): số trạm tiền tiêu, số liên kết chiến lược và số phương án bảo trì.
  • Dòng thứ hai chứa N số nguyên dương B1,B2,…,BN (1≤Bi≤109): năng lượng tiết kiệm được khi ngắt từng dây cáp tương ứng.
  • M dòng tiếp theo, dòng thứ j chứa hai số nguyên uj và vj (1≤uj,vj≤N, uj≠vj): hai trạm của liên kết chiến lược thứ j.
  • Q dòng tiếp theo, dòng thứ k chứa hai số nguyên Lk và Rk (1≤Lk≤Rk≤N): khu vực của phương án bảo trì thứ k.

Dữ liệu ra

In ra Q dòng, mỗi dòng chứa một số nguyên là tổng năng lượng tiết kiệm lớn nhất của phương án tương ứng.

Ràng buộc

  • 3≤N≤2·105, 1≤M≤2·105, 1≤Q≤2·105.
  • 1≤Bi≤109.
  • 1≤uj,vj≤N, uj≠vj.
  • 1≤Lk≤Rk≤N.

Ví dụ

Input Output Giải thích
5 2 2
10 20 15 30 40
1 3
2 4
1 5
2 4
70
30
Vành đai có 5 dây cáp với B=[10,20,15,30,40] và 2 liên kết (1,3), (2,4). Phương án 1 (L=1,R=5): khu vực là cả vòng; có thể ngắt đồng thời hai dây e4 và e5 mà cả hai cặp (1,3) và (2,4) vẫn liên lạc được, tiết kiệm B4+B5=30+40=70. Phương án 2 (L=2,R=4): khu vực gồm {e2,e3,e4}, các dây e1,e5 phải giữ nguyên; không thể ngắt đồng thời hai dây nào trong khu vực vì sẽ làm đứt ít nhất một liên kết, nên chỉ ngắt dây có lợi nhất là e4, tiết kiệm B4=30.
6 1 3
5 1 4 2 3 6
2 5
1 6
2 4
3 3
14
7
4
Liên kết (2,5) cho phép ngắt nhiều dây cùng lúc khi tất cả nằm trên cùng một cung giữa trạm 2 và trạm 5: cung {e2,e3,e4} hoặc cung {e5,e6,e1}. Phương án 1: ngắt e5,e6,e1, tiết kiệm 3+6+5=14. Phương án 2: ngắt e2,e3,e4, tiết kiệm 1+4+2=7. Phương án 3: chỉ ngắt e3, tiết kiệm 4.

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