Đề bài

Sau khi dùng lợi nhuận bán rô-bốt để thuê một trợ lý, bạn đã sẵn sàng tìm chiếc két chứa huy chương CEOI.

Két nằm trong một tòa nhà đại học gồm \(N\) phòng và \(N-1\) cánh cửa nối các phòng. Từ mọi phòng đều có thể đến mọi phòng khác, và mỗi phòng có nhiều nhất \(3\) cửa. Bạn và trợ lý đều có sơ đồ của cùng tòa nhà, nhưng hai bản sơ đồ có thể đánh số các phòng và các cửa khác nhau.

Trợ lý sẽ tìm căn phòng chứa két rồi để lại dấu hiệu bí mật giúp bạn tìm đến đó. Dấu hiệu là những chiếc cà vạt giống hệt nhau, nên thông tin duy nhất tại một phòng là số cà vạt được để lại trong phòng ấy. Để tránh gây chú ý, số cà vạt lớn nhất trong một phòng cần càng nhỏ càng tốt theo phần chấm điểm.

Sau đó, bạn bắt đầu từ một phòng nào đó và phải dùng các dấu hiệu để tìm phòng chứa két. Bản thân chiếc két bị giấu nên bạn không thể nhận ra nó chỉ bằng cách bước vào phòng. Bạn phải đi qua nhiều nhất \(d+30\) cánh cửa, trong đó \(d\) là số cửa trên đường đi trực tiếp từ vị trí bắt đầu đến phòng chứa két. Mỗi lần đi qua một cánh cửa đều được tính, kể cả khi đi qua cùng một cửa nhiều lần.

Hãy viết chương trình:

• Chỉ dẫn trợ lý số cà vạt cần để lại trong mỗi phòng.
• Sau đó dẫn bạn đến phòng chứa két.

Giao tiếp

Đây là bài giao tiếp mà chương trình được chạy hai lần riêng biệt cho mỗi bộ kiểm thử. Bạn phải nộp mã nguồn C++ cài đặt hai hàm sau, đồng thời khai báo giao diện bằng cách #include "incursion.h":

std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe);
void locate(std::vector<std::pair<int, int>> F, int curr, int t);

Hàm do trình chấm cung cấp:

int visit(int v);

Lần chạy thứ nhất: mark

std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe);

• F chứa \(N-1\) cặp \((u,v)\) với \(1\le u,v\le N\) và \(u\ne v\). Mỗi cặp biểu thị một cánh cửa nối phòng \(u\) và phòng \(v\).
• safe là số hiệu căn phòng chứa két theo cách đánh số trong bản sơ đồ của trợ lý.

Hàm phải trả về một vector T gồm đúng \(N\) số nguyên T[0], T[1], ..., T[N-1]. Giá trị T[i] là số cà vạt trợ lý để lại trong phòng \(i+1\) và phải thỏa mãn

Trong lần chạy này, không được gọi visit.

Lần chạy thứ hai: locate

void locate(std::vector<std::pair<int, int>> F, int curr, int t);

• F mô tả cùng một cây phòng, nhưng số hiệu phòng và thứ tự các cửa có thể khác hoàn toàn so với lần chạy thứ nhất.
• curr là phòng hiện tại của bạn theo cách đánh số trong bản sơ đồ thứ hai.
• t là số cà vạt được tìm thấy trong phòng curr.

Trong hàm này, bạn có thể gọi:

int visit(int v);

Lời gọi này di chuyển từ phòng hiện tại đến phòng \(v\) theo cách đánh số của bản sơ đồ thứ hai, rồi trả về số cà vạt trợ lý đã để trong phòng đó. Phải có một cánh cửa nối trực tiếp phòng hiện tại với \(v\), và \(1\le v\le N\).

Khi locate kết thúc, vị trí hiện tại phải là phòng chứa két. Tổng số lời gọi visit không được vượt quá \(d+30\), với \(d\) được định nghĩa ở trên.

Nếu gọi visit quá nhiều lần, gọi với đối số không hợp lệ, gọi trong lần chạy thứ nhất, trả về vector không hợp lệ từ mark, hoặc kết thúc locate ở sai phòng, chương trình bị dừng và bộ kiểm thử đó bị chấm sai.

Không được đọc từ đầu vào chuẩn hoặc ghi ra đầu ra chuẩn. Làm vậy có thể nhận kết quả Security violation!. Bạn được phép ghi ra luồng lỗi chuẩn (stderr).

Trình chấm chính thức có tính thích nghi: cách tương ứng giữa hai cách đánh số có thể phụ thuộc vào hành vi của chương trình trong lần chạy hiện tại cũng như các lần chạy trước.

Ràng buộc

• \(2\le N\le45\,000\).
• Mỗi phòng có bậc không quá \(3\).

Phân nhóm

Gọi

• Subtask 1 (30 điểm): Không có phòng nào có \(3\) cửa.
• Subtask 2 (30 điểm): Có đúng một phòng có \(2\) cửa.
• Subtask 3 (40 điểm): Không có ràng buộc bổ sung.

Trong mỗi subtask, phần điểm thực nhận phụ thuộc vào \(T_{\max}\):

Ví dụ giao tiếp

Xét tòa nhà có \(N=3\) với sơ đồ dưới đây. Trong mỗi phòng, số thứ nhất là số hiệu trên sơ đồ của trợ lý và số thứ hai là số hiệu trên sơ đồ của bạn. Phòng lớn phía dưới, tô màu vàng, chứa két; phòng phía trên bên phải, có viền đậm, là vị trí bắt đầu.

![Hai cách đánh số phòng trong ví dụhttps://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_f62a8e6f.png

Trong lần chạy thứ nhất, trình chấm gọi:

mark({{1, 2}, {2, 3}}, 1)

Giả sử hàm trả về {2, 2, 0}: trợ lý để hai cà vạt trong phòng \(1\) và \(2\), không để cà vạt trong phòng \(3\).

Trong lần chạy thứ hai, trình chấm gọi:

locate({{1, 3}, {2, 3}}, 1, 0)

Một phiên giao tiếp có thể diễn ra như sau:

Bạn đã đi qua bốn cánh cửa, trong khi khoảng cách trực tiếp \(d\) từ vị trí bắt đầu đến két là \(2\).

Trình chấm mẫu

Để thử chương trình cục bộ, liên kết lời giải với sample_grader.cpp và incursion.h. Để đơn giản, trình chấm mẫu không chạy chương trình trong hai tiến trình riêng mà gọi mark rồi locate đúng một lần trong cùng một lần chạy.

Trình chấm mẫu đọc \(N\) và safe, sau đó đọc \(N-1\) cặp mô tả F. Nó gọi mark(F, safe) và in vector trả về. Tiếp theo, nó đọc vị trí bắt đầu curr, gọi locate(F, curr, T[curr-1]) và in biên bản các lời gọi visit. Trình chấm mẫu không thay đổi cách đánh số phòng và cửa giữa hai hàm.

Khi kết thúc, trình chấm mẫu in một trong các thông báo:

• Invalid input: dữ liệu cho trình chấm không đúng định dạng.
• Invalid call to visit: visit được gọi từ mark hoặc với đối số không hợp lệ.
• Invalid return value of mark: vector trả về không có đúng \(N\) phần tử hoặc có giá trị ngoài đoạn \([0,10^9]\).
• Correct: at most Tmax tie(s) per room: locate kết thúc ở phòng chứa két và giá trị lớn nhất trong vector là \(T_{\max}\).
• Not correct: current position is curr: locate kết thúc ở một phòng khác phòng chứa két.

Trình chấm chính thức chỉ trả về Not correct, Security violation!, Partially correct hoặc Correct. Cả trình chấm mẫu lẫn trình chấm chính thức đều tự động dừng chương trình ngay khi phát hiện lỗi. Các giới hạn tài nguyên được áp dụng riêng cho từng lần chạy chính thức.