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.