JOI 2017 Final Camp - Ngày 4

Khu đô thị là một lưới chữ nhật có \(H\) đường phố chạy đông-tây và \(W\) đường phố chạy bắc-nam. Khoảng cách giữa hai giao lộ kề nhau là \(1\) km. Đường đông-tây thứ \(i\) từ phía bắc có độ ùn tắc \(A_i\); đường bắc-nam thứ \(j\) từ phía tây có độ ùn tắc \(B_j\). Tất cả \(H+W\) giá trị này đôi một khác nhau và không đổi dọc theo mỗi đường.

Những kẻ bắt cóc di chuyển như sau:

• Chúng luôn ở trong thành phố và trên các đường phố.
• Ban đầu, chúng chọn một hướng có thể đi từ hiện trường.
• Tại một giao lộ, nếu độ ùn tắc của đường cắt ngang lớn hơn đường hiện tại, chúng rẽ. Nếu có thể rẽ theo cả hai phía, chúng chọn tùy ý.
• Nếu độ ùn tắc của đường hiện tại lớn hơn đường cắt ngang, chúng đi thẳng. Nếu đang ở biên thành phố và không thể đi thẳng, chúng dừng lại.

Có \(Q\) giao lộ ứng viên đôi một khác nhau. Với mỗi ứng viên, hãy tính quãng đường lớn nhất mà chúng có thể đi.

Dữ liệu vào

• Dòng đầu chứa \(H,W,Q\).
• Dòng thứ hai chứa \(A_1,\ldots,A_H\).
• Dòng thứ ba chứa \(B_1,\ldots,B_W\).
• \(Q\) dòng tiếp theo, dòng thứ \(k\) chứa \(S_k,T_k\), chỉ giao lộ giữa đường đông-tây thứ \(S_k\) và đường bắc-nam thứ \(T_k\).

Dữ liệu ra

In \(Q\) dòng; dòng thứ \(k\) là quãng đường lớn nhất, tính bằng km, từ ứng viên thứ \(k\).

Ràng buộc

• \(2\le H,W\le 50\,000\).
• \(1\le Q\le 100\).
• \(1\le A_i,B_j\le 10^9\).
• Tất cả \(H+W\) độ ùn tắc đôi một khác nhau.
• \(1\le S_k\le H\), \(1\le T_k\le W\).
• Các cặp \((S_k,T_k)\) đôi một khác nhau.

Phân nhóm

1. \(13\) điểm: \(H,W\le 8\), \(Q=1\)
2. \(10\) điểm: \(H,W\le 2\,000\), \(Q=1\)
3. \(17\) điểm: \(Q=1\)
4. \(4\) điểm: \(H,W\le 2\,000\)
5. \(56\) điểm: Không có

Giới hạn

• Thời gian: 5 giây.
• Bộ nhớ: 512 MB.

Ví dụ

3 3 5
3 2 6
1 4 5
1 1
1 2
2 2
3 1
3 3

4
5
4
4
2

4 5 6
30 10 40 20
15 55 25 35 45
1 3
4 3
2 2
4 1
2 5
3 3

7
6
9
4
6
9

Nguồn

JOI 2016/2017 Spring Training Camp, ngày thi 4, bài Abduction 2.

Mạng đường của Vương quốc JOI là một cây gồm \(N\) thành phố đánh số từ \(0\) đến \(N-1\). Từ thành phố \(0\) đến mọi thành phố khác phải đi qua không quá \(18\) con đường.

Với hai thành phố khác nhau \(X,Y\), cần trả lời đúng một trong ba trường hợp:

1. Mọi đường đi từ \(0\) đến \(X\) đều đi qua \(Y\).
2. Mọi đường đi từ \(0\) đến \(Y\) đều đi qua \(X\).
3. Không thuộc hai trường hợp trên.

Nếu \(X=0\), quy ước đáp án là \(1\); nếu \(Y=0\), quy ước đáp án là \(0\).

Bạn cần xây dựng hai chương trình độc lập. Encoder biết toàn bộ cây và gán cho mỗi thành phố một mã trong \([0,2^{60}-1]\). Device chỉ nhận hai mã, không biết \(N\), cây, hay số hiệu hai thành phố, và phải trả lời truy vấn. Mục tiêu là làm cho mã lớn nhất càng nhỏ càng tốt.

Chi tiết cài đặt

Nộp hai tệp cùng ngôn ngữ.

Tệp Encoder.c hoặc Encoder.cpp khai báo #include "Encoder.h" và cài đặt:

void Encode(int N, int A[], int B[]);

A, B có độ dài \(N-1\); cạnh thứ \(i\) nối A[i] và B[i]. Để gán mã, gọi:

void Code(int city, long long code);

Phải có \(0\le city<N\) và không gán hai lần cho cùng thành phố; nếu không nhận Wrong Answer [1] hoặc [2]. Phải có \(0\le code<2^{60}\), nếu không nhận [3]. Khi Encode kết thúc phải đã gọi Code đúng \(N\) lần, nếu không nhận [4].

Tệp Device.c hoặc Device.cpp khai báo #include "Device.h" và cài đặt:

void InitDevice();
int Answer(long long S, long long T);

InitDevice được gọi một lần trước các truy vấn. Với mỗi truy vấn, Answer nhận mã \(S,T\) của \(X,Y\) và phải trả về \(0\), \(1\) hoặc \(2\) theo định nghĩa trên. Giá trị ngoài khoảng nhận Wrong Answer [5]; giá trị trong khoảng nhưng sai nhận [6].

Nếu một lời gọi bị chấm sai, chương trình kết thúc ngay. Trình tự chấm là: gọi Encode đúng một lần; gọi InitDevice đúng một lần; với mỗi trong \(Q\) truy vấn, gọi Answer(S_j,T_j) với hai mã do Encoder đã gán; sau đó đánh giá toàn bộ bài làm.

Thời gian và bộ nhớ được tính cho cả ba giai đoạn trên; tổng cộng Answer được gọi \(Q\) lần. Bài làm phải không bị Wrong Answer hoặc lỗi thực thi trong bất kỳ lời gọi nào.

Bài làm có thể cài đặt hàm phụ và dùng biến toàn cục. Các tệp được biên dịch cùng trình chấm thành một tệp thực thi; mọi biến toàn cục và hàm nội bộ phải khai báo static để tránh xung đột tên. Tuy vậy, Encoder và Device được chấm trong hai tiến trình riêng biệt, nên không thể chia sẻ biến toàn cục hay bất kỳ trạng thái nào. Không được đọc/ghi luồng chuẩn hoặc giao tiếp qua tệp.

Biên dịch và chạy thử

Gói chính thức chứa trình chấm mẫu và mã nguồn mẫu. Có thể biên dịch bằng một trong các lệnh:

gcc -std=c11 -O2 -o grader grader.c Encoder.c Device.c -lm
g++ -std=c++14 -O2 -o grader grader.cpp Encoder.cpp Device.cpp

Trình chấm thật khác trình chấm mẫu. Trình chấm mẫu chạy trong một tiến trình, đọc đầu vào chuẩn và ghi đầu ra chuẩn.

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

• Dòng đầu chứa \(N,Q\).
• \(N-1\) dòng tiếp theo chứa \(A_i,B_i\).
• \(Q\) dòng tiếp theo chứa \(X_j,Y_j,E_j\); trình chấm mẫu đối chiếu kết quả với \(E_j\).

Dữ liệu ra của trình chấm mẫu

Nếu đúng, trình chấm mẫu in dạng Accepted : max_code=123456. với mã lớn nhất đã dùng. Nếu sai, in một thông báo dạng Wrong Answer [1].; nếu có nhiều lỗi, chỉ một lỗi được báo.

Ràng buộc

• \(2\le N\le 250\,000\).
• \(1\le Q\le 250\,000\).
• \(0\le A_i,B_i<N\) và \(A_i\ne B_i\).
• Có đúng \(N-1\) cạnh và có thể đi từ mọi thành phố tới mọi thành phố khác; do đó các cạnh tạo thành một cây.
• Từ \(0\) tới mọi thành phố đi qua không quá \(18\) cạnh.
• \(0\le X_j,Y_j<N\) và \(X_j\ne Y_j\).

Phân nhóm

• Nhóm 1 (8 điểm): \(N\le 10\).
• Nhóm 2 (92 điểm): không có ràng buộc bổ sung. Gọi \(L\) là mã lớn nhất trên mọi bộ dữ liệu của nhóm này. Điểm nhóm là:

Nếu \(L\ge 2^{38}\), hệ thống thi có thể hiển thị Accepted : 0 points hoặc Wrong Answer.

Giới hạn

• Thời gian: 3 giây, tính trên toàn bộ quy trình chấm.
• Bộ nhớ: 256 MB.

Ví dụ giao tiếp

6 5
4 1
0 3
4 5
3 2
3 4
2 4 2
1 0 0
5 1 2
5 3 0
4 1 1

Nguồn

JOI 2016/2017 Spring Training Camp, ngày thi 4, bài City.

Đồng bằng JOI là một mặt phẳng tọa độ. Có \(N\) con rồng, đánh số từ \(1\) đến \(N\), thuộc \(M\) bộ tộc. Rồng \(i\) đứng tại \((A_i,B_i)\) và thuộc bộ tộc \(C_i\). Không nhất thiết mọi bộ tộc đều có rồng.

Hai ngôi làng nằm tại \((D_1,E_1)\) và \((D_2,E_2)\), được nối bởi một con đường là đoạn thẳng giữa hai điểm đó. Toàn bộ \(N+2\) điểm nói trên đôi một khác nhau và không có ba điểm thẳng hàng.

Khi bộ tộc \(a\) thù địch bộ tộc \(b\), mỗi rồng của bộ tộc \(a\) phóng một quả cầu lửa về phía mỗi rồng của bộ tộc \(b\). Quả cầu đi thẳng qua mục tiêu và tiếp tục theo cùng hướng, nên quỹ đạo là một tia. Với mỗi trong \(Q\) xung đột có thể xảy ra, hãy đếm số quả cầu lửa cắt con đường.

Dữ liệu vào

• Dòng đầu chứa \(N,M\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(A_i,B_i,C_i\).
• Dòng tiếp theo chứa \(D_1,E_1,D_2,E_2\).
• Dòng tiếp theo chứa \(Q\).
• \(Q\) dòng tiếp theo, dòng thứ \(j\) chứa \(F_j,G_j\): bộ tộc \(F_j\) thù địch bộ tộc \(G_j\).

Dữ liệu ra

In \(Q\) dòng; dòng thứ \(j\) là số quả cầu lửa cắt con đường trong xung đột thứ \(j\).

Ràng buộc

• \(2\le N\le 30\,000\).
• \(2\le M\le N\).
• \(-10^9\le A_i,B_i,D_1,E_1,D_2,E_2\le 10^9\).
• \(1\le C_i\le M\).
• \(N+2\) điểm đôi một khác nhau; không có ba điểm thẳng hàng.
• \(1\le Q\le 100\,000\).
• \(1\le F_j,G_j\le M\) và \(F_j\ne G_j\).
• Các cặp có thứ tự \((F_j,G_j)\) đôi một khác nhau.

Phân nhóm

1. \(15\) điểm: \(N\le 3\,000\)
2. \(45\) điểm: \(Q\le 100\)
3. \(40\) điểm: Không có

Giới hạn

• Thời gian: 3 giây.
• Bộ nhớ: 256 MB.

Ví dụ

4 2
0 1 1
0 -1 1
1 2 2
-6 1 2
-2 0 2 0
2
1 2
2 1

1
2

3 2
-1000000000 -1 1
-999999998 -1 1
0 0 2
999999997 1 999999999 1
1
1 2

1

6 3
2 -1 1
1 0 1
0 3 2
2 4 2
5 4 3
3 9 3
0 0 3 3
6
1 2
1 3
2 1
2 3
3 1
3 2

4
2
4
0
2
1

Nguồn

JOI 2016/2017 Spring Training Camp, ngày thi 4, bài Dragon 2.