IOI 2018 - Ngày 2

Búp bê cơ khí là một con búp bê tự động lặp đi lặp lại một dãy các cử động nhất định. Ở Nhật Bản, có nhiều loại búp bê cơ khí được tạo từ thời xưa.

Các cử động của búp bê cơ khí được điều khiển bởi một mạch bao gồm nhiều thiết bị. Các thiết bị được nối với nhau bởi các đường ống. Mỗi thiết bị có một hoặc hai đầu ra, và có thể có một số lượng tùy ý (có thể là không) đầu vào. Mỗi đường ống nối một đầu ra của một thiết bị với một đầu vào của chính thiết bị đó hoặc của một thiết bị khác. Chính xác một đường ống được nối với mỗi đầu vào, và chính xác một đường ống được nối với mỗi đầu ra.

Để mô tả cách một con búp bê thực hiện các cử động, xét một quả bóng được đặt tại một trong các thiết bị. Quả bóng di chuyển trong mạch. Tại mỗi bước, quả bóng rời thiết bị qua một trong các đầu ra của thiết bị, di chuyển theo đường ống nối đến đầu ra và đi vào thiết bị tại đầu kia của đường ống.

Có ba kiểu thiết bị: nguồn (origin), kích hoạt (trigger) và chuyển đổi (switch). Có đúng một thiết bị nguồn, \(M\) thiết bị kích hoạt và \(S\) thiết bị chuyển đổi (\(S\) có thể bằng không). Bạn phải xác định giá trị của \(S\). Mỗi thiết bị có một số hiệu duy nhất.

Thiết bị nguồn là thiết bị nơi đầu tiên quả bóng được đặt vào. Thiết bị nguồn có một đầu ra. Số hiệu của nó là \(0\).

Một thiết bị kích hoạt sẽ điều khiển búp bê thực hiện một cử động cụ thể khi quả bóng đi vào nó. Mỗi thiết bị kích hoạt có một đầu ra. Số hiệu của các thiết bị kích hoạt là từ \(1\) đến \(M\).

Mỗi thiết bị chuyển đổi có hai đầu ra được gọi là X và Y. Trạng thái của một thiết bị chuyển đổi hoặc là X hoặc là Y. Sau khi quả bóng đi vào một thiết bị chuyển đổi, nó rời thiết bị bằng đầu ra được xác định bởi trạng thái hiện tại của thiết bị. Sau đó, thiết bị chuyển đổi chuyển trạng thái của nó sang trạng thái đối lại. Ban đầu, trạng thái của tất cả các thiết bị chuyển đổi là X. Số hiệu của các thiết bị chuyển đổi là từ \(-1\) đến \(-S\).

Bạn được cho số lượng thiết bị kích hoạt \(M\). Bạn cũng được cho một dãy \(A\) có độ dài \(N\), mỗi phần tử là số hiệu của một thiết bị kích hoạt. Mỗi thiết bị kích hoạt có thể xuất hiện một vài (có thể không) lần trong dãy \(A\). Nhiệm vụ của bạn là tạo ra một mạch thỏa mãn các điều kiện sau:

• Quả bóng quay lại thiết bị nguồn sau một số bước nào đó.
• Khi quả bóng quay lại thiết bị nguồn lần đầu tiên, trạng thái của mỗi thiết bị chuyển đổi là X.
• Quả bóng quay lại thiết bị nguồn lần đầu tiên sau khi đi vào các thiết bị kích hoạt đúng \(N\) lần. Số hiệu của các thiết bị kích hoạt, theo thứ tự mà quả bóng đi vào, là \(A_0, A_1, \ldots, A_{N-1}\).
• Gọi \(P\) là tổng số lần thay đổi trạng thái của tất cả các thiết bị chuyển đổi do quả bóng gây ra trước khi nó quay lại thiết bị nguồn lần đầu tiên. Giá trị của \(P\) không được vượt quá \(20\,000\,000\).

Đồng thời, bạn không muốn sử dụng quá nhiều thiết bị chuyển đổi.

Chi tiết cài đặt

Bạn phải cài đặt thủ tục sau, với chữ ký C++ trong tệp doll.h của gói đính kèm:

void create_circuit(int M, std::vector<int> A);

• M: số lượng thiết bị kích hoạt.
• A: mảng độ dài \(N\), cho biết số hiệu của các thiết bị kích hoạt theo thứ tự mà quả bóng cần đi vào.
• Thủ tục này được gọi đúng một lần.
• Lưu ý, giá trị \(N\) là độ dài của mảng A, và có thể lấy được theo cách mô tả trong Lưu ý cài đặt.

Chương trình của bạn phải gọi thủ tục sau để trả lời:

void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);

• C: mảng độ dài \(M+1\). Đầu ra của thiết bị \(i\) (\(0 \le i \le M\)) được nối với thiết bị C[i].
• X, Y: các mảng cùng độ dài. Độ dài \(S\) của các mảng này là số lượng thiết bị chuyển đổi. Với thiết bị chuyển đổi \(-j\) (\(1 \le j \le S\)), đầu ra X được nối với thiết bị X[j - 1] và đầu ra Y được nối với thiết bị Y[j - 1].
• Mọi phần tử của C, X và Y phải là số nguyên nằm giữa \(-S\) và \(M\), bao gồm cả hai đầu mút.
• \(S\) nhiều nhất là \(400\,000\).
• Thủ tục này phải được gọi đúng một lần.
• Mạch được biểu diễn bởi C, X và Y phải thỏa mãn các điều kiện trong phát biểu bài toán.

Nếu một trong các điều kiện nêu trên không được thỏa mãn, chương trình của bạn được chấm là Wrong Answer. Ngược lại, chương trình được chấm là Accepted và điểm của bạn được tính theo \(S\) (xem phần Subtasks).

Ví dụ

Cho \(M=4\), \(N=4\) và \(A=[1,2,1,3]\). Trình chấm gọi create_circuit(4, [1, 2, 1, 3]).

Hình trên biểu diễn một mạch được mô tả bằng lời gọi answer([1, -1, -2, 0, 2], [2, -2], [3, 1]). Các con số trong hình là số hiệu của các thiết bị.

Có hai thiết bị chuyển đổi được sử dụng. Do đó, \(S=2\). Ban đầu, trạng thái của cả hai thiết bị chuyển đổi \(-1\) và \(-2\) là X.

Quả bóng di chuyển như sau:

• Khi quả bóng lần đầu tiên đi vào thiết bị chuyển đổi \(-1\), trạng thái của nó là X. Do đó, quả bóng di chuyển tới thiết bị kích hoạt \(2\). Tiếp theo, trạng thái của thiết bị chuyển đổi \(-1\) được chuyển thành Y.
• Khi quả bóng đi vào thiết bị chuyển đổi \(-1\) lần thứ hai, trạng thái của nó là Y. Do đó, quả bóng di chuyển tới thiết bị kích hoạt \(3\). Tiếp theo, trạng thái của thiết bị chuyển đổi \(-1\) được chuyển thành X.

Khi quả bóng quay lại thiết bị nguồn lần đầu tiên, nó đã đi vào các thiết bị kích hoạt \(1,2,1,3\). Trạng thái của cả hai thiết bị chuyển đổi \(-1\) và \(-2\) là X. Giá trị của \(P\) là \(4\). Vì vậy, mạch thỏa mãn các điều kiện.

Tệp sample-01-in.txt trong gói nén đính kèm tương ứng với ví dụ này. Dữ liệu đầu vào của các ví dụ khác cũng có trong gói đính kèm.

Hạn chế

• \(1 \le M \le 100\,000\).
• \(1 \le N \le 200\,000\).
• \(1 \le A_k \le M\) (\(0 \le k \le N-1\)).

Phân nhóm

Điểm và các hạn chế cho mỗi bộ dữ liệu như sau:

Với mỗi bộ dữ liệu, nếu chương trình của bạn được chấm là Accepted, điểm của bạn được tính dựa vào giá trị \(S\):

• Nếu \(S \le N+\log_2 N\), bạn đạt toàn bộ số điểm của bộ dữ liệu.
• Với mỗi bộ dữ liệu trong subtasks \(5\) và \(6\), nếu \(N+\log_2 N < S \le 2N\), bạn đạt một phần điểm. Điểm của bộ dữ liệu bằng hệ số dưới đây nhân với số điểm được cho của subtask:

• Trong các trường hợp còn lại, điểm là \(0\).

Điểm của bạn cho mỗi subtask là điểm nhỏ nhất của các bộ dữ liệu trong subtask đó.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu từ thiết bị vào chuẩn theo khuôn mẫu sau:

• Dòng \(1\): \(M\ N\).
• Dòng \(2\): \(A_0\ A_1\ \ldots\ A_{N-1}\).

Trình chấm mẫu xuất ba dữ liệu ra.

Đầu tiên, trình chấm mẫu đưa câu trả lời của bạn ra tệp out.txt theo khuôn mẫu sau:

• Dòng \(1\): \(S\).
• Dòng \(2+i\) (\(0 \le i \le M\)): C[i].
• Dòng \(2+M+j\) (\(1 \le j \le S\)): X[j - 1] Y[j - 1].

Thứ hai, trình chấm mẫu mô phỏng các bước di chuyển của quả bóng. Nó đưa số hiệu của các thiết bị quả bóng đi vào, theo thứ tự, ra tệp log.txt.

Thứ ba, trình chấm mẫu in đánh giá kết quả của bạn ra thiết bị ra chuẩn. Nếu chương trình của bạn được chấm là Accepted, trình chấm mẫu in \(S\) và \(P\) theo khuôn mẫu Accepted: S P. Nếu chương trình được chấm là Wrong Answer, nó in Wrong Answer: MSG, trong đó ý nghĩa của MSG như sau:

Lưu ý, trình chấm mẫu có thể không tạo ra out.txt và/hoặc log.txt khi chương trình của bạn được chấm là Wrong Answer.

Dữ liệu vào của ví dụ trên:

4 4
1 2 1 3

Với mạch được mô tả trong ví dụ, dòng đánh giá trên thiết bị ra chuẩn là:

Accepted: 2 4

Ở Nhật Bản, các thành phố được kết nối bằng mạng lưới các con đường cao tốc. Mạng lưới này gồm \(N\) thành phố và \(M\) con đường cao tốc. Mỗi con đường cao tốc nối một cặp hai thành phố khác nhau. Không có hai con đường cao tốc nối cùng một cặp hai thành phố. Các thành phố được đánh số từ \(0\) đến \(N-1\), và các con đường cao tốc được đánh số từ \(0\) đến \(M-1\). Bạn có thể lái xe trên mỗi con đường cao tốc theo cả hai chiều. Bạn có thể đi từ một thành phố bất kỳ sang một thành phố bất kỳ khác qua những con đường cao tốc.

Phải mua vé khi lái xe trên mỗi con đường cao tốc. Giá vé cho mỗi con đường cao tốc phụ thuộc vào độ tắc nghẽn của con đường. Độ tắc nghẽn có thể là thưa hoặc dày. Khi độ tắc nghẽn là thưa, giá vé là \(A\) yen (đơn vị tiền tệ Nhật Bản). Khi độ tắc nghẽn là dày, giá vé là \(B\) yen. Đảm bảo rằng \(A<B\). Chú ý là bạn biết giá trị của \(A\) và \(B\).

Bạn có một cỗ máy, khi được cho độ tắc nghẽn của tất cả các con đường cao tốc, nó tính ra tổng giá vé nhỏ nhất phải trả khi di chuyển giữa cặp hai thành phố \(S\) và \(T\) (\(S \ne T\)), trong trạng thái giao thông đó.

Tuy nhiên, cỗ máy này mới chỉ ở dạng thử nghiệm. Giá trị \(S\) và \(T\) cố định (tức là được cài đặt cố định vào cỗ máy) và bạn không biết các giá trị này. Bạn phải xác định giá trị của \(S\) và \(T\). Để thực hiện điều này, bạn lên kế hoạch nhập vào cỗ máy một số bộ giá trị độ tắc nghẽn, và sử dụng tổng giá vé mà cỗ máy tính ra để xác định \(S\) và \(T\). Vì việc nhập vào các độ tắc nghẽn là tốn kém, bạn không muốn sử dụng cỗ máy nhiều lần.

Chi tiết cài đặt

Bạn phải cài đặt thủ tục sau, với chữ ký C++ trong tệp highway.h của gói đính kèm:

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B);

• N: số lượng các thành phố.
• U và V: các mảng độ dài \(M\), với \(M\) là số lượng các con đường cao tốc nối giữa các thành phố. Với mỗi \(i\) (\(0 \le i \le M-1\)), con đường cao tốc thứ \(i\) nối hai thành phố U[i] và V[i].
• A: giá vé trên con đường cao tốc với độ tắc nghẽn là thưa.
• B: giá vé trên con đường cao tốc với độ tắc nghẽn là dày.
• Thủ tục này được gọi đúng một lần cho mỗi bộ dữ liệu.
• Chú ý rằng \(M\) là độ dài của các mảng; cách lấy độ dài mảng được mô tả trong Lưu ý cài đặt.

Thủ tục find_pair có thể gọi hàm sau:

long long ask(const std::vector<int> &w);

• Độ dài của w phải đúng bằng \(M\). Mảng w mô tả độ tắc nghẽn.
• Với mỗi \(i\) (\(0 \le i \le M-1\)), w[i] mô tả độ tắc nghẽn trên con đường cao tốc thứ \(i\). Giá trị của w[i] phải là \(0\) hoặc \(1\): w[i] = 0 nghĩa là độ tắc nghẽn trên con đường đó là thưa; w[i] = 1 nghĩa là độ tắc nghẽn trên con đường đó là dày.
• Hàm này trả lại tổng giá vé nhỏ nhất khi di chuyển giữa hai thành phố \(S\) và \(T\), với trạng thái giao thông được xác định bởi w. Giá trị trả về là số nguyên \(64\) bit.
• Hàm này được gọi tối đa \(100\) lần cho mỗi bộ dữ liệu.

find_pair phải gọi thủ tục sau để báo cáo kết quả:

void answer(int s, int t);

• s và t phải là cặp \(S\) và \(T\) (thứ tự không quan trọng).
• Thủ tục này phải được gọi đúng một lần.

Nếu một trong những điều kiện trên không thỏa mãn, chương trình của bạn được chấm là Wrong Answer. Ngược lại, chương trình được chấm là Accepted và điểm số của bạn được tính dựa trên số lần gọi ask (xem phần Subtasks).

Ví dụ

Giả sử \(N=4\), \(M=4\), \(U=[0,0,0,1]\), \(V=[1,2,3,2]\), \(A=1\), \(B=3\), \(S=1\) và \(T=3\).

Trình chấm gọi find_pair(4, [0, 0, 0, 1], [1, 2, 3, 2], 1, 3).

Trong hình trên, cạnh có số thứ tự \(i\) tương ứng với con đường cao tốc thứ \(i\). Một số lời gọi ask có thể và giá trị trả về tương ứng được liệt kê dưới đây:

Với lời gọi ask([0, 0, 0, 0]), độ tắc nghẽn của tất cả các con đường cao tốc là thưa và giá vé cho mỗi con đường là \(1\). Tuyến đường có chi phí thấp nhất từ \(S=1\) tới \(T=3\) là \(1 \to 0 \to 3\). Tổng giá vé trên tuyến đường này là \(2\). Do đó, hàm này trả về giá trị \(2\).

Để đưa ra câu trả lời đúng, thủ tục find_pair phải gọi answer(1, 3) hoặc answer(3, 1).

Tệp sample-01-in.txt trong gói nén zip đính kèm tương ứng với ví dụ này. Gói đính kèm cũng chứa dữ liệu đầu vào của các ví dụ khác.

Hạn chế

• \(2 \le N \le 90\,000\).
• \(1 \le M \le 130\,000\).
• \(1 \le A < B \le 1\,000\,000\,000\).
• Với mỗi \(i\) (\(0 \le i \le M-1\)): \(0 \le U[i] \le N-1\), \(0 \le V[i] \le N-1\) và \(U[i] \ne V[i]\).
• \((U[i],V[i]) \ne (U[j],V[j])\) và \((U[i],V[i]) \ne (V[j],U[j])\) (\(0 \le i < j \le M-1\)).
• Bạn có thể đi từ một thành phố bất kỳ đến bất kỳ thành phố nào còn lại bằng các con đường cao tốc.
• \(0 \le S \le N-1\).
• \(0 \le T \le N-1\).
• \(S \ne T\).

Trong bài này, trình chấm không có tính thích nghi. Điều này có nghĩa là \(S\) và \(T\) được cố định ngay từ đầu khi trình chấm chạy và không phụ thuộc vào các truy vấn do chương trình của bạn đưa ra.

Phân nhóm

Giả sử chương trình của bạn được chấm là Accepted và gọi ask \(X\) lần. Tùy theo subtask, điểm số \(P\) của bạn cho bộ dữ liệu được tính như sau:

Điểm của bạn cho mỗi subtask là điểm nhỏ nhất của các bộ dữ liệu trong subtask đó.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu đầu vào theo khuôn dạng sau:

• Dòng \(1\): \(N\ M\ A\ B\ S\ T\).
• Dòng \(2+i\) (\(0 \le i \le M-1\)): \(U[i]\ V[i]\).

Nếu chương trình của bạn được chấm là Accepted, trình chấm mẫu in Accepted: q, với q là số lần gọi ask.

Nếu chương trình của bạn được chấm là Wrong Answer, trình chấm mẫu in Wrong Answer: MSG, trong đó MSG có thể là:

Dữ liệu vào của ví dụ trên:

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

Nếu chương trình thực hiện đúng bốn lời gọi ask trong bảng rồi gọi answer(1, 3), trình chấm mẫu in:

Accepted: 4

Dọc theo một đường thẳng nằm ngang có \(N\) ngọn núi được đánh số từ \(0\) đến \(N-1\), từ trái qua phải. Chiều cao của ngọn núi \(i\) là \(H_i\) (\(0 \le i \le N-1\)). Có đúng một người sống trên đỉnh của mỗi ngọn núi.

Bạn cần tổ chức \(Q\) cuộc họp được đánh số từ \(0\) đến \(Q-1\). Tham gia cuộc họp \(j\) (\(0 \le j \le Q-1\)) sẽ là tất cả những người sống trên đỉnh các ngọn núi từ \(L_j\) đến \(R_j\), kể cả hai đầu mút (\(0 \le L_j \le R_j \le N-1\)). Đối với cuộc họp này, bạn cần chọn ngọn núi \(x\) làm nơi diễn ra cuộc họp (\(L_j \le x \le R_j\)). Chi phí của cuộc họp phụ thuộc vào lựa chọn của bạn và được tính như sau:

• Chi phí của thành viên đến từ ngọn núi \(y\) (\(L_j \le y \le R_j\)) là độ cao lớn nhất của các ngọn núi trong khoảng giữa hai ngọn núi \(x\) và \(y\), kể cả hai đầu mút. Đặc biệt, chi phí của thành viên đến từ ngọn núi \(x\) là \(H_x\), tức chiều cao của ngọn núi \(x\).
• Chi phí của cuộc họp là tổng các chi phí của tất cả các thành viên.

Đối với mỗi cuộc họp, bạn phải tìm chi phí nhỏ nhất có thể để tổ chức nó.

Chú ý là tất cả các thành viên sẽ quay lại ngọn núi của mình sau mỗi cuộc họp, do đó chi phí của một cuộc họp không bị ảnh hưởng bởi các cuộc họp trước đó.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau, với chữ ký C++ trong tệp meetings.h của gói đính kèm:

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R);

• H: mảng độ dài \(N\), biểu diễn chiều cao của các ngọn núi.
• L và R: các mảng độ dài \(Q\), biểu diễn các khoảng ngọn núi có người tham gia các cuộc họp.
• Hàm này cần trả lại mảng \(C\) độ dài \(Q\), gồm các số nguyên \(64\) bit. Giá trị của \(C_j\) (\(0 \le j \le Q-1\)) phải là chi phí nhỏ nhất có thể để tổ chức cuộc họp \(j\).
• Chú ý là các giá trị \(N\) và \(Q\) là độ dài của các mảng, và có thể lấy được theo cách mô tả trong Lưu ý cài đặt.

Ví dụ

Giả sử \(N=4\), \(H=[2,4,3,5]\), \(Q=2\), \(L=[0,1]\) và \(R=[2,3]\).

Trình chấm gọi minimum_costs([2, 4, 3, 5], [0, 1], [2, 3]).

Cuộc họp \(j=0\) có \(L_j=0\) và \(R_j=2\), vì thế những người sống ở các ngọn núi \(0\), \(1\) và \(2\) sẽ tham gia. Nếu ngọn núi \(0\) được chọn làm nơi tổ chức cuộc họp thì chi phí của cuộc họp \(0\) được tính như sau:

• Chi phí của thành viên đến từ ngọn núi \(0\) là \(\max\{H_0\}=2\).
• Chi phí của thành viên đến từ ngọn núi \(1\) là \(\max\{H_0,H_1\}=4\).
• Chi phí của thành viên đến từ ngọn núi \(2\) là \(\max\{H_0,H_1,H_2\}=4\).
• Vì vậy, chi phí của cuộc họp \(0\) là \(2+4+4=10\).

Không thể tổ chức cuộc họp \(0\) với chi phí nhỏ hơn, do đó chi phí nhỏ nhất để tổ chức cuộc họp \(0\) là \(10\).

Cuộc họp \(j=1\) có \(L_j=1\) và \(R_j=3\), vì thế những người sống ở các ngọn núi \(1\), \(2\) và \(3\) sẽ tham gia. Nếu ngọn núi \(2\) được chọn làm nơi tổ chức cuộc họp thì chi phí của cuộc họp \(1\) được tính như sau:

• Chi phí của thành viên đến từ ngọn núi \(1\) là \(\max\{H_1,H_2\}=4\).
• Chi phí của thành viên đến từ ngọn núi \(2\) là \(\max\{H_2\}=3\).
• Chi phí của thành viên đến từ ngọn núi \(3\) là \(\max\{H_2,H_3\}=5\).
• Vì vậy, chi phí của cuộc họp \(1\) là \(4+3+5=12\).

Không thể tổ chức cuộc họp \(1\) với chi phí nhỏ hơn, do đó chi phí nhỏ nhất để tổ chức cuộc họp \(1\) là \(12\).

Các tệp sample-01-in.txt và sample-01-out.txt trong gói nén zip đính kèm tương ứng với ví dụ này. Các ví dụ về dữ liệu vào/ra khác cũng có trong gói đính kèm.

Hạn chế

• \(1 \le N \le 750\,000\).
• \(1 \le Q \le 750\,000\).
• \(1 \le H_i \le 1\,000\,000\,000\) (\(0 \le i \le N-1\)).
• \(0 \le L_j \le R_j \le N-1\) (\(0 \le j \le Q-1\)).
• \((L_j,R_j) \ne (L_k,R_k)\) (\(0 \le j < k \le Q-1\)).

Phân nhóm

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo khuôn dạng sau:

• Dòng \(1\): \(N\ Q\).
• Dòng \(2\): \(H_0\ H_1\ \ldots\ H_{N-1}\).
• Dòng \(3+j\) (\(0 \le j \le Q-1\)): \(L_j\ R_j\).

Trình chấm mẫu in giá trị trả lại bởi minimum_costs theo khuôn dạng sau:

• Dòng \(1+j\) (\(0 \le j \le Q-1\)): \(C_j\).

Dữ liệu vào của ví dụ trên:

4 2
2 4 3 5
0 2
1 3

Dữ liệu ra tương ứng:

10
12