JOI 2024 - Tuyển chọn mùa xuân - Ngày 4

Vương quốc IOI gồm \(N\) thành phố nằm trên một đường từ tây sang đông, được đánh số từ \(1\) đến \(N\) theo thứ tự từ phía tây.

Ở vương quốc IOI, đơn vị thời gian là Byou và một ngày dài \(T\) Byou. Thời điểm đã trôi qua \(x\) Byou kể từ đầu ngày, với \(0 \le x < T\), được gọi là thời điểm \(x\). Vì vậy, sau một Byou kể từ thời điểm \(T-1\) của một ngày là thời điểm \(0\) của ngày tiếp theo.

JOI là một tổ chức bí mật hoạt động trong vương quốc IOI. Các thành viên phải tránh những trạm kiểm soát của vương quốc, nên khi di chuyển giữa các thành phố, họ chỉ được sử dụng các chuyến bay của hãng hàng không JOY.

Hãng JOY khai thác \(M_i\) chuyến bay khởi hành từ thành phố \(i\) \((1 \le i \le N-1)\). Chuyến bay thứ \(j\) \((1 \le j \le M_i)\) khởi hành từ thành phố \(i\) vào thời điểm \(A_{i,j}\) mỗi ngày và đến thành phố \(i+1\) vào thời điểm \(B_{i,j}\) trong cùng ngày, với \(A_{i,j}<B_{i,j}\). Việc nối chuyến rất thuận tiện: một người có thể khởi hành đúng lúc vừa đến một thành phố. Người đó cũng có thể chờ qua đêm tại sân bay của bất kỳ thành phố nào.

Tổ chức có \(Q\) thành viên, được đánh số từ \(1\) đến \(Q\). Thành viên \(k\) có căn cứ hoạt động ở thành phố \(L_k\) và nơi sinh sống ở thành phố \(R_k\). Người đó muốn biết thời gian ngắn nhất tính từ lúc rời thành phố \(L_k\) đến lúc tới thành phố \(R_k\), khi được tự chọn thời điểm khởi hành và các chuyến bay sẽ sử dụng.

Cho thông tin về các chuyến bay và các thành viên, hãy tính thời gian ngắn nhất cho từng thành viên.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N T
M_1
A_{1,1} B_{1,1}
...
A_{1,M_1} B_{1,M_1}
M_2
A_{2,1} B_{2,1}
...
A_{2,M_2} B_{2,M_2}
...
M_{N-1}
A_{N-1,1} B_{N-1,1}
...
A_{N-1,M_{N-1}} B_{N-1,M_{N-1}}
Q
L_1 R_1
...
L_Q R_Q

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(k\) chứa thời gian ngắn nhất để thành viên \(k\) đi từ thành phố \(L_k\) đến thành phố \(R_k\), tính bằng Byou nhưng không in tên đơn vị.

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(2 \le T \le 10^9\).
• \(M_i \ge 1\) với mọi \(1 \le i \le N-1\).
• \(M_1+M_2+\cdots+M_{N-1} \le 100\,000\).
• \(0 \le A_{i,j}<B_{i,j}<T\) với mọi \(1 \le i \le N-1\), \(1 \le j \le M_i\).
• \(1 \le Q \le 300\,000\).
• \(1 \le L_k<R_k \le N\) với mọi \(1 \le k \le Q\).
• Tất cả giá trị đầu vào đều là số nguyên.

Phân nhóm

• Nhóm 1 (6 điểm): \(N \le 2\,000\) và \(M_i=1\) với mọi \(i\).
• Nhóm 2 (8 điểm): \(N \le 2\,000\) và \(M_i \le 5\) với mọi \(i\).
• Nhóm 3 (17 điểm): \(M_i=1\) với mọi \(i\).
• Nhóm 4 (23 điểm): \(M_i \le 5\) với mọi \(i\).
• Nhóm 5 (36 điểm): \(N \le 90\,000\), \(Q \le 90\,000\) và \(M_1+\cdots+M_{N-1} \le 90\,000\).
• Nhóm 6 (10 điểm): Không có ràng buộc bổ sung.

Ví dụ

4 10000
1
100 300
2
200 400
300 600
1
500 600
3
1 3
2 4
1 4

500
400
10500

6 10000
1
100 300
1
400 700
1
500 600
1
300 900
1
200 800
1
1 6

30700

Nguồn

JOI 2023/2024, kỳ thi tuyển chọn mùa xuân, ngày thi thứ tư (24/03/2024). Đề của Ủy ban Olympic Tin học Nhật Bản (JCIOI). Bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.

Vương quốc JOI có \(N\) hòn đảo, được đánh số từ \(1\) đến \(N\), và \(N-1\) tuyến đường biển, được đánh số từ \(1\) đến \(N-1\). Tuyến thứ \(j\) nối đảo \(A_j\) với đảo \(B_j\) theo cả hai chiều. Có thể đi từ bất kỳ đảo nào đến bất kỳ đảo nào khác bằng cách sử dụng một số tuyến đường biển.

Aoi đang lên kế hoạch du lịch ở vương quốc JOI nhưng không biết những tuyến đường biển này. Cô sẽ hỏi Bitaro, một cư dân của vương quốc, theo cách sau:

1. Aoi đưa ra hai số nguyên \(v,k\), với \(1 \le v \le N\) và \(1 \le k \le N-1\).
2. Bitaro cho biết số hiệu của đảo gần đảo \(v\) thứ \(k\) trong số \(N-1\) đảo khác \(v\). Cụ thể, gọi \(\operatorname{dist}(v,i)\) là số tuyến đường biển ít nhất cần dùng để đi từ đảo \(v\) đến đảo \(i\). Bitaro trả về số nguyên \(i\) \((1 \le i \le N, i\ne v)\) có giá trị \(\operatorname{dist}(v,i)\times N+i\) nhỏ thứ \(k\). Như vậy, các đảo được xếp theo khoảng cách tăng dần, và khi bằng khoảng cách thì theo số hiệu tăng dần.

Aoi muốn xác định tất cả các tuyến đường biển nhưng chỉ được hỏi Bitaro tối đa \(L\) lần. Cho số đảo và giới hạn số câu hỏi, hãy cài đặt chiến lược giúp Aoi tìm được tất cả các tuyến đường biển.

Chi tiết cài đặt

Nộp một tệp duy nhất tên island.cpp. Tệp này phải có chỉ thị #include "island.h" và cài đặt hàm:

void solve(int N, int L);

Hàm được gọi đúng một lần cho mỗi bộ dữ liệu. N là số đảo, còn L là số câu hỏi tối đa được phép hỏi.

Trong island.cpp, có thể gọi hai hàm sau do chương trình chấm cung cấp:

int query(int v, int k);
void answer(int x, int y);

Hàm query(v, k) đặt một câu hỏi cho Bitaro và trả về số hiệu của đảo gần đảo v thứ k, theo đúng định nghĩa trong đề.

• Phải có \(1 \le v \le N\); nếu không, nhận Wrong Answer [1].
• Phải có \(1 \le k \le N-1\); nếu không, nhận Wrong Answer [2].
• Không được gọi query quá \(L\) lần; nếu vượt quá, nhận Wrong Answer [3].

Hàm answer(x, y) báo rằng có một tuyến đường biển nối đảo x và đảo y.

• Cả x và y phải thuộc đoạn từ \(1\) đến \(N\); nếu không, nhận Wrong Answer [4].
• Phải thực sự có tuyến đường biển nối hai đảo đó: tồn tại \(j\) sao cho \((x,y)=(A_j,B_j)\) hoặc \((x,y)=(B_j,A_j)\). Nếu không, nhận Wrong Answer [5].
• Không được báo cùng một tuyến đường biển từ hai lần trở lên, kể cả khi đổi thứ tự hai đầu mút; nếu vi phạm, nhận Wrong Answer [6].
• Phải gọi answer đúng \(N-1\) lần. Nếu khi solve kết thúc mà số lần gọi không bằng \(N-1\), nhận Wrong Answer [7].

Lưu ý cài đặt

Có thể cài đặt các hàm phụ và sử dụng biến toàn cục. Chương trình nộp không được đọc hoặc ghi đầu vào chuẩn, đầu ra chuẩn, hay giao tiếp với bất kỳ tệp nào bằng bất kỳ cách nào. Có thể ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Chương trình chấm chính thức không thích nghi trong mọi bộ dữ liệu: các tuyến đường biển được cố định từ trước, không thay đổi theo những câu hỏi đã đặt.

Chương trình chấm mẫu

Gói tệp dành cho thí sinh chứa chương trình chấm mẫu grader.cpp, tệp mẫu island.cpp, tệp tiêu đề island.h và compile.sh. Đặt grader.cpp, island.cpp, island.h trong cùng một thư mục rồi biên dịch bằng lệnh dưới đây, hoặc chạy compile.sh:

g++ -std=gnu++20 -O2 -o grader grader.cpp island.cpp

Nếu biên dịch thành công, tệp thực thi grader được tạo ra. Chương trình chấm chính thức khác chương trình chấm mẫu. Chương trình chấm mẫu chạy trong một tiến trình, đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn; đây không phải quyền sử dụng đầu vào/đầu ra chuẩn của mã thí sinh.

Dữ liệu vào

N L
A_1 B_1
A_2 B_2
...
A_{N-1} B_{N-1}

Dữ liệu ra

Nếu đáp án đúng, chương trình chấm mẫu in số lần gọi query, chẳng hạn Accepted: 2024. Nếu đáp án sai, chương trình chấm mẫu in loại lỗi, chẳng hạn Wrong Answer [4]. Các dấu nháy không được in. Nếu chương trình vi phạm nhiều điều kiện, chỉ một loại lỗi được báo.

Ràng buộc

• \(3 \le N \le 300\).
• \(1 \le A_j \le N\) và \(1 \le B_j \le N\) với mọi \(1 \le j \le N-1\).
• \(A_j\ne B_j\) với mọi \(1 \le j \le N-1\).
• Có thể đi từ một đảo bất kỳ đến mọi đảo khác bằng một số tuyến đường biển.
• Tất cả giá trị đầu vào đều là số nguyên. Giá trị \(L\) được quy định theo từng nhóm dưới đây.

Phân nhóm

• Nhóm 1 (2 điểm): \(N=3\), \(L=9\).
• Nhóm 2 (4 điểm): \(L=N^2\); mỗi đảo nối trực tiếp với nhiều nhất hai đảo khác.
• Nhóm 3 (7 điểm): \(L=2N\); mỗi đảo nối trực tiếp với nhiều nhất hai đảo khác.
• Nhóm 4 (9 điểm): \(L=N^2\); đảo \(1\) nối trực tiếp với đúng ba đảo khác, mỗi đảo còn lại nối trực tiếp với nhiều nhất hai đảo khác.
• Nhóm 5 (13 điểm): \(L=3N\); đảo \(1\) nối trực tiếp với đúng ba đảo khác, mỗi đảo còn lại nối trực tiếp với nhiều nhất hai đảo khác.
• Nhóm 6 (15 điểm): \(L=N^2\).
• Nhóm 7 (22 điểm): \(L=3N\).
• Nhóm 8 (28 điểm): \(L=2N\).

Ví dụ giao tiếp

Các ví dụ sau gồm đầu vào của chương trình chấm mẫu và một chuỗi lời gọi hàm tương ứng.

Ví dụ 1

Dữ liệu vào của trình chấm mẫu:

4 16
1 2
2 4
4 3

Lời gọi hàm

Giải thích

Chương trình thí sinh trả lời bằng các lời gọi answer, không in đáp án ra đầu ra chuẩn.

Khoảng cách từ đảo \(2\) đến các đảo \(1,3,4\) lần lượt là \(1,2,1\). Chẳng hạn, để đi từ đảo \(2\) đến đảo \(3\), có thể đi qua tuyến đường biển thứ \(2\) rồi tuyến thứ \(3\).

Xếp các đảo khác \(2\) theo \(\operatorname{dist}(2,i)\times N+i\) tăng dần thu được thứ tự \(1,4,3\). Vì thế, query(2, 1) trả về 1 và query(2, 2) trả về 4.

Ví dụ này thỏa mãn các nhóm \(2,6\), tương ứng với tệp mẫu chính thức sample-01-in.txt.

Ví dụ 2

Dữ liệu vào của trình chấm mẫu:

5 25
5 2
3 1
1 4
1 5

Lời gọi hàm

Giải thích

Chương trình thí sinh trả lời bằng các lời gọi answer, không in đáp án ra đầu ra chuẩn.

Khoảng cách từ đảo \(1\) đến các đảo \(2,3,4,5\) lần lượt là \(2,1,1,1\). Chẳng hạn, để đi từ đảo \(1\) đến đảo \(2\), có thể đi qua tuyến đường biển thứ \(4\) rồi tuyến thứ \(1\).

Xếp các đảo khác \(1\) theo \(\operatorname{dist}(1,i)\times N+i\) tăng dần thu được thứ tự \(3,4,5,2\). Vì thế, query(1, 3) trả về 5 và query(1, 4) trả về 2.

Ví dụ này thỏa mãn các nhóm \(4,6\), tương ứng với tệp mẫu chính thức sample-02-in.txt.

Cả sample-01-in.txt và sample-02-in.txt đều có thể dùng làm đầu vào của chương trình chấm mẫu.

Nguồn

JOI 2023/2024, kỳ thi tuyển chọn mùa xuân, ngày thi thứ tư (24/03/2024). Đề của Ủy ban Olympic Tin học Nhật Bản (JCIOI). Bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.

Một giải bóng bàn được tổ chức ở vương quốc JOI với \(N\) chú hải ly, được đánh số từ \(1\) đến \(N\). Giải đấu diễn ra theo thể thức vòng tròn: mỗi cặp đấu với nhau một trận.

Bitaro cho bạn biết các thông tin sau về kết quả giải đấu:

• Không có trận hòa.
• Có đúng \(M\) cách chọn ba chú hải ly tạo thành một vòng thắng thua. Cụ thể, ba chú hải ly \(i,j,k\) \((1 \le i<j<k \le N)\) tạo thành một vòng thắng thua khi đúng một trong hai điều sau xảy ra: \(i\) thắng \(j\), \(j\) thắng \(k\), \(k\) thắng \(i\); hoặc \(i\) thắng \(k\), \(k\) thắng \(j\), \(j\) thắng \(i\).

Bạn không biết thông tin của Bitaro có chính xác hay không. Hãy xác định có tồn tại kết quả giải đấu phù hợp với thông tin đó hay không; nếu có, hãy tìm một kết quả như vậy.

Dữ liệu vào

Một bộ dữ liệu gồm \(Q\) tình huống, được đánh số từ \(1\) đến \(Q\). Mỗi tình huống cho biết số hải ly tham gia \(N\) và số bộ ba tạo thành vòng thắng thua \(M\).

Đọc từ đầu vào chuẩn theo định dạng:

Q
N_1 M_1
N_2 M_2
...
N_Q M_Q

Cặp \(N_i,M_i\) là các giá trị \(N,M\) của tình huống thứ \(i\).

Dữ liệu ra

In đáp án cho các tình huống theo thứ tự từ \(1\) đến \(Q\).

Nếu tồn tại một kết quả phù hợp, in:

Yes
S_2
S_3
...
S_N

Với mỗi \(2 \le i \le N\), \(S_i\) là xâu độ dài \(i-1\) chỉ gồm 0 và 1. Ký tự thứ \(j\) \((1 \le j<i)\) của \(S_i\) là 0 nếu hải ly \(i\) thua hải ly \(j\), và là 1 nếu hải ly \(i\) thắng hải ly \(j\). Nếu có nhiều kết quả phù hợp, có thể in bất kỳ kết quả nào.

Nếu không tồn tại kết quả phù hợp, in No cho tình huống đó.

Ràng buộc

• \(Q \ge 1\).
• Trong mỗi tình huống, \(3 \le N \le 5\,000\).
• Trong mỗi tình huống, \(0 \le M \le \dfrac{N(N-1)(N-2)}{6}\).
• Tổng các giá trị \(N\) của \(Q\) tình huống không vượt quá \(5\,000\).
• Tất cả giá trị đầu vào đều là số nguyên.

Phân nhóm

• Nhóm 1 (5 điểm): \(M \le N-2\) trong mọi tình huống.
• Nhóm 2 (4 điểm): Tổng các giá trị \(N\) không vượt quá \(7\).
• Nhóm 3 (23 điểm): Tổng các giá trị \(N\) không vượt quá \(20\).
• Nhóm 4 (30 điểm): Tổng các giá trị \(N\) không vượt quá \(150\).
• Nhóm 5 (15 điểm): Tổng các giá trị \(N\) không vượt quá \(600\).
• Nhóm 6 (23 điểm): Không có ràng buộc bổ sung.

Ví dụ

2
3 1
4 4

Yes
0
10
No

Yes
1
01

1
5 3

Yes
0
11
001
0101

Nguồn

JOI 2023/2024, kỳ thi tuyển chọn mùa xuân, ngày thi thứ tư (24/03/2024). Đề của Ủy ban Olympic Tin học Nhật Bản (JCIOI). Bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.