3. IOI 2020 - Stations
Mạng trục Internet của Singapore (SIB) gồm \(n\) trạm, được đánh chỉ số từ \(0\) đến \(n-1\). Có \(n-1\) đường truyền hai chiều, được đánh số từ \(0\) đến \(n-2\). Mỗi đường truyền nối hai trạm phân biệt. Hai trạm được nối với nhau bởi một đường truyền được gọi là kề nhau.
Một đường đi từ trạm \(x\) đến trạm \(y\) là một dãy các trạm phân biệt \(a_0,a_1,\ldots,a_p\), trong đó \(a_0=x\), \(a_p=y\) và mỗi cặp trạm liên tiếp trong dãy kề nhau. Có đúng một đường đi từ bất kỳ trạm \(x\) nào đến bất kỳ trạm \(y\) nào khác.
Bất kỳ trạm \(x\) nào cũng có thể tạo một gói tin (một phần dữ liệu) và gửi đến một trạm \(y\) khác, gọi là trạm đích của gói tin. Gói tin phải được định tuyến theo đường đi duy nhất từ \(x\) đến \(y\) như sau. Xét trạm \(z\) hiện đang giữ một gói tin có trạm đích là \(y\), với \(z \ne y\). Trạm \(z\) sẽ:
- Thực thi một hàm định tuyến để xác định trạm kề với \(z\) nằm trên đường đi duy nhất từ \(z\) đến \(y\).
- Chuyển tiếp gói tin đến trạm kề đó.
Tuy nhiên, các trạm có bộ nhớ hạn chế và không lưu toàn bộ danh sách đường truyền của SIB để dùng trong hàm định tuyến.
Nhiệm vụ của bạn là cài đặt một phương thức định tuyến cho SIB, gồm hai hàm. Hàm thứ nhất nhận \(n\), danh sách đường truyền trong SIB và một số nguyên \(k \ge n-1\). Hàm này gán cho mỗi trạm một nhãn nguyên riêng biệt từ \(0\) đến \(k\), tính cả hai đầu mút.
Hàm thứ hai là hàm định tuyến, được triển khai ở tất cả các trạm sau khi gán nhãn. Hàm này chỉ nhận các dữ liệu sau:
- \(s\): nhãn của trạm đang giữ gói tin;
- \(t\): nhãn của trạm đích, với \(t \ne s\);
- \(c\): danh sách nhãn của tất cả các trạm kề với trạm có nhãn \(s\).
Hàm phải trả về nhãn của trạm kề với trạm có nhãn \(s\) mà gói tin cần được chuyển tiếp đến.
Trong một subtask, điểm bài làm phụ thuộc vào giá trị nhãn lớn nhất được gán cho bất kỳ trạm nào; nhìn chung, giá trị này càng nhỏ càng tốt.
Chi tiết cài đặt
Bạn cần cài đặt hai hàm C++ sau:
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v);
- \(n\): số trạm trong SIB.
- \(k\): giá trị nhãn lớn nhất được phép sử dụng.
- \(u\) và \(v\): hai mảng có độ dài \(n-1\) mô tả các đường truyền. Với mỗi \(0 \le i \le n-2\), đường truyền \(i\) nối hai trạm có chỉ số \(u[i]\) và \(v[i]\).
- Hàm phải trả về một mảng \(L\) có độ dài \(n\). Với mỗi \(0 \le i \le n-1\), \(L[i]\) là nhãn được gán cho trạm có chỉ số \(i\). Tất cả phần tử của \(L\) phải đôi một khác nhau và nằm trong đoạn từ \(0\) đến \(k\), tính cả hai đầu mút.
int find_next_station(int s, int t, std::vector<int> c);
- \(s\): nhãn của trạm đang giữ gói tin.
- \(t\): nhãn của trạm đích của gói tin.
- \(c\): mảng chứa nhãn của tất cả các trạm kề với trạm có nhãn \(s\). Mảng được sắp xếp theo thứ tự tăng dần.
- Hàm phải trả về nhãn của trạm kề với trạm có nhãn \(s\) mà gói tin cần được chuyển tiếp đến, tức trạm kề nằm trên đường đi duy nhất đến trạm có nhãn \(t\).
Mỗi test chứa một hoặc nhiều kịch bản độc lập, tức các mô tả SIB khác nhau. Với một test gồm \(r\) kịch bản, chương trình gọi các hàm trên được chạy đúng hai lần.
Trong lần chạy thứ nhất:
labelđược gọi \(r\) lần;- hệ thống chấm lưu các nhãn được trả về;
find_next_stationkhông được gọi.
Trong lần chạy thứ hai:
find_next_stationcó thể được gọi nhiều lần. Trong mỗi lần gọi, một kịch bản bất kỳ được chọn; các nhãn do lời gọilabelcho kịch bản đó trả về được dùng làm dữ liệu vào chofind_next_station;labelkhông được gọi.
Đặc biệt, mọi thông tin lưu trong các biến tĩnh (static) hoặc biến toàn cục trong lần chạy thứ nhất đều không có sẵn để sử dụng trong find_next_station.
Ràng buộc
- \(1 \le r \le 10\).
Với mỗi lần gọi label:
- \(2 \le n \le 1000\).
- \(k \ge n-1\).
- \(0 \le u[i],v[i] \le n-1\) (\(0 \le i \le n-2\)).
Với mỗi lần gọi find_next_station, dữ liệu vào lấy từ một lời gọi label trước đó được chọn tùy ý. Xét các nhãn mà lời gọi đó đã tạo ra:
- \(s\) và \(t\) là nhãn của hai trạm khác nhau.
- \(c\) là dãy nhãn của tất cả các trạm kề với trạm có nhãn \(s\), theo thứ tự tăng dần.
Trong mỗi test, tổng độ dài của tất cả các mảng \(c\) được truyền vào find_next_station, tính gộp tất cả các kịch bản, không vượt quá \(100\,000\).
Phân nhóm
| Subtask | Điểm | Ràng buộc bổ sung |
|---|---|---|
| 1 | 5 | \(k=1000\); không trạm nào có nhiều hơn \(2\) trạm kề. |
| 2 | 8 | \(k=1000\); với mỗi \(0 \le i \le n-2\), đường truyền \(i\) nối trạm \(i+1\) và trạm \(\left\lfloor i/2 \right\rfloor\). |
| 3 | 16 | \(k=1\,000\,000\); có nhiều nhất một trạm có nhiều hơn \(2\) trạm kề. |
| 4 | 10 | \(n \le 8\), \(k=10^9\). |
| 5 | 61 | \(k=10^9\). |
Ở subtask \(5\), bạn có thể nhận điểm thành phần. Gọi \(m\) là giá trị nhãn lớn nhất do label trả về trên tất cả các kịch bản. Điểm cho subtask này được tính theo bảng sau:
| Giá trị nhãn lớn nhất | Điểm |
|---|---|
| \(m \ge 10^9\) | \(0\) |
| \(2000 \le m < 10^9\) | \(50\cdot\log_{5\cdot 10^5}\!\left(\dfrac{10^9}{m}\right)\) |
| \(1000 < m < 2000\) | \(50\) |
| \(m \le 1000\) | \(61\) |
Ví dụ
Ví dụ dưới đây mô tả các lời gọi hàm và giá trị trả về tương ứng.
Ví dụ 1
Input
label(5, 10, [0, 1, 1, 2], [1, 2, 3, 4])
find_next_station(9, 6, [2, 7])
find_next_station(2, 3, [3, 6, 9])Output
[6, 2, 9, 3, 7]
2
3Note
Xét lời gọi label(5, 10, [0, 1, 1, 2], [1, 2, 3, 4]). Có tổng cộng \(5\) trạm và \(4\) đường truyền nối các cặp trạm có chỉ số \((0,1)\), \((1,2)\), \((1,3)\) và \((2,4)\). Mỗi nhãn có thể là một số nguyên từ \(0\) đến \(k=10\).
Để đưa ra cách gán nhãn sau:
| Chỉ số | Nhãn |
|---|---|
| 0 | 6 |
| 1 | 2 |
| 2 | 9 |
| 3 | 3 |
| 4 | 7 |
hàm label phải trả về [6, 2, 9, 3, 7]. Các số trong hình sau thể hiện chỉ số của các trạm ở hình bên trái và nhãn được gán ở hình bên phải.
Giả sử các nhãn đã được gán như trên. Xét lời gọi:
find_next_station(9, 6, [2, 7])Trạm đang giữ gói tin có nhãn \(9\), còn trạm đích có nhãn \(6\). Nhãn của các trạm trên đường đi đến trạm đích lần lượt là:
Do đó, lời gọi phải trả về $2$, là nhãn của trạm mà gói tin cần được chuyển tiếp đến; trạm này có chỉ số $1$.
Xét một lời gọi khác có thể xảy ra:
```sample
find_next_station(2, 3, [3, 6, 9])
```
Hàm phải trả về $3$, vì trạm đích có nhãn $3$ kề với trạm có nhãn $2$, nên phải nhận gói tin trực tiếp.
Dữ liệu vào
Trình chấm mẫu đọc dòng đầu chứa \(r\). Tiếp theo là \(r\) khối, mỗi khối mô tả một kịch bản theo định dạng sau; số dòng dưới đây được tính từ đầu mỗi khối:
- Dòng \(1\):
n k. - Dòng \(2+i\) (\(0 \le i \le n-2\)):
u[i] v[i]. - Dòng \(1+n\): \(q\), số lần gọi
find_next_station. - Dòng \(2+n+j\) (\(0 \le j \le q-1\)):
z[j] y[j] w[j], là chỉ số các trạm liên quan đến lời gọifind_next_stationthứ \(j\). Trạm \(z[j]\) đang giữ gói tin, trạm \(y[j]\) là trạm đích, và trạm \(w[j]\) là trạm mà gói tin phải được chuyển tiếp đến.
Dữ liệu ra
Trình chấm mẫu in dòng đầu chứa \(m\), giá trị nhãn lớn nhất. Tiếp theo là \(r\) khối tương ứng với các kịch bản theo thứ tự trong dữ liệu vào.
Trong mỗi khối, dòng \(1+j\) (\(0 \le j \le q-1\)) chứa chỉ số của trạm có nhãn được trả về bởi lời gọi find_next_station thứ \(j\) trong kịch bản đó.
Lưu ý rằng mỗi lần chạy trình chấm mẫu đều gọi cả label và find_next_station.
Nguồn
IOI 2020, Ngày 2 — Stations (stations). Đề chính thức tiếng Anh và bản dịch tiếng Việt.