JOI Open Contest 2014 - Ngày 2

Vào năm 21XX, Vương quốc JOI quyết định di dân đến hành tinh IOI mới được phát hiện.

Vương quốc có \(N\) dân tộc, đánh số từ \(1\) đến \(N\), và có \(M\) cặp dân tộc có quan hệ hữu nghị. Trên hành tinh IOI có \(L\) khu dân cư, đánh số từ \(1\) đến \(L\), với \(L\ge N\). Khu dân cư \(i\) là điểm \(P_i=(X_i,Y_i)\) trên mặt phẳng tọa độ.

Bạn phải gán cho mỗi dân tộc đúng một khu dân cư, và không khu dân cư nào được gán cho nhiều hơn một dân tộc. Với mỗi cặp dân tộc có quan hệ hữu nghị, một đường ray thẳng sẽ nối hai khu dân cư của họ. Hai đường ray có thể cắt nhau tùy theo cách gán.

Mục tiêu là đưa ra một phương án làm nhỏ nhất số cặp đường ray cắt nhau.

Dữ liệu vào

Bài có năm bộ dữ liệu công khai, mỗi bộ tương ứng với một nhóm. Mỗi tệp có định dạng:

• Dòng đầu gồm \(N,M\).
• \(M\) dòng tiếp theo, dòng thứ \(j\) gồm \(A_j,B_j\), biểu thị hai dân tộc có quan hệ hữu nghị.
• Dòng tiếp theo chứa \(L\).
• \(L\) dòng tiếp theo, dòng thứ \(i\) gồm \(X_i,Y_i\), là tọa độ khu dân cư \(P_i\).

Dữ liệu ra

Với mỗi tệp đầu vào, nộp một tệp đầu ra gồm \(N\) dòng. Dòng thứ \(k\) chứa chỉ số khu dân cư được gán cho dân tộc \(k\).

Các chỉ số được in phải đôi một khác nhau và nằm trong đoạn \([1,L]\).

Ràng buộc

• \(1 \le A_j,B_j \le N\).
• \(1 \le X_i,Y_i \le 100\,000\).
• Không có ba điểm \(P_i,P_j,P_k\) nào thẳng hàng.
• Đồ thị hữu nghị liên thông.
• Có thể có nhiều hơn hai đường ray cùng giao nhau tại một điểm.

Phân nhóm

Mỗi nhóm gồm đúng một tệp đầu vào công khai và có tối đa 20 điểm.

Chấm điểm

Nếu phương án không thỏa mãn các điều kiện của đề, nhóm đó nhận \(0\) điểm.

Nếu phương án hợp lệ, gọi \(C\) là số cặp đường ray cắt nhau. Điểm của nhóm có các tham số \(S,T\) được tính như sau:

Trong đó \(\lfloor x\rfloor\) là số nguyên lớn nhất không vượt quá \(x\).

Tổng điểm của bài là tổng điểm của năm nhóm, tối đa 100 điểm.

Ví dụ

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

1
5
4
2
7
3

Bàn pinball là một lưới gồm \(M+2\) hàng và \(N\) cột. Hàng thứ nhất là đỉnh bàn và hàng thứ \(M+2\) là đáy bàn. Ô tại hàng \(i\), cột \(j\) được ký hiệu là \((i,j)\).

Một quả bóng xuất hiện tại một ô bất kỳ trên hàng đầu tiên rồi rơi thẳng xuống. Nếu bóng xuất hiện tại \((1,i)\) và không gặp thiết bị nào, nó sẽ đi qua các ô \((2,i),\ldots,(M+1,i)\) rồi đến \((M+2,i)\).

Có \(M\) thiết bị, đánh số từ \(1\) đến \(M\). Thiết bị \(i\) nằm trên hàng \(i+1\), phủ các ô từ \((i+1,A_i)\) đến \((i+1,B_i)\). Khi bóng chạm một ô thuộc thiết bị này, bóng được chuyển đến ô \((i+1,C_i)\) rồi tiếp tục rơi dọc theo cột \(C_i\). Mỗi thiết bị tương tác với một quả bóng không quá một lần.

Đặt thiết bị \(i\) lên bàn tốn \(D_i\) yên. Alice muốn chọn một số thiết bị sao cho dù bóng xuất hiện ở ô nào trên hàng đầu tiên, nó chỉ có thể đến đúng một ô duy nhất ở hàng đáy. Hãy tìm tổng chi phí nhỏ nhất.

Dữ liệu vào

• Dòng đầu gồm \(M,N\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) gồm \(A_i,B_i,C_i,D_i\).

Dữ liệu ra

In tổng chi phí nhỏ nhất để chỉ còn một ô ở hàng đáy mà bóng có thể đến. Nếu không thể, in -1.

Ràng buộc

• \(1 \le M \le 100\,000\).
• \(2 \le N \le 1\,000\,000\,000\).
• \(1 \le A_i \le C_i \le B_i \le N\).
• \(1 \le D_i \le 1\,000\,000\,000\).

Phân nhóm

• Nhóm 1 (11 điểm): \(M \le 10\), \(N \le 1\,000\)
• Nhóm 2 (18 điểm): \(M \le 200\)
• Nhóm 3 (22 điểm): \(M \le 1\,000\)
• Nhóm 4 (49 điểm): Không có ràng buộc bổ sung

Ví dụ

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

25

3 5
2 4 3 10
1 3 1 20
2 5 4 30

-1

Anna nghĩ ra một phép toán hai ngôi bí mật \(\star\). Với mọi số nguyên không âm \(x,y\le 1\,000\,000\,000\), giá trị \(x\star y\) cũng là một số nguyên không âm không vượt quá \(1\,000\,000\,000\). Phép toán này có tính kết hợp:

Anna cho Bruno xem \(N\) số \(A_0,A_1,\ldots,A_{N-1}\), sau đó đặt nhiều truy vấn yêu cầu tính:

Bruno không biết phép toán \(\star\), nhưng có thể hỏi giá trị \(x\star y\) thông qua hàm Secret. Hãy cài đặt chiến lược trả lời đúng mọi truy vấn với số lần gọi Secret nhỏ nhất có thể.

Chi tiết cài đặt

Bài nộp phải khai báo:

#include "secret.h"

và cài đặt chính xác hai hàm:

void Init(int N, int A[]);
int Query(int L, int R);

Hàm Init được gọi đúng một lần lúc bắt đầu.

• N là số phần tử.
• A là mảng độ dài \(N\), chứa \(A_0,A_1,\ldots,A_{N-1}\).

Hàm Query được gọi cho mỗi truy vấn.

• \(0\le L\le R\le N-1\).
• Hàm phải trả về \(A_L\star A_{L+1}\star\cdots\star A_R\).

Bài nộp có thể gọi hàm do bộ chấm cung cấp:

int Secret(int X, int Y);

• X và Y phải nằm trong đoạn \([0,1\,000\,000\,000]\). Gọi hàm với tham số ngoài đoạn này sẽ bị chấm sai ngay lập tức.
• Hàm trả về \(X\star Y\).

Bài nộp không được cài đặt hàm main.

Bộ chấm mẫu

Trong bộ chấm mẫu, phép toán được định nghĩa là:

Phép toán của bộ chấm chính thức có thể khác.

Bộ chấm mẫu đọc:

• Dòng đầu chứa \(N\).
• Dòng thứ hai chứa \(A_0,A_1,\ldots,A_{N-1}\).
• Dòng thứ ba chứa số truy vấn \(Q\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa \(L_j,R_j\).

Bộ chấm mẫu in giá trị trả về của mỗi lời gọi Query, mỗi giá trị trên một dòng. Nó cũng báo số lần gọi Secret trong Init và số lần gọi lớn nhất trong một lời gọi Query.

Ràng buộc

• \(1 \le N \le 1\,000\).
• \(0 \le A_i \le 1\,000\,000\,000\).
• Số lần gọi Query không vượt quá \(10\,000\).

Chấm điểm

Điểm chỉ được trao nếu chương trình kết thúc bình thường, mọi lời gọi Secret đều hợp lệ và tất cả giá trị trả về bởi Query đều đúng.

• 100 điểm: trong mỗi bộ kiểm thử, Init gọi Secret không quá \(8\,000\) lần và mỗi lời gọi Query gọi Secret không quá một lần.
• 30 điểm: nếu không đạt điều kiện 100 điểm, nhưng Init gọi Secret không quá \(8\,000\) lần và mỗi lời gọi Query gọi Secret không quá \(20\) lần.
• 6 điểm: lời giải đúng nhưng không đạt hai mức trên.

Ví dụ

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

13
32
8
13