Đây là bài toán giao tiếp.
Trong ngày lễ ngập tràn hương thơm ngọt ngào này, việc làm món tráng miệng cuối cùng — sữa hai lớp — đã gặp phải một thử thách cuối cùng.
Là món tráng miệng được yêu thích nhất trong cửa hàng, một phần sữa hai lớp hoàn hảo cần kết hợp hài hòa lớp bánh ở trên với lớp pudding ở dưới. Trong vương quốc bọ chét kỳ diệu này, năng lượng của hai lớp thành phần tráng miệng đan xen với nhau, ẩn trong mạng lưới thành phố phức tạp.
Hai bậc thầy làm món tráng miệng giàu kinh nghiệm của cửa hàng — dacake8 và dapudding8 — quyết định thử thách bạn. Họ giấu bánh và pudding trên các con đường giữa các thành phố. Chỉ bằng cách hỏi họ và xác định chính xác một thành phố được nối với cửa hàng chính nơi bạn đang ở (thành phố $1$) bằng một con đường có giấu món tráng miệng, bạn mới có thể hoàn thành món sữa hai lớp cuối cùng này!
Có $n$ thành phố, và giữa mỗi cặp thành phố đều có một con đường nối chúng. Có $n-1$ miếng bánh; miếng thứ $i$ nằm trên con đường nối thành phố $u_{i,1}$ với thành phố $v_{i,1}$. Có $n-1$ phần pudding; phần thứ $i$ nằm trên con đường nối thành phố $u_{i,2}$ với thành phố $v_{i,2}$. Các con đường có bánh và các con đường có pudding lần lượt tạo thành hai cây.
Ban đầu, bạn không biết vị trí cụ thể của bánh và pudding. Bạn có thể thực hiện tối đa $\min(1000,\frac{n\times(n-1)}{2})$ truy vấn với dacake8 và dapudding8:
Hỏi dacake8 và dapudding8 về thành phố $u$ và thành phố $v$. Ban đầu, đa tập $S$ rỗng.
- dacake8 xuất phát từ thành phố $u$, đi theo đường đi có bánh đến thành phố $v$, và thêm số hiệu của các thành phố đi qua vào đa tập $S$.
- dapudding8 xuất phát từ thành phố $u$, đi theo đường đi có pudding đến thành phố $v$, và thêm số hiệu của các thành phố đi qua vào đa tập $S$.
- Thư viện giao tiếp trả về đa tập $S$.
Bạn đang ở thành phố $1$. Sau khi kết thúc các truy vấn, bạn cần đưa ra một thành phố $u$ sao cho con đường nối thành phố $1$ với thành phố $u$ có một loại món tráng miệng.
dacake8 và dapudding8 không muốn làm khó bạn. Họ đảm bảo rằng vị trí của bánh và pudding đã được xác định trước khi bắt đầu truy vấn. Nói cách khác, thư viện giao tiếp không thích nghi.
Chi tiết cài đặt
Bạn không cần và cũng không nên cài đặt hàm main.
Bạn cần đưa tệp tiêu đề milk.h vào tệp mã nguồn milk.cpp và cài đặt hai hàm sau:
void init(int c, int t);- $c,t$ lần lượt biểu thị số hiệu nhiệm vụ con và số bộ dữ liệu kiểm tra. $id=0$ biểu thị rằng điểm kiểm tra này là ví dụ.
- Với mỗi điểm kiểm tra, thư viện giao tiếp sẽ gọi hàm này đúng một lần khi chương trình bắt đầu chạy.
int find(int c, int n);- $c,n$ lần lượt biểu thị số hiệu nhiệm vụ con và số thành phố.
- Hàm này cần trả về một số nguyên dương $u$, tức là đưa ra một thành phố $u$ sao cho con đường nối thành phố $1$ với thành phố $u$ có một loại món tráng miệng.
- Với mỗi điểm kiểm tra, thư viện giao tiếp sẽ gọi hàm này đúng $t$ lần.
Bạn có thể thực hiện một truy vấn bằng cách gọi hàm sau:
std::vector<int>query(int u, int v);- $u,v$ biểu thị hai thành phố $u$ và $v$ được đưa ra.
- Bạn cần đảm bảo rằng $1\le u,v\le n$ và $u\ne v$.
- Hàm này trả về đa tập $S$, có ý nghĩa cụ thể được mô tả trong đề bài.
- Gọi kích thước của đa tập $S$ là $m$. Khi đó, $1\le S_i\le n$ và $S_0\le S_1\le \ldots \le S_{m-1}$.
- Bạn cần đảm bảo rằng mỗi lần thư viện giao tiếp gọi
find, số lần gọi hàm này không vượt quá $1000$.
Cách kiểm tra chương trình
Đặt milk.cpp, milk.h và tệp grader.cpp trong phần đính kèm vào cùng một thư mục, rồi biên dịch bằng C++17:
g++ grader.cpp milk.cpp -o milk -O2 -std=c++17
./milk < ex_milk1.inĐối với tệp thực thi milk thu được sau khi biên dịch:
Dòng đầu tiên trong dữ liệu vào của thư viện giao tiếp chứa hai số nguyên không âm $id,t$, lần lượt biểu thị số hiệu điểm kiểm tra và số bộ dữ liệu kiểm tra.
Với mỗi bộ dữ liệu kiểm tra, dòng đầu tiên chứa một số nguyên dương $n$, biểu thị số thành phố. Mỗi dòng từ dòng $2\sim n$ chứa hai số nguyên dương $u_{i,1}$, $v_{i,1}$; mỗi dòng trong $n-1$ dòng tiếp theo chứa hai số nguyên dương $u_{i,2}$, $v_{i,2}$.
Nếu đáp án của cả $t$ lần gọi find đều đúng, thư viện giao tiếp in Correct! ở dòng đầu tiên và Max queries used: Q ở dòng thứ hai, trong đó $Q$ biểu thị số lần gọi query lớn nhất trong tất cả các bộ dữ liệu kiểm tra. Nếu ít nhất một đáp án sai, thư viện in Wrong answer.; nếu một lời gọi giao diện không hợp lệ, nguyên nhân lỗi cũng sẽ được đưa ra trên luồng lỗi chuẩn.
Ví dụ
Dữ liệu vào 1
0 3 5 1 5 2 5 2 4 3 5 1 2 1 4 3 4 4 5 8 1 2 2 3 3 4 4 5 5 6 6 7 7 8 1 7 2 4 3 6 4 6 5 7 5 8 6 8 2 1 2 1 2
Dữ liệu ra 1
Correct! Max queries used: 28
Ghi chú
Lưu ý rằng dữ liệu kiểm tra cuối cùng không chứa ví dụ.
Trong hình, cạnh màu đỏ biểu thị rằng con đường giữa hai thành phố có một miếng bánh, còn cạnh màu xanh lam biểu thị rằng con đường giữa hai thành phố có một phần pudding.
Đối với bộ dữ liệu thứ nhất, hai cây tạo bởi các con đường có bánh và có pudding có hình dạng như sau:
Đối với bộ dữ liệu thứ hai, hai cây tạo bởi các con đường có bánh và có pudding có hình dạng như sau:
Đối với bộ dữ liệu thứ ba, một con đường cũng có thể đồng thời có cả bánh và pudding.
Giới hạn
| Số hiệu nhiệm vụ con $c=$ | $t=$ | $n=$ | Tính chất đặc biệt | Điểm |
|---|---|---|---|---|
| $1$ | $6$ | $3$ | Không có | $1$ |
| $2$ | $7875$ | $5$ | Không có | $2$ |
| $3$ | $100$ | $8$ | Không có | $3$ |
| $4$ | $1$ | $10^5$ | $\text{A}$ | $5$ |
| $5$ | $5$ | $10^5$ | $\text{B}$ | $5$ |
| $6$ | $10^3$ | $100$ | $\text{C}$ | $1$ |
| $7$ | $5$ | $10^5$ | $\text{C}$ | $5$ |
| $8$ | $10^3$ | $100$ | $\text{D}$ | $5$ |
| $9$ | $5$ | $10^5$ | $\text{D}$ | $15$ |
| $10$ | $10^3$ | $100$ | $\text{E}$ | $5$ |
| $11$ | $5$ | $10^5$ | $\text{E}$ | $15$ |
| $12$ | $10^3$ | $100$ | $\text{F}$ | $5$ |
| $13$ | $5$ | $10^5$ | $\text{F}$ | $15$ |
| $14$ | $10^3$ | $100$ | Không có | $15$ |
| $15$ | $5$ | $10^5$ | Không có | $3$ |
Tính chất đặc biệt $\text{A}$: Vị trí của bánh và pudding được sinh hoàn toàn ngẫu nhiên.
Tính chất đặc biệt $\text{B}$: Đảm bảo rằng chỉ có một đáp án có thể đúng.
Tính chất đặc biệt $\text{C}$: Nếu lấy thành phố $1$ làm gốc trong cả hai cây tạo bởi các con đường có bánh và có pudding, rồi từ mỗi thành phố nối một cạnh đến thành phố cha của nó trong từng cây, thì đồ thị có hướng thu được là một DAG.
Tính chất đặc biệt $\text{D}$: Nếu lấy thành phố $2$ làm gốc trong cả hai cây tạo bởi các con đường có bánh và có pudding, rồi từ mỗi thành phố nối một cạnh đến thành phố cha của nó trong từng cây, thì đồ thị có hướng thu được là một DAG.
Tính chất đặc biệt $\text{E}$: Vị trí của pudding được sinh hoàn toàn ngẫu nhiên. Vị trí của bánh không phụ thuộc vào vị trí của pudding.
Tính chất đặc biệt $\text{F}$: Hai cây tạo bởi các con đường có bánh và có pudding là hai đường đi dạng chuỗi, và cả hai đều có thành phố $1$ làm đầu chuỗi.
Trong bài toán này, việc sinh cây ngẫu nhiên được định nghĩa là sử dụng một dãy Prufer ngẫu nhiên.
Nhiệm vụ con
Nếu đáp án do find trả về không đúng hoặc tham số của query không hợp lệ, hệ số điểm của điểm kiểm tra đó là $0$.
Đối với các nhiệm vụ con $1,2,3$, nếu số truy vấn vượt quá $\frac{n\times(n-1)}{2}$, hệ số điểm của điểm kiểm tra đó là $0$; nếu không, hệ số điểm là $1$.
Đối với các nhiệm vụ con $4\sim 15$, gọi $Q$ là số lần gọi query lớn nhất trong tất cả các bộ dữ liệu kiểm tra. Hệ số điểm $f(Q)$ được tính theo bảng sau:
| Khoảng của $Q$ | $f(Q)$ |
|---|---|
| $Q\le 100$ | $1$ |
| $100< Q\le 1000$ | $1-\log_{20}(\frac{Q}{100})$ |
| $Q>1000$ | $0$ |
Điểm cuối cùng của một điểm kiểm tra bằng số điểm của điểm kiểm tra đó nhân với hệ số điểm, được giữ đến ba chữ số sau dấu phẩy theo quy tắc điểm số thực của UOJ.
Giới hạn thời gian: $20\ \mathrm{s}$.
Giới hạn bộ nhớ: $512\ \mathrm{MiB}$.