JOI 2014 Final Camp - Ngày 2

Thành phố IOI, nơi JOI sinh sống, nổi tiếng là rất nóng quanh năm.

Thành phố IOI có dạng hình chữ nhật được chia thành \(H\) hàng và \(W\) cột ô vuông. Mỗi ô là một tòa nhà, một bãi đất trống hoặc một bức tường. Có \(P\) ô là tòa nhà, được đánh số từ \(1\) đến \(P\).

JOI chỉ có thể đi vào các ô là tòa nhà hoặc bãi đất trống. Từ một ô, JOI chỉ có thể đi trực tiếp sang một ô kề cạnh, tức là có chung một cạnh với ô đó. Trong quá trình di chuyển, JOI không được đi ra ngoài thành phố IOI.

JOI cần đi bộ giữa các tòa nhà để giải quyết nhiều công việc khác nhau. Bên trong các tòa nhà có điều hòa, nhưng các bãi đất trống rất nóng vì nắng gắt, nên mỗi lần đi qua một ô đất trống, JOI cần uống \(1\) đơn vị nước. Hơn nữa, các bãi đất trống không có máy bán hàng tự động hay vòi nước uống, nên người dân thành phố IOI thường mang theo bình nước khi di chuyển. Một bình nước có dung tích \(x\) chứa được tối đa \(x\) đơn vị nước. Trong các ô tòa nhà có vòi nước, vì vậy JOI có thể đổ đầy lại bình nước.

Bình nước lớn rất bất tiện khi mang theo, nên JOI muốn dùng bình nhỏ nhất có thể. Với một số chuyến đi giữa các tòa nhà, hãy viết chương trình tìm dung tích bình nước nhỏ nhất mà JOI cần để thực hiện chuyến đi đó.

Yêu cầu

Cho bản đồ thành phố IOI và \(Q\) câu hỏi. Câu hỏi thứ \(i\) (\(1 \le i \le Q\)) là: “Dung tích bình nước nhỏ nhất cần có để di chuyển giữa tòa nhà \(S_i\) và tòa nhà \(T_i\) là bao nhiêu?”. Hãy viết chương trình trả lời từng câu hỏi.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa bốn số nguyên \(H, W, P, Q\), cách nhau bởi dấu cách. Thành phố IOI có \(H\) hàng và \(W\) cột ô vuông, trong đó có \(P\) ô tòa nhà; chương trình cần trả lời \(Q\) câu hỏi.
• \(H\) dòng tiếp theo mô tả bản đồ thành phố IOI. Dòng thứ \(r\) trong số này (\(1 \le r \le H\)) chứa một xâu gồm \(W\) ký tự, mỗi ký tự là . hoặc #. Ký tự thứ \(c\) (\(1 \le c \le W\)) mô tả ô ở hàng thứ \(r\) từ trên xuống và cột thứ \(c\) từ trái sang. Ký tự . biểu thị tòa nhà hoặc bãi đất trống; ký tự # biểu thị tường.
• \(P\) dòng tiếp theo mô tả vị trí các tòa nhà. Dòng thứ \(j\) trong số này (\(1 \le j \le P\)) chứa hai số nguyên \(A_j, B_j\), cách nhau bởi dấu cách, cho biết tòa nhà \(j\) nằm ở hàng thứ \(A_j\) từ trên xuống và cột thứ \(B_j\) từ trái sang. Ô tương ứng trên bản đồ đã cho được bảo đảm là ..
• \(Q\) dòng tiếp theo mô tả các câu hỏi. Dòng thứ \(i\) trong số này (\(1 \le i \le Q\)) chứa hai số nguyên \(S_i, T_i\), cách nhau bởi dấu cách, cho biết câu hỏi thứ \(i\) yêu cầu tìm dung tích bình nước nhỏ nhất cần có để di chuyển giữa tòa nhà \(S_i\) và tòa nhà \(T_i\).

Dữ liệu ra

Ghi \(Q\) dòng ra đầu ra chuẩn. Dòng thứ \(i\) (\(1 \le i \le Q\)) chứa một số nguyên là dung tích bình nước nhỏ nhất cần có để di chuyển giữa tòa nhà \(S_i\) và tòa nhà \(T_i\). Nếu không thể di chuyển giữa hai tòa nhà, in -1. Nếu có thể di chuyển mà không đi qua ô đất trống nào, in 0.

Ràng buộc

Tất cả dữ liệu đầu vào thỏa mãn:

• \(1 \le H \le 2\,000\).
• \(1 \le W \le 2\,000\).
• \(2 \le P \le 200\,000\).
• \(1 \le Q \le 200\,000\).
• \(1 \le A_j \le H \quad (1 \le j \le P)\).
• \(1 \le B_j \le W \quad (1 \le j \le P)\).
• \((A_i, B_i) \ne (A_j, B_j) \quad (1 \le i < j \le P)\).
• \(1 \le S_i < T_i \le P \quad (1 \le i \le Q)\).

Phân nhóm

• Nhóm 1 (10 điểm): \(H \le 200\), \(W \le 200\), \(P \le 200\)
• Nhóm 2 (30 điểm): \(P \le 5\,000\), \(Q = 1\)
• Nhóm 3 (30 điểm): \(P \le 5\,000\), \(Q \le 10\,000\)
• Nhóm 4 (30 điểm): Không có ràng buộc bổ sung.

Ví dụ

5 5 4 4
.....
..##.
.#...
..#..
.....
1 1
4 2
3 3
2 5
1 2
2 4
1 3
3 4

3
4
4
2

5 5 3 2
...#.
..#..
#....
.##..
...#.
1 3
5 2
1 5
1 2
1 3

-1
7

Bạn là một điệp viên hoạt động phía sau những sự kiện lịch sử, ngày ngày nỗ lực vì hòa bình thế giới. Thế giới này có \(N\) quốc gia, được đánh số khác nhau từ \(1\) đến \(N\). Mục tiêu của bạn là giúp các quốc gia này xây dựng quan hệ hữu nghị với nhau nhiều nhất có thể. Để lên kế hoạch cho công việc, bạn đã vẽ một sơ đồ thể hiện quan hệ quốc tế hiện tại.

Bạn chuẩn bị một tờ giấy vẽ lớn và trước tiên đánh dấu \(N\) điểm, mỗi điểm biểu thị một quốc gia. Tiếp theo, để thể hiện quan hệ quốc tế hiện tại, bạn vẽ \(M\) mũi tên nối các cặp quốc gia. Mũi tên từ điểm biểu thị quốc gia \(a\) đến điểm biểu thị một quốc gia khác \(b\) có nghĩa là “hiện tại, quốc gia \(a\) đang cử đại sứ đến quốc gia \(b\)”. Từ đây, ta gọi mũi tên từ điểm biểu thị quốc gia \(a\) đến điểm biểu thị quốc gia \(b\) là mũi tên \((a, b)\). Như vậy, \(N\) điểm và \(M\) mũi tên vừa vẽ tạo thành sơ đồ quan hệ quốc tế hiện tại.

Để tạo cơ hội xây dựng quan hệ hữu nghị giữa các quốc gia, ta cân nhắc tổ chức hội nghị ký kết hiệp ước hữu nghị giữa hai quốc gia, sau đây gọi ngắn gọn là “hội nghị”. Để hai quốc gia \(p, q\) có thể tổ chức hội nghị, cần có một quốc gia \(x\) làm trung gian và đang cử đại sứ đến cả hai quốc gia đó. Sau hội nghị, mỗi quốc gia sẽ cử đại sứ đến quốc gia còn lại. Nói cách khác, để quốc gia \(p\) và quốc gia \(q\) tổ chức hội nghị, phải tồn tại quốc gia \(x\) sao cho có cả hai mũi tên \((x, p)\) và \((x, q)\). Sau hội nghị, ta vẽ thêm hai mũi tên \((p, q)\) và \((q, p)\). Tuy nhiên, nếu một mũi tên đã có sẵn thì không vẽ thêm mũi tên đó.

Công việc của bạn là chọn hai quốc gia có thể tổ chức hội nghị cùng với quốc gia làm trung gian, rồi cho họ tổ chức hội nghị. Khi mô phỏng công việc này bằng sơ đồ, bạn quyết định dùng số mũi tên trên giấy làm thước đo mức độ thế giới tiến gần đến hòa bình. Cụ thể, bạn muốn biết số mũi tên lớn nhất có thể có trên giấy sau khi lặp lại thao tác chọn hai quốc gia và cho họ tổ chức hội nghị.

Yêu cầu

Cho số quốc gia trên thế giới và thông tin về quan hệ quốc tế hiện tại. Hãy viết chương trình tìm số mũi tên lớn nhất có thể có trên giấy bằng cách lặp lại thao tác chọn hai quốc gia và cho họ tổ chức hội nghị.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên \(N, M\), cách nhau bởi dấu cách. \(N\) là số điểm trên giấy, cũng là số quốc gia trên thế giới; \(M\) là số mũi tên trên giấy.
• \(M\) dòng tiếp theo mô tả các mũi tên trên giấy. Dòng thứ \(i\) trong số này (\(1 \le i \le M\)) chứa hai số nguyên \(A_i, B_i\), cách nhau bởi dấu cách. Điều này có nghĩa là trên giấy có một mũi tên từ điểm biểu thị quốc gia \(A_i\) đến điểm biểu thị quốc gia \(B_i\), tức là quốc gia \(A_i\) đang cử đại sứ đến quốc gia \(B_i\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa số mũi tên lớn nhất có thể đạt được. Lưu ý rằng số này bao gồm cả các mũi tên đã có ban đầu và các mũi tên được vẽ thêm nhờ các hội nghị.

Ràng buộc

Tất cả dữ liệu đầu vào thỏa mãn:

• \(1 \le N \le 100\,000\).
• \(0 \le M \le 200\,000\).
• \(1 \le A_i \le N \quad (1 \le i \le M)\).
• \(1 \le B_i \le N \quad (1 \le i \le M)\).
• \(A_i \ne B_i \quad (1 \le i \le M)\).
• \((A_i, B_i) \ne (A_j, B_j) \quad (1 \le i < j \le M)\).

Phân nhóm

• Nhóm 1 (5 điểm): \(N \le 100\)
• Nhóm 2 (30 điểm): \(N \le 5\,000\)
• Nhóm 3 (65 điểm): Không có ràng buộc bổ sung.

Ví dụ

5 4
1 2
1 3
4 3
4 5

10

Đường sắt IOI có một tuyến đường thẳng gồm \(N + 2\) nhà ga. Các ga trên tuyến được đánh số lần lượt từ \(0\) đến \(N + 1\), bắt đầu từ một đầu tuyến.

Trên tuyến có hai loại tàu: tàu chiều tăng và tàu chiều giảm. Tàu chiều tăng di chuyển theo hướng số hiệu ga tăng dần; tàu chiều giảm di chuyển theo hướng số hiệu ga giảm dần. Đi tàu từ một ga sang ga liền kề mất \(T\) giây. Cụ thể, khi đi tàu chiều tăng, ta có thể đi từ ga \(i\) đến ga \(i + 1\) trong \(T\) giây; khi đi tàu chiều giảm, ta có thể đi từ ga \(i\) đến ga \(i - 1\) trong \(T\) giây. Tuy nhiên, không thể lên tàu chiều tăng tại ga \(N + 1\) hoặc lên tàu chiều giảm tại ga \(0\). Tàu đến rất thường xuyên, nên có thể bỏ qua thời gian chờ tàu.

Mỗi ga có một sân ga dành cho tàu chiều tăng và một sân ga dành cho tàu chiều giảm. Trên lối đi nối hai sân ga có đặt một bàn đóng dấu.

Hiện tại, đường sắt IOI đang tổ chức một hoạt động sưu tập dấu. Để hoàn thành hoạt động này, người tham gia phải xuất phát từ sân ga tàu chiều tăng của ga \(0\), lấy một dấu tại mỗi ga từ \(1\) đến \(N\), rồi đến sân ga tàu chiều tăng của ga \(N + 1\).

Để lấy dấu tại một ga, người tham gia phải xuống tàu rồi đi bộ đến bàn đóng dấu nằm trên lối đi của ga. Thời gian di chuyển giữa sân ga tàu chiều tăng, bàn đóng dấu và sân ga tàu chiều giảm tại ga \(i\) được cho như sau:

• Từ sân ga tàu chiều tăng của ga \(i\) đến bàn đóng dấu: \(U_i\) giây.
• Từ bàn đóng dấu đến sân ga tàu chiều tăng của ga \(i\): \(V_i\) giây.
• Từ sân ga tàu chiều giảm của ga \(i\) đến bàn đóng dấu: \(D_i\) giây.
• Từ bàn đóng dấu đến sân ga tàu chiều giảm của ga \(i\): \(E_i\) giây.

Người tham gia chỉ được ghé ga \(0\) và ga \(N + 1\) mỗi ga một lần. Tại các ga từ \(1\) đến \(N\), người tham gia có thể xuống tàu bao nhiêu lần tùy ý.

Cấu trúc ga \(i\).

Yêu cầu

Cho số ga có dấu cần sưu tập, thời gian đi tàu giữa hai ga liền kề, thời gian di chuyển giữa sân ga tàu chiều tăng và bàn đóng dấu tại mỗi ga, cùng thời gian di chuyển giữa sân ga tàu chiều giảm và bàn đóng dấu tại mỗi ga. Hãy viết chương trình tìm thời gian ít nhất để hoàn thành hoạt động sưu tập dấu.

Thời gian hoàn thành được tính từ lúc xuất phát tại ga \(0\), lấy đủ \(N\) dấu, cho đến khi đến sân ga tàu chiều tăng của ga \(N + 1\). Có thể bỏ qua thời gian chờ tàu ở sân ga và thời gian đóng dấu.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên \(N, T\), cách nhau bởi dấu cách. Tuyến đường có \(N + 2\) ga và thời gian đi tàu giữa hai ga liền kề là \(T\) giây.
• \(N\) dòng tiếp theo mô tả thời gian di chuyển tại các ga. Dòng thứ \(i\) trong số này (\(1 \le i \le N\)) chứa bốn số nguyên \(U_i, V_i, D_i, E_i\), cách nhau bởi dấu cách, với ý nghĩa như sau:

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên là thời gian ít nhất, tính bằng giây, để hoàn thành hoạt động sưu tập dấu.

Ràng buộc

Tất cả dữ liệu đầu vào thỏa mãn:

• \(1 \le N \le 3\,000\).
• \(1 \le T \le 100\,000\).
• \(1 \le U_i \le 100\,000 \quad (1 \le i \le N)\).
• \(1 \le V_i \le 100\,000 \quad (1 \le i \le N)\).
• \(1 \le D_i \le 100\,000 \quad (1 \le i \le N)\).
• \(1 \le E_i \le 100\,000 \quad (1 \le i \le N)\).

Phân nhóm

• Nhóm 1 (10 điểm): \(N \le 16\)
• Nhóm 2 (75 điểm): \(N \le 100\)
• Nhóm 3 (15 điểm): Không có ràng buộc bổ sung.

Ví dụ

4 1
1 1 1 1
1 9 9 1
9 9 1 1
1 9 9 1

23

6 2
5 5 3 5
9 7 9 3
3 4 9 4
8 2 6 6
8 5 7 5
3 2 1 6

73