Có \(N\) điểm tham quan trong công viên chủ đề lớn nhất ở Jakarta, được đánh số từ \(0\) đến \(N-1\). Các điểm tham quan này được nối với nhau bằng \(N-1\) con đường hai chiều sao cho giữa hai điểm tham quan bất kỳ có duy nhất một cách đi thông qua các con đường này. Các con đường được đánh số từ \(0\) đến \(N-2\). Con đường thứ \(i\) nối điểm tham quan \(A[i]\) và điểm tham quan \(B[i]\), và mất \(1\) giờ để đi bộ. Để tránh tắc đường, mỗi điểm tham quan là đầu mút của nhiều nhất \(3\) con đường.

Bạn muốn tạo một chuyến đi thăm tất cả các điểm tham quan, mỗi điểm đúng một lần. Việc phải đi qua nhiều con đường để di chuyển từ điểm tham quan này đến một điểm tham quan khác thì buồn chán. Vì vậy, bạn muốn tạo một chuyến tham quan vui vẻ bằng cách xếp thứ tự các điểm tham quan sao cho thời gian cần để di chuyển đến điểm tham quan tiếp theo không lớn hơn thời gian cần để di chuyển đến điểm tham quan trước đó. Nói cách khác, bạn muốn tìm một dãy \(P[0],P[1],\ldots,P[N-1]\) chứa tất cả các số nguyên từ \(0\) đến \(N-1\), mỗi số đúng một lần, sao cho thời gian cần để di chuyển từ điểm tham quan \(P[i]\) tới điểm tham quan \(P[i+1]\) không lớn hơn thời gian cần để di chuyển từ điểm tham quan \(P[i-1]\) tới điểm tham quan \(P[i]\), với mọi \(0<i<N-1\).

Bạn không có bản đồ đầy đủ của các điểm tham quan. Vì vậy, bạn phải hỏi trung tâm thông tin một số câu hỏi để có thể tạo được chuyến tham quan vui vẻ. Bạn có thể hỏi tối đa \(Q\) câu hỏi, mỗi câu hỏi có hai tham số \(X\) và \(Y\), trong đó \(0 \le X,Y < N\). Mỗi câu hỏi thuộc một trong hai dạng sau:

• Cần bao nhiêu giờ để đi từ điểm tham quan \(X\) đến điểm tham quan \(Y\)? Đặc biệt, nếu \(X=Y\) thì câu trả lời là \(0\).
• Có bao nhiêu điểm tham quan \(Z\) mà đường đi từ điểm tham quan \(X\) đến điểm tham quan \(Z\) phải đi qua điểm tham quan \(Y\)? Điểm tham quan \(Y\) cũng được tính. Đặc biệt, nếu \(X=Y\) thì câu trả lời là \(N\).

Chi tiết cài đặt

Bạn phải cài đặt hàm createFunTour. Hàm này được phép gọi hai hàm hoursRequired và attractionsBehind của trình chấm. Các chữ ký C++ chính xác là:

int hoursRequired(int X, int Y);

int attractionsBehind(int X, int Y);

std::vector<int> createFunTour(int N, int Q);

Hàm thí sinh cài đặt: createFunTour

Hàm createFunTour được trình chấm gọi đúng một lần.

• N: số điểm tham quan.
• Q: số lượng tối đa các câu hỏi.
• Hàm phải trả về một mảng gồm đúng \(N\) số nguyên, biểu diễn một hoán vị của các điểm tham quan trong chuyến đi vui vẻ.
• Tổng số lần gọi hoursRequired và attractionsBehind không được vượt quá \(Q\).

Hàm của trình chấm: hoursRequired

• X: điểm tham quan thứ nhất.
• Y: điểm tham quan thứ hai.
• Hàm trả về một số nguyên biểu diễn số giờ cần để đi từ điểm tham quan \(X\) đến điểm tham quan \(Y\).
• Đặc biệt, nếu \(X=Y\) thì hàm trả về \(0\).
• Nếu một trong hai giá trị \(X\) hoặc \(Y\) không nằm trong khoảng từ \(0\) đến \(N-1\), bài làm nhận kết quả WA.

Hàm của trình chấm: attractionsBehind

• X: điểm tham quan thứ nhất.
• Y: điểm tham quan thứ hai.
• Hàm trả về một số nguyên biểu diễn số lượng điểm tham quan \(Z\) mà đường đi từ điểm tham quan \(X\) đến điểm tham quan \(Z\) phải đi qua điểm tham quan \(Y\); điểm tham quan \(Y\) cũng được tính.
• Đặc biệt, nếu \(X=Y\) thì hàm trả về \(N\).
• Nếu một trong hai giá trị \(X\) hoặc \(Y\) không nằm trong khoảng từ \(0\) đến \(N-1\), bài làm nhận kết quả WA.

Ví dụ

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

3 6 4 5 2 0 1

Trong ví dụ này, \(N=7\), \(Q=400\,000\), \(A=[0,0,0,1,1,2]\) và \(B=[1,5,6,2,4,3]\). Ví dụ được minh họa bằng hình dưới đây:

{{asset:apio20fun/example.png}}

Trình chấm gọi createFunTour(7, 400000).

• Nếu thí sinh gọi hoursRequired(3, 5), hàm trả về \(4\).
• Nếu thí sinh gọi hoursRequired(5, 4), hàm trả về \(3\).
• Nếu thí sinh gọi attractionsBehind(5, 1), hàm trả về \(4\). Đường đi từ điểm tham quan \(5\) đến mỗi điểm tham quan \(1\), \(2\), \(3\), \(4\) đều phải đi qua điểm tham quan \(1\).
• Nếu thí sinh gọi attractionsBehind(1, 5), hàm trả về \(1\).
• Thí sinh có thể trả về \([3,6,4,5,2,0,1]\) vì số giờ cần thiết để đi đến điểm tham quan tiếp theo theo thứ tự trên là \([4,3,3,3,2,1]\).

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(Q=400\,000\).
• Có thể di chuyển giữa bất kỳ cặp điểm tham quan nào thông qua các con đường trên.
• Mỗi điểm tham quan là đầu mút của không quá \(3\) con đường.

Phân nhóm

1. Đường đi từ điểm tham quan \(T\) đến điểm tham quan \(j\) phải đi qua điểm tham quan \(i\) khi và chỉ khi \(L[i] \le j \le R[i]\).
2. Nếu \(L[i]<i\), có đúng một điểm tham quan \(X\) sao cho \(L[i] \le X<i\) và có một con đường nối \(i\) với \(X\).
3. Nếu \(i<R[i]\), có đúng một điểm tham quan \(Y\) sao cho \(i<Y \le R[i]\) và có một con đường nối \(i\) với \(Y\). |
   | 5 | 34 | Không có ràng buộc gì thêm. |

Trình chấm mẫu

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

N Q
A[0] B[0]
A[1] B[1]
.
.
.
A[N-2] B[N-2]

Trình chấm mẫu ghi các số nguyên trả về từ hàm createFunTour nếu hàm trả về đúng một mảng gồm \(N\) số nguyên biểu diễn một hoán vị của các điểm tham quan trong chuyến đi vui vẻ và tổng số lần gọi cả hai hàm hoursRequired và attractionsBehind không quá \(Q\). Ngược lại, trình chấm mẫu in ra một thông báo câu trả lời sai.

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2020: Fun Tour.