Vòng Chung kết - Bảng Siêu Cup OLPTH MTTN 2025

Cho một cây gồm \(n\) đỉnh được đánh số từ \(1\) đến \(n\). Với hai đỉnh \(x\) và \(y\) bất kỳ trên cây, gọi \(d(x, y)\) là số cạnh trên đường đi chứa ít cạnh nhất từ \(x\) tới \(y\).

Với mỗi đỉnh \(r\) và cặp đỉnh \((x, y)\) trên cây, ta gọi \(f_r(x, y)\) là đỉnh \(p\) trên cây thỏa mãn:

• \(d(r, x) = d(r, p) + d(p, x)\)
• \(d(r, y) = d(r, p) + d(p, y)\)
• \(p\) là đỉnh có \(d(r, p)\) nhỏ nhất trong tất cả các đỉnh \(p\) thỏa mãn đồng thời hai điều kiện trên.

Dễ thấy rằng, giá trị \(f_r(x, y)\) luôn tồn tại và được xác định duy nhất với định nghĩa trên.

Với một đỉnh \(r\) cho trước, thầy giáo T liệt kê tất cả \(n^2\) bộ ba có dạng \((x, f_r(x, y), y)\) với mọi \(1 \le x, y \le n\). Sau đó, thầy sắp xếp các bộ ba này theo thứ tự từ điển. Nhắc lại, bộ ba \((a_1, a_2, a_3)\) có thứ tự từ điển nhỏ hơn bộ ba \((b_1, b_2, b_3)\) khi và chỉ khi một trong ba điều kiện sau thỏa mãn:

• \(a_1 < b_1\)
• \(a_1 = b_1\) và \(a_2 < b_2\)
• \(a_1 = b_1, a_2 = b_2\) và \(a_3 < b_3\)

Thầy T đưa ra \(q\) câu đố thuộc một trong hai dạng sau:

• 1 r x y: Tìm vị trí của bộ ba \((x, f_r(x, y), y)\) trong dãy sau khi sắp xếp theo quy trình trên.
• 2 r k: Tìm bộ ba ở vị trí thứ \(k\) trong dãy sắp xếp ở trên.

Bạn hãy giúp bạn A trả lời \(q\) câu đố này nhé.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 10^5\)) lần lượt là số đỉnh của cây và số câu đố.
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) (\(1 \le u, v \le n\)) thể hiện một cạnh của cây.
• \(q\) dòng tiếp theo, dòng thứ \(i\) thể hiện một câu đố thuộc một trong hai dạng sau:
  • 1 r x y với \(1 \le r, x, y \le n\).
  • 2 r k với \(1 \le r, \sqrt{k} \le n\).

Output

• In ra \(q\) dòng, dòng thứ \(i\) là câu trả lời của câu đố thứ \(i\).
• Nếu câu đố thứ \(i\) thuộc loại 1, in ra một số nguyên là thứ tự của bộ \((x, f_r(x, y), y)\).
• Nếu câu đố thứ \(i\) thuộc loại 2, in ra hai số nguyên \(x\) và \(y\) thể hiện bộ thứ \(k\) là \((x, f_r(x, y), y)\).

Example

5 2
1 2
1 3
2 4
2 5
1 2 3 4
2 2 13

13
3 4

Scoring

• Subtask \(1\) (\(11\%\) số điểm): \(n \le 300\).
• Subtask \(2\) (\(12\%\) số điểm): \(n, q \le 3000\).
• Subtask \(3\) (\(13\%\) số điểm): với mỗi đỉnh của cây không có quá hai đỉnh kết nối với nó.
• Subtask \(4\) (\(15\%\) số điểm): khoảng cách giữa hai đỉnh bất kỳ trên cây không vượt quá \(40\).
• Subtask \(5\) (\(16\%\) số điểm): không có câu đố loại 1.
• Subtask \(6\) (\(16\%\) số điểm): không có câu đố loại 2.
• Subtask \(7\) (\(17\%\) số điểm): không có rằng buộc gì thêm.

Bạn sẽ chơi trò dò mìn trên một bảng gồm \(n\) hàng và \(m\) cột. Mỗi bảng có đúng \(k\) ô chứa mìn, nhưng bạn không biết vị trí của chúng.

Bạn có thể mở một ô để nhận thông tin về ô đó:

• Nếu ô chứa mìn, thao tác trả về -1 và số lần trúng mìn của ván tăng thêm \(1\).
• Nếu ô không chứa mìn, thao tác trả về số ô chứa mìn trong tối đa \(8\) ô kề cạnh hoặc kề góc với nó.

Mục tiêu là mở tất cả các ô không chứa mìn và hạn chế số lần mở trúng mìn. Bạn không cần mở những ô mà mình đã suy ra là có mìn.

Giao diện thư viện

Đây là bài toán sử dụng giao diện hàm. Thí sinh phải thêm dòng sau vào đầu chương trình:

#include "minesweeper.h"

Không viết hàm main. Hãy cài đặt hàm:

void solve(int n, int m, int k, int b, int l);

Máy chấm gọi solve một lần cho mỗi bảng. Các lời gọi diễn ra liên tiếp trong cùng một tiến trình, vì vậy chương trình phải khởi tạo lại trạng thái riêng của từng ván ở đầu hàm. Trong hàm này, bạn có thể gọi:

int open(int x, int y);

Trong đó \((x,y)\) là ô ở hàng \(x\), cột \(y\), được đánh số từ \(0\):

Mỗi lần gọi open trên một ô có mìn đều được tính là một lần trúng mìn, kể cả khi ô đó đã được mở trước đó. Khi solve kết thúc, mọi ô không chứa mìn phải từng được mở ít nhất một lần; nếu không, kết quả của ván không hợp lệ.

Bạn có thể tải mã nguồn mẫu để xem cấu trúc chương trình cần nộp.

Chấm điểm

Mỗi tệp chấm chứa \(10\) bảng có cùng các tham số \(n,m,k,b,l\). Gọi \(p\) là số lần trúng mìn lớn nhất trong \(10\) ván của tệp đó.

• Nếu \(p \le b\), bạn nhận toàn bộ điểm của tệp.
• Nếu \(b < p \le l\), bạn nhận tỉ lệ

điểm của tệp.

• Nếu \(p>l\) hoặc còn ô không chứa mìn chưa được mở, bạn không nhận điểm của tệp.

Bộ dữ liệu gồm ba nhóm:

Mỗi nhóm lần lượt gồm \(27\), \(35\) và \(38\) tệp chấm; mỗi tệp chứa \(10\) bảng cố định.

Cho \(n\) điểm phân biệt có tọa độ nguyên trên mặt phẳng. Dữ liệu bảo đảm tồn tại \(k\) đường thẳng song song với nhau, cùng song song với trục \(Ox\) hoặc cùng song song với trục \(Oy\), sao cho mọi điểm đã cho đều nằm trên các đường thẳng này.

Bạn cần dùng các đoạn thẳng ngang hoặc dọc có đầu mút nguyên để nối tất cả các điểm thành một thành phần liên thông. Chi phí của một cấu hình là tổng độ dài Manhattan của các đoạn thẳng được sử dụng. Hãy tìm một cấu hình hợp lệ có chi phí càng nhỏ càng tốt.

Hai điểm được xem là liên thông nếu có thể đi từ điểm này đến điểm kia dọc theo hợp của các đoạn thẳng đã chọn.

Dữ liệu vào

Mỗi tệp dữ liệu có định dạng:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\).
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x_i\) và \(y_i\), là tọa độ của một điểm.

Trong bộ dữ liệu hiện tại, \(1 \le n \le 1000\), \(1 \le k \le 5\) và \(0 \le x_i, y_i \le 10^9\).

Đây là bài toán dạng output-only. Tải bộ dữ liệu đầu vào hiện tại. Với mỗi tệp inputs/<tên>.in, hãy tạo tệp kết quả tương ứng tại outputs/<tên>.out và nén thư mục outputs thành tệp ZIP để nộp.

Dữ liệu ra

Mỗi tệp kết quả có định dạng:

• Dòng đầu tiên chứa số nguyên \(C\) — tổng độ dài của các đoạn thẳng.
• Dòng thứ hai chứa số nguyên \(m\) — số đoạn thẳng được sử dụng.
• \(m\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_1\), \(y_1\), \(x_2\), \(y_2\), mô tả đoạn thẳng nối \((x_1,y_1)\) với \((x_2,y_2)\).

Cấu hình phải thỏa mãn:

• Mỗi đoạn thẳng phải nằm ngang hoặc thẳng đứng và có hai đầu mút nguyên.
• \(C\) phải đúng bằng tổng độ dài Manhattan của \(m\) đoạn thẳng.
• Mọi điểm đầu vào phải thuộc hợp các đoạn thẳng và tất cả các điểm phải liên thông với nhau.
• Hai đoạn thẳng khác nhau chỉ được có nhiều nhất một điểm chung. Nếu có điểm chung, điểm đó phải là đầu mút của cả hai đoạn. Vì vậy, các đoạn không được chồng lấn, cắt nhau ở phần trong hoặc tạo thành nút giao chữ T.

Chấm điểm

Với mỗi tệp dữ liệu, gọi \(J\) là chi phí của đáp án Ban giám khảo và \(C\) là chi phí của kết quả hợp lệ của bạn.

• Nếu \(C \le J\), bạn nhận toàn bộ điểm của tệp đó.
• Nếu \(J < C \le 2J\), đặt \(\Delta = \dfrac{C-J}{J}\); bạn nhận tỉ lệ \((1-\Delta)^2\) điểm của tệp đó.
• Nếu \(C > 2J\) hoặc kết quả không hợp lệ, bạn không nhận điểm của tệp đó.

Bộ dữ liệu gồm \(20\) tệp có trọng số bằng nhau:

• Nhóm 1 (\(15\%\)): \(n \le 7\).
• Nhóm 2 (\(10\%\)): \(n \le 50\).
• Nhóm 3 (\(15\%\)): \(k=2\).
• Nhóm 4 (\(15\%\)): \(k \in \{3,4\}\).
• Nhóm 5 (\(45\%\)): \(k=5\).

Ví dụ

3 3
0 1
1 0
2 2

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