Các nhà tổ chức IOI 2023 đang gặp khó khăn lớn! Họ đã quên lên kế hoạch chuyến đi đến Ópusztaszer cho ngày mai. Nhưng có lẽ chưa quá muộn...

Ở Ópusztaszer có \(N\) điểm du lịch được đánh số từ \(0\) đến \(N-1\). Một số cặp điểm này được nối bởi các con đường hai chiều. Mỗi cặp điểm du lịch được nối bởi tối đa một con đường. Các nhà tổ chức không biết những điểm nào được nối bởi các con đường.

Chúng ta nói rằng mật độ của mạng lưới đường đi ở Ópusztaszer tối thiểu là \(\delta\) nếu mỗi bộ \(3\) điểm du lịch khác nhau có ít nhất \(\delta\) con đường giữa chúng. Nói cách khác, đối với mỗi bộ ba điểm \((u,v,w)\) sao cho \(0 \le u < v < w < N\), trong số các cặp điểm \((u,v)\), \((v,w)\) và \((u,w)\) có ít nhất \(\delta\) cặp được nối bởi một con đường.

Các nhà tổ chức biết một số nguyên dương \(D\) sao cho mật độ của mạng lưới đường đi tối thiểu là \(D\). Lưu ý rằng giá trị của \(D\) không thể lớn hơn \(3\).

Các nhà tổ chức có thể gọi điện tới bộ phận điều phối ở Ópusztaszer để thu thập thông tin về các kết nối đường đi giữa một số điểm du lịch. Trong mỗi cuộc gọi, họ cần xác định hai mảng không rỗng của các điểm du lịch \([A[0],\ldots,A[P-1]]\) và \([B[0],\ldots,B[R-1]]\). Các điểm du lịch phải đôi một khác nhau, nghĩa là:

• \(A[i] \ne A[j]\) với mọi \(i,j\) sao cho \(0 \le i < j < P\);
• \(B[i] \ne B[j]\) với mọi \(i,j\) sao cho \(0 \le i < j < R\);
• \(A[i] \ne B[j]\) với mọi \(i,j\) sao cho \(0 \le i < P\) và \(0 \le j < R\).

Đối với mỗi cuộc gọi, bộ phận điều phối báo cáo xem có con đường nối giữa một điểm du lịch từ \(A\) và một điểm du lịch từ \(B\) hay không. Cụ thể, bộ phận điều phối xét tất cả các cặp \(i,j\) sao cho \(0 \le i < P\) và \(0 \le j < R\). Nếu với bất kì cặp nào trong chúng, các điểm du lịch \(A[i]\) và \(B[j]\) được nối bởi một con đường, bộ phận điều phối trả về true. Nếu không, bộ phận điều phối trả về false.

Một hành trình có độ dài \(l\) là một chuỗi các điểm du lịch khác nhau \(t[0],t[1],\ldots,t[l-1]\), trong đó với mỗi \(i\) từ \(0\) đến \(l-2\) (kể cả hai đầu), điểm \(t[i]\) và điểm \(t[i+1]\) được nối bởi một con đường. Một hành trình có độ dài \(l\) được gọi là một hành trình dài nhất nếu không tồn tại bất kì hành trình nào có độ dài tối thiểu là \(l+1\).

Nhiệm vụ của bạn là giúp các nhà tổ chức tìm một hành trình dài nhất ở Ópusztaszer bằng cách thực hiện các cuộc gọi tới bộ phận điều phối.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

std::vector<int> longest_trip(int N, int D);

• \(N\): số lượng điểm du lịch ở Ópusztaszer.
• \(D\): mật độ tối thiểu được đảm bảo của mạng lưới đường đi.
• Hàm này cần trả về một mảng \(t=[t[0],t[1],\ldots,t[l-1]]\), biểu diễn một hành trình dài nhất.
• Hàm này có thể được gọi nhiều lần trong mỗi test.

Hàm trên có thể gọi đến hàm sau:

bool are_connected(std::vector<int> A, std::vector<int> B);

• \(A\): một mảng không rỗng gồm các điểm du lịch khác nhau.
• \(B\): một mảng không rỗng gồm các điểm du lịch khác nhau.
• \(A\) và \(B\) phải không có phần tử chung.
• Hàm này trả về true nếu có một điểm du lịch từ \(A\) và một điểm du lịch từ \(B\) được nối bởi một con đường. Ngược lại, hàm trả về false.
• Hàm này có thể được gọi tối đa \(32\,640\) lần trong mỗi lời gọi longest_trip, và tối đa \(150\,000\) lần tổng cộng.
• Tổng độ dài của các mảng \(A\) và \(B\) được truyền vào hàm này qua tất cả các lần gọi không được vượt quá \(1\,500\,000\).

Trình chấm không thích nghi. Mỗi bài nộp được chấm trên cùng một bộ test. Nghĩa là các giá trị \(N\) và \(D\), cũng như các cặp điểm du lịch được nối bởi các con đường, đều cố định đối với mỗi lời gọi longest_trip trong mỗi test.

Các ví dụ

Ví dụ 1

Xét kịch bản khi \(N=5\), \(D=1\), và các kết nối đường đi được chỉ ra trong hình vẽ sau:

Hàm longest_trip được gọi theo cách sau:

longest_trip(5, 1)

Hàm này có thể thực hiện các lời gọi đến hàm are_connected như sau:

Sau lần gọi thứ tư, nhận thấy không có cặp nào trong số \((1,4)\), \((0,4)\), \((1,3)\) và \((0,3)\) được nối bởi một con đường. Vì mật độ của mạng ít nhất là \(D=1\), ta thấy rằng từ bộ ba \((0,3,4)\), cặp \((3,4)\) phải được nối bởi một con đường. Tương tự, các điểm du lịch \(0\) và \(1\) phải được nối với nhau.

Tại thời điểm này, có thể kết luận rằng \(t=[1,0,2,3,4]\) là một hành trình có độ dài \(5\) và không tồn tại hành trình có độ dài lớn hơn \(5\). Do đó, hàm longest_trip có thể trả về \([1,0,2,3,4]\).

Xét một kịch bản khác khi \(N=4\), \(D=1\), và các con đường giữa các điểm du lịch được chỉ ra trong hình sau:

Hàm longest_trip được gọi theo cách sau:

longest_trip(4, 1)

Trong kịch bản này, độ dài của hành trình dài nhất là \(2\). Do đó, sau một vài lời gọi đến hàm are_connected, hàm longest_trip có thể trả về một trong số \([0,1]\), \([1,0]\), \([2,3]\) hoặc \([3,2]\).

Ví dụ 2

Subtask \(0\) chứa thêm một test ví dụ với \(N=256\) điểm du lịch. Test này có trong gói đính kèm mà bạn có thể tải về từ hệ thống cuộc thi.

Các ràng buộc

• \(3 \le N \le 256\).
• Tổng các giá trị \(N\) trong tất cả lời gọi đến longest_trip không vượt quá \(1\,024\) trong mỗi test.
• \(1 \le D \le 3\).

Các subtask

Trong subtask \(4\), điểm của bạn được xác định dựa trên số lần gọi hàm are_connected trong một lần gọi longest_trip. Gọi \(q\) là số lần gọi lớn nhất trong số tất cả các lần gọi longest_trip trong mọi test của subtask. Điểm của bạn cho subtask này được tính theo bảng sau:

Nếu trong bất kì test nào các lời gọi hàm are_connected không tuân theo các ràng buộc được mô tả trong phần Chi tiết cài đặt, hoặc mảng được trả về bởi longest_trip không đúng, điểm cho lời giải của bạn đối với subtask đó sẽ là \(0\).

Trình chấm mẫu

Gọi \(C\) là số lượng kịch bản, nghĩa là số lần gọi đến longest_trip. Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

dòng 1: C

Theo sau là mô tả của \(C\) kịch bản. Trình chấm mẫu đọc mô tả mỗi kịch bản theo định dạng sau:

dòng 1: N D
dòng 1 + i (1 ≤ i < N): U_i[0] U_i[1] … U_i[i − 1]

Ở đây, mỗi \(U_i\) (\(1 \le i < N\)) là một mảng kích thước \(i\), mô tả các cặp điểm du lịch được nối bởi một con đường. Với mỗi \(i,j\) sao cho \(1 \le i < N\) và \(0 \le j < i\):

• nếu các điểm du lịch \(j\) và \(i\) được nối bởi một con đường thì \(U_i[j]\) phải bằng \(1\);
• nếu không có con đường nào nối các điểm du lịch \(j\) và \(i\) thì \(U_i[j]\) phải bằng \(0\).

Trong mỗi kịch bản, trước khi gọi longest_trip, trình chấm mẫu kiểm tra xem mật độ của mạng lưới đường đi có ít nhất là \(D\) hay không. Nếu điều kiện này không thỏa mãn, nó in thông báo Insufficient Density và kết thúc.

Nếu trình chấm mẫu phát hiện vi phạm giao thức, đầu ra của trình chấm mẫu là Protocol Violation: <MSG>, trong đó <MSG> là một trong các thông báo lỗi sau:

• invalid array: trong một lời gọi tới are_connected, ít nhất một trong hai mảng \(A\) và \(B\) là rỗng, hoặc chứa một phần tử không phải là số nguyên từ \(0\) đến \(N-1\) (kể cả hai đầu), hoặc có một phần tử xuất hiện ít nhất hai lần.
• non-disjoint arrays: trong một lời gọi tới are_connected, các mảng \(A\) và \(B\) có phần tử chung.
• too many calls: số lần gọi đến are_connected vượt quá \(32\,640\) trong lời gọi hiện tại tới longest_trip, hoặc vượt quá \(150\,000\) tổng cộng.
• too many elements: tổng số điểm du lịch được truyền vào are_connected trên tất cả các lời gọi vượt quá \(1\,500\,000\).

Ngược lại, gọi các phần tử của mảng được trả về bởi longest_trip trong một kịch bản là \(t[0],t[1],\ldots,t[l-1]\) với một số \(l\) không âm. Trình chấm mẫu in ba dòng đối với kịch bản này theo định dạng sau:

dòng 1: l
dòng 2: t[0] t[1] … t[l − 1]
dòng 3: số lần gọi tới are_connected trong kịch bản này

Cuối cùng, trình chấm mẫu in:

dòng 1 + 3 · C: số lần gọi tới are_connected lớn nhất trong tất cả các lần gọi tới longest_trip

Nguồn: Olympic Tin học Quốc tế 2023 (IOI 2023). Bản dịch tiếng Việt chính thức của đoàn Việt Nam, được đối chiếu với đề tiếng Anh chính thức. Nội dung đề được phát hành theo giấy phép CC BY.