JOI 2013 Final Camp - Ngày 2

Đất nước IOI quyết định xây dựng đồng bộ mạng lưới giao thông. Đất nước được biểu diễn trên mặt phẳng tọa độ \(xy\), với \(N\) thị trấn. Thị trấn thứ \(i\) nằm tại \((X_i,Y_i)\).

Việc xây dựng gồm hai phần:

• Chọn một số thị trấn để xây sân bay quốc tế. Phải xây ít nhất một sân bay. Mỗi sân bay có một chi phí xây dựng cố định.
• Xây một số con đường nối các thị trấn. Mỗi đường là một đoạn thẳng nối trực tiếp hai điểm biểu diễn hai thị trấn và song song với trục \(x\) hoặc trục \(y\). Chi phí xây mỗi đường bằng độ dài của nó.

Có \(M\) khu vực không thể xây đường, chẳng hạn do nền đất yếu. Khu vực thứ \(j\) là hình chữ nhật có góc dưới bên trái tại \((P_j,Q_j)\) và góc trên bên phải tại \((R_j,S_j)\), với \(P_j<R_j\) và \(Q_j<S_j\). Mỗi khu vực bao gồm cả phần biên. Không con đường nào được có điểm chung với bất kỳ khu vực cấm nào, kể cả biên của khu vực đó.

Sau khi xây dựng, từ mỗi thị trấn phải có thể đến một thị trấn có sân bay quốc tế bằng cách đi theo các con đường từ thị trấn này sang thị trấn khác.

Có \(C\) công ty xây dựng đang được xem xét để giao toàn bộ dự án. Công ty thứ \(k\) cần chi phí \(B_k\) cho mỗi sân bay và có thể xây tối đa \(H_k\) sân bay. Chi phí xây đường không phụ thuộc công ty; không có giới hạn về số lượng hay độ dài các con đường.

Với mỗi công ty, cần tìm tổng chi phí nhỏ nhất để đáp ứng các điều kiện trên. Một công ty có thể không thực hiện được dự án do giới hạn số sân bay quá thấp.

Yêu cầu

Cho tọa độ các thị trấn, các khu vực cấm xây đường và thông tin các công ty, hãy tính tổng chi phí nhỏ nhất nếu giao dự án cho từng công ty, hoặc xác định rằng công ty đó không thể thực hiện dự án.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa ba số nguyên \(N,M,C\), lần lượt là số thị trấn, số khu vực cấm xây đường và số công ty.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(X_i,Y_i\), là tọa độ thị trấn thứ \(i\).
• Trong \(M\) dòng tiếp theo, dòng thứ \(j\) chứa bốn số nguyên \(P_j,Q_j,R_j,S_j\), mô tả khu vực cấm thứ \(j\).
• Trong \(C\) dòng tiếp theo, dòng thứ \(k\) chứa hai số nguyên \(B_k,H_k\), là chi phí xây một sân bay và số sân bay tối đa của công ty thứ \(k\).

Dữ liệu ra

Ghi ra đầu ra chuẩn \(C\) dòng. Dòng thứ \(k\) chứa tổng chi phí nhỏ nhất nếu công ty thứ \(k\) thực hiện dự án. Nếu công ty đó không thể đáp ứng các điều kiện, ghi -1.

Ràng buộc

• Giới hạn thời gian: 5 giây.
• Giới hạn bộ nhớ: 256 MB.
• \(1\le N\le200000\).
• \(1\le M\le200000\).
• \(1\le C\le500000\).
• \(0\le X_i,Y_i\le10^9\).
• Không có hai thị trấn trùng tọa độ.
• \(0\le P_j<R_j\le10^9\) và \(0\le Q_j<S_j\le10^9\).
• Không thị trấn nào nằm trong hoặc trên biên của bất kỳ khu vực cấm nào.
• \(1\le B_k\le10^9\) và \(1\le H_k\le N\).

Phân nhóm

Mỗi nhóm gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi chương trình trả lời đúng tất cả bộ dữ liệu trong nhóm.

• Nhóm 1 (10 điểm): \(M\le100\), \(C\le100\).
• Nhóm 2 (30 điểm): \(C\le100\).
• Nhóm 3 (30 điểm): \(M\le100\).
• Nhóm 4 (30 điểm): Không có ràng buộc bổ sung.

4 2 3
1 1
10 1
1 10
10 10
4 0 8 9
1 4 9 8
7 4
10 3
1 1

28
38
-1

Có thể xây đường nối thị trấn \(2\) với \(4\) và thị trấn \(3\) với \(4\). Không thể xây đường nối thị trấn \(1\) với \(2\) vì đường đó đi qua khu vực cấm. Cũng không thể xây đường nối thị trấn \(1\) với \(3\), vì đường không được có điểm chung ngay cả với biên của khu vực cấm.

• Công ty thứ nhất xây được tối đa \(4\) sân bay với chi phí \(7\) mỗi sân bay. Phương án tốt nhất là xây sân bay tại cả bốn thị trấn và không xây đường nào, với tổng chi phí \(7\times4=28\).
• Công ty thứ hai xây được tối đa \(3\) sân bay với chi phí \(10\) mỗi sân bay. Một phương án tốt nhất là xây hai đường dài \(9\) nối \(2\) với \(4\) và \(3\) với \(4\), rồi xây sân bay ở thị trấn \(1\) và \(2\). Tổng chi phí là \(10\times2+9+9=38\).
• Công ty thứ ba chỉ xây được tối đa một sân bay với chi phí \(1\). Do không thể xây đường nối thị trấn \(1\) với bất kỳ thị trấn nào khác, dự án cần ít nhất hai sân bay. Công ty này không thể thực hiện dự án, nên kết quả là -1.

JOI vừa chơi với các bạn bằng những con thú linh vật. Các bạn đã về và giờ là lúc dọn dẹp.

JOI có \(R\times C\) con thú và dùng một bảng hình chữ nhật gồm \(R\) hàng, \(C\) cột để cất chúng. Mỗi ô chứa một con thú. Ô ở hàng \(A\) tính từ trên xuống và cột \(B\) tính từ trái sang được ký hiệu là \((A,B)\).

Ban đầu đã có \(N\) con thú được đặt vào các ô, và còn ít nhất một ô trống. JOI đặt lần lượt từng con thú còn lại vào một ô trống cho đến khi lấp đầy bảng. Các con thú không được phân biệt theo loại; một cách đặt được xác định bởi thứ tự các ô được lấp đầy.

Sau mỗi lần đặt thêm một con thú, nếu toàn bộ các ô có thú tạo thành đúng một hình chữ nhật thì JOI cảm thấy vui một lần. Nếu trạng thái ban đầu đã là một hình chữ nhật thì trạng thái đó không được tính.

Cụ thể, toàn bộ các ô có thú tạo thành một hình chữ nhật khi tồn tại bốn số nguyên \(r_1,r_2,c_1,c_2\) thỏa mãn \(1\le r_1\le r_2\le R\) và \(1\le c_1\le c_2\le C\), sao cho mọi ô \((i,j)\) với \(r_1\le i\le r_2\) và \(c_1\le j\le c_2\) đều có thú, còn tất cả ô khác đều không có thú.

JOI càng có nhiều lần cảm thấy vui thì tối nay càng ngủ ngon. Có bao nhiêu cách đặt các con thú để số lần cảm thấy vui đạt giá trị lớn nhất?

Yêu cầu

Cho kích thước bảng và vị trí những con thú đã được đặt, hãy đếm số thứ tự đặt các con thú còn lại làm số lần cảm thấy vui lớn nhất. Tính kết quả theo modulo \(1000000007\).

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên \(R,C\), là số hàng và số cột của bảng.
• Dòng thứ hai chứa số nguyên \(N\), là số con thú đã được đặt.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(A_i,B_i\), cho biết ô \((A_i,B_i)\) ban đầu đã có thú. Các cặp tọa độ này đôi một khác nhau.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là số cách đặt đạt số lần cảm thấy vui lớn nhất, lấy phần dư khi chia cho \(1000000007\).

Ràng buộc

• Giới hạn thời gian: 2 giây.
• Giới hạn bộ nhớ: 256 MB.
• \(2\le R,C\le3000\).
• \(1\le N\le100000\) và \(N<R\times C\).
• \(1\le A_i\le R\) và \(1\le B_i\le C\).
• Các ô ban đầu có thú đôi một khác nhau.

Phân nhóm

Mỗi nhóm gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi chương trình trả lời đúng tất cả bộ dữ liệu trong nhóm.

• Nhóm 1 (10 điểm): \(R,C\le3\).
• Nhóm 2 (30 điểm): \(R,C\le50\).
• Nhóm 3 (60 điểm): Không có ràng buộc bổ sung.

2 3
2
1 2
2 2

8

Trong sáu ô, hai ô \((1,2)\) và \((2,2)\) ban đầu đã có thú. Số lần cảm thấy vui lớn nhất là \(2\). Có đúng tám thứ tự đặt đạt giá trị này:

Trong mỗi cách, sau lần đặt thứ \(2\), các ô có thú tạo thành hình chữ nhật \(2\times2\); sau lần đặt thứ \(4\), chúng tạo thành hình chữ nhật \(2\times3\). Vì vậy JOI cảm thấy vui tổng cộng hai lần.

3 3
2
1 1
3 3

5040

Dù đặt theo thứ tự nào, JOI cũng chỉ cảm thấy vui một lần, khi toàn bộ bảng được lấp đầy. Vì còn \(7\) ô trống nên có \(7!=5040\) cách đặt.

Công ty Just Odd Inventions, gọi tắt là JOI, chuyên tạo ra những phát minh kỳ lạ. Công ty Incredibly Odd Inventions, gọi tắt là IOI, chuyên tạo ra những phát minh kỳ lạ đến khó tin. IOI luôn đánh cắp thông tin về các dự án nghiên cứu của JOI để tạo ra các phát minh của mình.

Mỗi công ty có \(N\) nhân viên. Nhân viên của JOI được gọi là \(j_1,j_2,\ldots,j_N\), còn nhân viên của IOI là \(i_1,i_2,\ldots,i_N\). Trong mỗi công ty có đúng một nhân viên là giám đốc. Mỗi nhân viên khác có đúng một cấp trên trực tiếp trong cùng công ty.

JOI vừa bắt đầu \(M\) dự án nghiên cứu \(r_1,r_2,\ldots,r_M\), còn IOI bắt đầu \(M\) dự án gián điệp \(s_1,s_2,\ldots,s_M\). Dự án gián điệp \(s_b\) nhằm đánh cắp thông tin của dự án nghiên cứu \(r_b\).

Hai công ty xác định thành viên dự án theo cùng một cách. Mỗi dự án có một trưởng dự án. Trưởng dự án ra lệnh cho tất cả cấp dưới trực tiếp của mình; mỗi người nhận lệnh lại truyền lệnh cho tất cả cấp dưới trực tiếp của họ. Thành viên dự án gồm trưởng dự án và mọi nhân viên nhận được lệnh, không có ai khác.

Nhân viên \(i_a\) chỉ đánh cắp thông tin từ nhân viên \(j_a\). Nếu \(i_a\) thuộc dự án gián điệp \(s_b\) và \(j_a\) thuộc dự án nghiên cứu \(r_b\), thì \(i_a\) thành công trong dự án \(s_b\). Mỗi nhân viên có thể thuộc nhiều dự án, và một nhân viên IOI có thể thành công trong nhiều dự án gián điệp.

Yêu cầu

Cho cơ cấu nhân viên và thông tin các dự án của hai công ty, hãy tính với mỗi nhân viên IOI số dự án gián điệp mà người đó thành công.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên \(N,M\). Mỗi công ty có \(N\) nhân viên và \(M\) dự án.
• Trong \(N\) dòng tiếp theo, dòng thứ \(a\) chứa hai số nguyên \(P_a,Q_a\). Nếu \(P_a\ne0\) thì \(j_a\) là cấp dưới trực tiếp của \(j_{P_a}\); nếu \(P_a=0\) thì \(j_a\) là giám đốc JOI. Tương tự, nếu \(Q_a\ne0\) thì \(i_a\) là cấp dưới trực tiếp của \(i_{Q_a}\); nếu \(Q_a=0\) thì \(i_a\) là giám đốc IOI.
• Trong \(M\) dòng tiếp theo, dòng thứ \(b\) chứa hai số nguyên \(R_b,S_b\). Trưởng dự án nghiên cứu \(r_b\) là \(j_{R_b}\), còn trưởng dự án gián điệp \(s_b\) là \(i_{S_b}\).

Dữ liệu ra

Ghi ra đầu ra chuẩn \(N\) dòng. Dòng thứ \(a\) chứa một số nguyên là số dự án gián điệp mà nhân viên \(i_a\) thành công.

Ràng buộc

• Giới hạn thời gian: 2 giây.
• Giới hạn bộ nhớ: 256 MB.
• \(1\le N\le2000\).
• \(1\le M\le500000\).
• \(0\le P_a,Q_a\le N\).
• \(1\le R_b,S_b\le N\).
• Mỗi công ty có đúng một giám đốc; mỗi nhân viên khác có đúng một cấp trên trực tiếp trong cùng công ty.

Phân nhóm

Mỗi nhóm gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi chương trình trả lời đúng tất cả bộ dữ liệu trong nhóm.

• Nhóm 1 (10 điểm): \(N\le200\), \(M\le200\).
• Nhóm 2 (20 điểm): \(M\le2000\).
• Nhóm 3 (70 điểm): Không có ràng buộc bổ sung.

3 4
0 2
1 0
2 2
1 1
2 1
2 3
3 2

1
0
2

Trong JOI, giám đốc là \(j_1\), \(j_2\) là cấp dưới trực tiếp của \(j_1\), và \(j_3\) là cấp dưới trực tiếp của \(j_2\). Trong IOI, giám đốc là \(i_2\), còn \(i_1\) và \(i_3\) đều là cấp dưới trực tiếp của \(i_2\). Các dự án có thành viên như sau:

• Nhân viên \(i_1\) thuộc các dự án \(s_1,s_2,s_4\). Vì \(j_1\) thuộc \(r_1\), người này thành công trong dự án \(s_1\).
• Nhân viên \(i_2\) thuộc dự án \(s_4\). Vì \(j_2\) không thuộc \(r_4\), người này không thành công trong dự án gián điệp nào.
• Nhân viên \(i_3\) thuộc các dự án \(s_3,s_4\). Vì \(j_3\) thuộc cả \(r_3\) lẫn \(r_4\), người này thành công trong cả hai dự án \(s_3,s_4\).