JOI 2016 Final Camp - Ngày 3

Bạn có biết công ty Just Ordinary Inventions không? Công việc của công ty này là tạo ra những “phát minh hết sức bình thường” (just ordinary inventions).

JOI đang chơi trò chơi mới nhất do công ty Just Ordinary Inventions phát triển.

Trong trò chơi này, người chơi khám phá một hầm ngục gồm một số căn phòng và các con đường. Mỗi con đường nối hai căn phòng khác nhau và có thể đi theo cả hai chiều. Giữa hai căn phòng khác nhau có nhiều nhất một con đường, và không có con đường nào có hai đầu là cùng một phòng. Có thể đi từ bất kỳ phòng nào đến bất kỳ phòng nào khác bằng một số con đường. Các phòng trông rất giống nhau: chỉ nhìn vào căn phòng thì hoàn toàn không thể phân biệt hai phòng có cùng số con đường đi ra.

Để hỗ trợ người chơi, mỗi phòng có một dấu mốc và một bệ đặt đá quý. Dựa vào dấu mốc, người chơi có thể đánh số các con đường đi ra từ phòng đó là \(1, 2, \ldots\). Cấu trúc hầm ngục không thay đổi trong suốt trò chơi, nên đi theo con đường có cùng số thứ tự từ cùng một phòng luôn dẫn đến cùng một phòng đích. Trên bệ có một viên đá quý mà người chơi có thể đổi màu. Màu của viên đá là một trong các màu \(1, 2, \ldots, X\). Khi trò chơi bắt đầu, đá quý trong mọi phòng đều có màu \(1\). Màu của chúng chỉ thay đổi khi người chơi chủ động đổi màu.

JOI nhận ra rằng nếu biết cấu trúc hầm ngục, tức là biết các phòng được nối với nhau như thế nào, thì sẽ dễ dàng chinh phục trò chơi. Tuy nhiên, dù thử nhiều cách, JOI vẫn không xác định được cấu trúc đó. Bạn quyết định viết một chương trình giúp JOI khám phá hầm ngục.

Yêu cầu

Hãy viết chương trình khám phá và xác định cấu trúc hầm ngục. Tuy nhiên, JOI không muốn được tiết lộ toàn bộ cấu trúc. Vì vậy, thay vì trả lời trực tiếp cấu trúc hầm ngục, với mỗi số nguyên \(i\) từ \(1\) đến \(R\), chương trình phải trả lời số cặp phòng có số con đường ít nhất cần đi qua để di chuyển giữa chúng bằng đúng \(i\). Hai cặp chỉ khác nhau ở thứ tự hai phòng được xem là cùng một cặp.

Thư viện được cung cấp cho phép thực hiện các thao tác sau:

• Biết số con đường đi ra từ phòng hiện tại.
• Biết màu viên đá quý trong phòng hiện tại.
• Đổi màu viên đá quý trong phòng hiện tại thành màu chỉ định, có thể là chính màu đang có; sau đó chọn một con đường đi ra từ phòng và di chuyển theo đường đó sang phòng khác.
• Biết con đường vừa đi qua mang số thứ tự nào trong các con đường đi ra từ phòng hiện tại.

Chi tiết cài đặt

Bạn phải viết một chương trình thực hiện việc trả lời cho JOI. Chương trình phải bao gồm tệp tiêu đề dungeon2.h:

#include "dungeon2.h"

Hàm cần cài đặt

void Inspect(int R);

Hàm này được gọi đúng một lần khi bắt đầu. Tham số R cho biết chương trình phải trả lời số cặp phòng có khoảng cách ngắn nhất bằng \(i\) với mỗi số nguyên \(i\) từ \(1\) đến \(R\). Thứ tự hai phòng trong một cặp không quan trọng.

Hàm trả lời

void Answer(int D, int A);

Lời gọi này trả lời rằng có \(A\) cặp phòng mà số con đường ít nhất cần đi qua để di chuyển giữa hai phòng bằng đúng \(D\).

Các lời gọi Answer phải thỏa mãn mọi điều kiện sau:

Nếu một lời gọi Answer bị đánh giá là sai, không có gì bảo đảm rằng chương trình sẽ tiếp tục được thực thi.

Các hàm dùng để khám phá

void Move(int I, int C);

Trước tiên, đổi viên đá quý trong phòng hiện tại, trước khi di chuyển sang màu C. Sau đó, người chơi đi theo con đường thứ I đi ra từ phòng này để đến phòng khác.

Các lời gọi Move phải thỏa mãn mọi điều kiện sau:

Trong tệp dungeon2.h được cung cấp, tham số màu được đặt tên là V, nên khai báo tương ứng là void Move(int I, int V);. Đây vẫn là cùng hàm Move với tham số thứ hai biểu thị màu cần đặt.

int NumberOfRoads();

Trả về số con đường đi ra từ phòng hiện tại.

int LastRoad();

Trả về số thứ tự của con đường vừa được dùng để di chuyển, theo cách đánh số tại phòng hiện tại. Nếu chưa từng gọi Move, hàm trả về \(-1\).

int Color();

Trả về màu viên đá quý trên bệ trong phòng hiện tại.

Sau khi lời gọi Inspect kết thúc, các câu trả lời sẽ được kiểm tra. Bạn được phép cài đặt các hàm phụ và khai báo biến toàn cục để sử dụng nội bộ. Tuy nhiên, chương trình nộp bài không được tương tác với đầu vào chuẩn, đầu ra chuẩn hoặc bất kỳ tệp nào khác bằng bất kỳ cách nào.

Cách nộp bài

Nộp một tệp mã nguồn C++ chứa hàm Inspect và include dungeon2.h được đính kèm theo bài. Không viết hàm main, không đọc đầu vào chuẩn và không ghi đầu ra chuẩn. Hệ thống chấm đặt người chơi ban đầu trong một phòng cố định, cung cấp các hàm Move, NumberOfRoads, LastRoad, Color, Answer, rồi gọi Inspect đúng một lần.

Ràng buộc

Các ký hiệu \(N, D_i, T_{ij}\) có ý nghĩa như trong phần dữ liệu vào của trình chấm mẫu. Mọi bộ dữ liệu thỏa mãn:

• \(2 \le N \le 200\).
• \(3 \le X \le 100\).
• \(1 \le R \le 200\).
• \(1 \le D_i \le N-1\) với mọi \(1 \le i \le N\).
• \(1 \le T_{ij} \le N\) và \(T_{ij} \ne i\) với mọi \(1 \le i \le N\), \(1 \le j \le D_i\).
• Với mỗi \(1 \le i \le N\), các giá trị \(T_{i1}, T_{i2}, \ldots, T_{iD_i}\) đôi một khác nhau.
• Với mỗi \(1 \le i \le N\) và \(1 \le j \le D_i\), tồn tại \(k\) thỏa mãn:

• Có thể đi từ bất kỳ phòng nào đến bất kỳ phòng nào khác bằng một số con đường.

Các bài toán con

Gọi \(N\) là số phòng và \(M\) là số con đường trong hầm ngục của bộ dữ liệu.

1. 17 điểm: \(N \le 50\), \(M \le 100\), \(X=100\).
2. 27 điểm: \(N \le 50\), \(M \le 100\), \(X=3\).
3. 56 điểm: \(X=3\).

Cách tính điểm bài toán con 3

Trong mỗi bộ kiểm thử, gọi \(C\) là số lần gọi Move. Gọi \(L\) là giá trị lớn nhất của tỉ số sau trên tất cả các bộ kiểm thử của bài toán con 3:

Điểm của bài toán con 3 được tính chính xác như sau:

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

Trên hệ thống chấm, nếu chương trình kết thúc đúng cách và câu trả lời được đánh giá là đúng, cột chi tiết hiển thị Accepted. Tuy nhiên, khi chấm bài toán con 3, đối với một bộ kiểm thử thỏa mãn điều kiện dưới đây, cột kết quả sẽ hiển thị sai, ngay cả khi cột chi tiết hiển thị Accepted:

Ví dụ giao tiếp

Dưới đây là một ví dụ dữ liệu vào của trình chấm mẫu và một chuỗi lời gọi hàm tương ứng.

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

Chuỗi lời gọi hàm

Lưu ý rằng các lời gọi trong ví dụ này không nhất thiết là những thao tác có ý nghĩa để giải bài toán.

Nhà hàng sushi băng chuyền JOI vận chuyển các đĩa sushi trên một băng chuyền hình vòng tròn quay ngược chiều kim đồng hồ. Hiện có \(N\) khách, được đánh số từ \(1\) đến \(N\), ngồi quanh băng chuyền theo thứ tự số tăng dần ngược chiều kim đồng hồ. Khách \(N\) ngồi cạnh khách \(1\).

Mỗi khách đang giữ đúng một chiếc đĩa. Mỗi đĩa có một giá trị gọi là giá tiền. Khi rời nhà hàng, mỗi khách phải trả số tiền bằng giá của chiếc đĩa mình đang giữ.

Nhà hàng JOI tổ chức một đợt khuyến mãi đặc biệt. Đầu bếp lần lượt đưa đĩa lên băng chuyền trong \(Q\) lượt. Lượt thứ \(i\) được mô tả bởi ba số nguyên \((S_i,T_i,P_i)\), với \(1 \le i \le Q\).

Ngay trước khi đợt khuyến mãi bắt đầu, đầu bếp thu hết các đĩa đang có trên băng chuyền. Sau đó, với \(i=1,2,\ldots,Q\), lần lượt thực hiện ba bước sau:

1. Đầu bếp đặt một đĩa có giá \(P_i\) lên băng chuyền tại vị trí trước mặt khách \(S_i\).
2. Đĩa di chuyển trên băng chuyền từ khách \(S_i\) đến khách \(T_i\). Mỗi khách trên đường đi, kể cả hai khách ở đầu và cuối, xem chiếc đĩa đi qua trước mặt mình. Nếu giá đĩa trên băng chuyền nhỏ hơn giá đĩa đang giữ, khách đổi đĩa của mình với đĩa trên băng chuyền. Nếu giá đĩa trên băng chuyền lớn hơn hoặc bằng giá đĩa đang giữ, khách không đổi đĩa.
3. Sau khi đĩa đi qua trước mặt khách \(T_i\), đầu bếp thu lại chiếc đĩa đó.

Bạn là người học việc của đầu bếp và được giao nhiệm vụ rửa đĩa. Cách rửa đĩa ở nhà hàng JOI phụ thuộc vào giá của đĩa. Để chuẩn bị, bạn muốn biết trước giá của chiếc đĩa mà đầu bếp thu lại trong từng lượt của \(Q\) lượt khuyến mãi.

Bổ sung sau khi kỳ thi kết thúc: Khi \(S_i=T_i\), chỉ khách \(S_i\) thực hiện thao tác ở bước 2.

Yêu cầu

Cho giá của đĩa mà mỗi khách đang giữ ngay trước đợt khuyến mãi và thông tin của các lượt đưa đĩa lên băng chuyền. Hãy tính giá của chiếc đĩa mà đầu bếp thu lại trong mỗi lượt.

Dữ liệu vào

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

• Dòng đầu chứa hai số nguyên \(N,Q\), cách nhau bởi dấu cách, lần lượt là số khách và số lượt đưa đĩa lên băng chuyền.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(X_i\), là giá của đĩa mà khách \(i\) giữ ngay trước đợt khuyến mãi, với \(1 \le i \le N\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(S_i,T_i,P_i\), cách nhau bởi dấu cách, mô tả lượt thứ \(i\), với \(1 \le i \le Q\).

Dữ liệu ra

Ghi ra đầu ra chuẩn \(Q\) dòng. Dòng thứ \(i\) chứa một số nguyên là giá của chiếc đĩa mà đầu bếp thu lại trong lượt thứ \(i\), với \(1 \le i \le Q\).

Ràng buộc

• \(1 \le N \le 400\,000\).
• \(1 \le Q \le 25\,000\).
• \(1 \le X_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\).
• \(1 \le S_i \le N\) với mọi \(1 \le i \le Q\).
• \(1 \le T_i \le N\) với mọi \(1 \le i \le Q\).
• \(1 \le P_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le Q\).

Các bài toán con

1. 5 điểm: \(N \le 2\,000\), \(Q \le 2\,000\).
2. 15 điểm: \(S_i=1\) và \(T_i=N\) với mọi \(1 \le i \le Q\).
3. 80 điểm: Không có ràng buộc bổ sung.

Ví dụ

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

7
9
8
7
8
6
5

4 2
5
2
4
7
1 4 3
1 4 1

7
5

10 10
19
5
8
17
14
3
9
10
7
6
1 8 4
7 3 2
5 9 10
4 8 3
10 3 6
8 7 4
6 6 3
2 9 12
6 3 7
9 6 3

19
10
14
17
8
10
3
12
7
9

Quần đảo JOI là một quốc đảo nhỏ trên Thái Bình Dương, gồm \(N\) hòn đảo được đánh số từ \(1\) đến \(N\).

Các đảo chủ yếu liên lạc với nhau bằng sóng vô tuyến. Mỗi đảo có một máy phát và một máy thu. Máy phát có thể phát sóng theo mọi hướng, nhưng máy thu chỉ nhận được sóng từ một hướng nhất định. Vì vậy, mỗi máy thu chỉ nhận được sóng từ đúng một đảo cụ thể. Có thể đổi hướng máy thu để thay đổi đảo mà nó nhận sóng.

Hiện tại, máy thu trên đảo \(i\) nhận được sóng từ đảo \(A_i\), với \(A_i \ne i\). Chi phí đổi hướng máy thu trên đảo \(i\) là \(C_i\), không phụ thuộc vào hướng mới, với \(1 \le i \le N\).

Quần đảo JOI cung cấp dịch vụ điện báo như một dịch vụ công. Nếu máy thu trên đảo \(j\) nhận được sóng từ đảo \(i\), với \(1 \le i,j \le N\) và \(i \ne j\), thì có thể gửi điện báo từ đảo \(i\) đến đảo \(j\) qua liên lạc vô tuyến. Điện báo cũng có thể được chuyển tiếp qua một số đảo. Cụ thể, với ba đảo phân biệt \(i,j,k\), nếu có thể gửi điện báo từ \(i\) đến \(j\) và từ \(j\) đến \(k\), thì có thể gửi điện báo từ \(i\) đến \(k\). Không thể gửi điện báo bằng phương thức nào khác ngoài liên lạc vô tuyến.

Là bộ trưởng phụ trách thông tin liên lạc của quần đảo JOI, bạn muốn có thể gửi điện báo từ bất kỳ đảo nào đến bất kỳ đảo nào khác. Để đạt được điều này, có thể cần đổi hướng máy thu trên một số đảo. Tổng chi phí là tổng chi phí đổi hướng của từng máy thu được thay đổi.

Yêu cầu

Cho số đảo và thông tin về máy thu trên từng đảo. Hãy tính chi phí nhỏ nhất để có thể gửi điện báo từ bất kỳ đảo nào đến bất kỳ đảo nào khác.

Dữ liệu vào

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

• Dòng đầu chứa số nguyên \(N\), là số đảo của quần đảo JOI.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(A_i,C_i\), cách nhau bởi dấu cách. Máy thu trên đảo \(i\) hiện nhận sóng từ đảo \(A_i\), và chi phí đổi hướng máy thu này là \(C_i\), với \(1 \le i \le N\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa chi phí nhỏ nhất để có thể gửi điện báo từ bất kỳ đảo nào đến bất kỳ đảo nào khác.

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(1 \le A_i \le N\) với mọi \(1 \le i \le N\).
• \(A_i \ne i\) với mọi \(1 \le i \le N\).
• \(1 \le C_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\).

Các bài toán con

1. 10 điểm: \(N \le 10\).
2. 30 điểm: \(N \le 15\).
3. 30 điểm: \(N \le 3\,000\).
4. 30 điểm: Không có ràng buộc bổ sung.

Ví dụ

4
2 2
1 4
1 3
3 1

4

4
2 2
1 6
1 3
3 1

5

    Không có cách đổi hướng các máy thu nào đạt yêu cầu với chi phí nhỏ hơn $5$, nên kết quả là $5$.

4
2 2
1 3
4 2
3 3

4

3
2 1
3 1
1 1

0