Bạn đang tham dự một hội nghị do Amazing Pearl Innovative Organization (APIO) tổ chức tại Đài Loan. Sứ mệnh của tổ chức này là giới thiệu các sáng tạo liên quan đến trà sữa trân châu — thức uống nổi tiếng thế giới. Tuy nhiên, bạn không đến đây để đóng góp chuyên môn kỹ thuật; bạn chỉ muốn thưởng thức đồ uống và tham quan. Trong một chuyến thăm quan, bạn được dẫn đến một khu phế tích cổ đại. Theo hướng dẫn viên, địa điểm này mới được khám phá gần đây và niên đại của nó vẫn còn là bí ẩn.

Hướng dẫn viên giải thích rằng khu phế tích gồm \(N\) tòa tháp, được đánh số từ \(0\) đến \(N-1\), trong đó tháp thứ \(i\) có chiều cao \(H[i]\). Có \(N-1\) con đường hai chiều nối các tháp này với nhau. Nghiên cứu lịch sử cho thấy tháp \(0\) là tháp đầu tiên được xây dựng. Với mỗi tháp \(i\) tiếp theo (với \(i \ge 1\)), người xây dựng đã chọn một tháp đã được xây trước đó \(P[i]\) (\(0 \le P[i] < i\)) làm tháp cha. Để tiện lợi, đặt \(P[0] = -1\). Vật liệu xây dựng được lưu trữ tại tháp cha. Để tạo điều kiện vận chuyển, một con đường hai chiều được xây dựng riêng giữa \(P[i]\) và \(i\).

Thật không may, nhiều tháp đã bị đổ nát một phần và các con đường bị chôn vùi dưới bụi. Do đó, tất cả chiều cao tháp \(H[i]\) và quan hệ cha \(P[i]\) đều chưa được biết. Để khám phá bí mật của nền văn minh này, các nhà khảo cổ đã phát triển một thiết bị đo độ tiện lợi — thiết bị mà người xưa dùng để lập kế hoạch bố cục thành phố.

Thiết bị này nhận đầu vào là mảng \(D[0], D[1], \ldots, D[N-1]\) và trả về mảng \(C[0], C[1], \ldots, C[N-1]\). Nó tính toán giá trị tiện lợi của các tháp bằng cách giả sử mỗi tháp \(i\) có chiều cao hiệu chỉnh \(H'[i] = H[i] + D[i]\). Với mỗi tháp \(i\), giá trị tiện lợi \(C[i]\) được định nghĩa là số tháp kề \(j\) thỏa mãn:

• \(H'[j] < H'[i]\), hoặc
• \(j = P[i]\) và \(H'[j] = H'[i]\).

Tháp \(j\) được coi là kề với tháp \(i\) nếu có một con đường nối hai tháp đó.

Chủ nhà APIO đã công bố một thách thức: nếu bạn có thể xác định tất cả chỉ số tháp cha \(P[i]\) và chiều cao tương đối \(R[i] := H[i] - H[0]\), bạn sẽ được thưởng trà sữa miễn phí cho suốt chuyến đi. Mặc dù không thể xác định chiều cao tuyệt đối, nhưng việc tìm ra các giá trị tương đối này là đủ để nhận giải thưởng.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau trong file ancient.cpp bằng cách include ancient.h:

std::pair<std::vector<int>, std::vector<int>>
find_information(int N, int S)

• \(N\): số lượng tháp trong khu phế tích.
• \(S\): chiều cao tối đa có thể của các tháp.
• Hàm này được gọi tối đa 1000 lần trong một test case.

Hàm cần trả về một cặp hai mảng \(P'\) và \(R'\), lần lượt đại diện cho chỉ số tháp cha và hiệu chiều cao tương đối, không bao gồm tháp 0.

• Cả hai mảng phải có kích thước đúng bằng \(N-1\).
• Với mỗi \(i\) thỏa \(1 \le i < N\): \(P'[i-1]\) phải bằng \(P[i]\) và \(R'[i-1]\) phải bằng \(R[i]\).

Để tương tác với thiết bị, hàm có thể gọi thủ tục sau:

std::vector<int>
detect_convenience_values(const std::vector<long long> &D)

• Mảng \(D\) phải có đúng \(N\) phần tử. Với mỗi \(i\) (\(0 \le i < N\)), \(D[i]\) phải thỏa \(-10^{18} \le D[i] \le 10^{18}\).
• Hàm trả về mảng \(N\) phần tử là các giá trị tiện lợi được tính toán.
• Hàm này được gọi tối đa 700 lần trong mỗi lần thực thi find_information.

Ràng buộc

• \(2 \le N \le 10^5\)
• Tổng \(N\) của tất cả các lần gọi find_information trong một test case không vượt quá \(10^5\).
• \(1 \le H[i] \le S \le 10^6\) với mỗi \(i\) thỏa \(0 \le i < N\).
• \(0 \le P[i] < i\) với mỗi \(i\) thỏa \(1 \le i < N\).

Phân nhóm

• Subtask 1 (2 điểm): \(N = 2\), \(S = 350\).
• Subtask 2 (3 điểm): \(N = 2\), \(S = 10^6\).
• Subtask 3 (6 điểm): \(P[i] = 0\), \(S = 10^6\).
• Subtask 4 (9 điểm): \(P[i] = i - 1\), \(S = 10^6\).
• Subtask 5 (4 điểm): \(N \le 700\), \(S = 1\).
• Subtask 6 (8 điểm): Với mỗi \(1 \le i < N\), tồn tại đường đi từ tháp \(0\) đến tháp \(i\) qua tối đa hai cạnh; \(S = 1\).
• Subtask 7 (13 điểm): \(S = 1\).
• Subtask 8 (55 điểm): \(S = 10^6\).

Ví dụ

Ví dụ 1

Xét lần gọi sau:

find_information(5, 1000000)

Các giá trị ẩn là:

P = [-1, 0, 1, 2, 3]
H = [2, 6, 7, 5, 1]

Giả sử find_information gọi detect_convenience_values([1, 0, -3, 0, 4]).

Chiều cao hiệu chỉnh \(H'\) trở thành \([3, 6, 4, 5, 5]\). Giá trị tiện lợi \(C\) được tính như sau:

• \(C[0] = 0\): Tháp kề duy nhất là tháp 1. \(H'[1] = 6\) không nhỏ hơn \(H'[0] = 3\).
• \(C[1] = 2\): Các tháp kề là 0 và 2. \(H'[0] = 3 < 6\) và \(H'[2] = 4 < 6\). Cả hai đều thấp hơn.
• \(C[2] = 0\): Các tháp kề là 1 và 3. \(H'[1] = 6\) và \(H'[3] = 5\); không cái nào nhỏ hơn hay bằng \(H'[2] = 4\).
• \(C[3] = 1\): Các tháp kề là 2 và 4. \(H'[2] = 4 < 5\) nên được đếm. Với tháp 4, \(H'[4] = 5 = H'[3]\), nhưng tháp 4 không phải cha của tháp 3 nên không được đếm.
• \(C[4] = 1\): Tháp kề duy nhất là tháp cha, tháp 3. Vì \(H'[3] = 5 = H'[4]\) và đây là tháp cha nên được đếm.

Do đó detect_convenience_values trả về \([0, 2, 0, 1, 1]\).

Nếu gọi detect_convenience_values([6, 0, 0, 0, 0]), chiều cao hiệu chỉnh là \([8, 6, 7, 5, 1]\), trả về \([1, 0, 2, 1, 0]\).

Nếu gọi detect_convenience_values([0, 1, 0, 0, 4]), chiều cao hiệu chỉnh là \([2, 7, 7, 5, 5]\), trả về \([0, 1, 2, 0, 1]\).

Cuối cùng, find_information phải trả về:

([0, 1, 2, 3], [4, 5, 3, -1])

Lưu ý: mảng trả về không chứa \(P[0]\) và \(R[0]\).

Ví dụ 2

Xét lần gọi sau:

find_information(7, 1000000)

Các giá trị ẩn là:

P = [-1, 0, 0, 1, 1, 2, 2]
H = [3, 1, 4, 1, 5, 9, 2]

Trong kịch bản này, tháp 0 là cha của 1 và 2; tháp 1 là cha của 3 và 4; tháp 2 là cha của 5 và 6.

Nếu gọi detect_convenience_values([0, 0, 0, 0, 0, 0, 0]), chiều cao hiệu chỉnh là \([3, 1, 4, 1, 5, 9, 2]\), trả về \([1, 0, 2, 1, 1, 1, 0]\).

Nếu gọi detect_convenience_values([0, 2, -1, 2, -2, -6, 1]), chiều cao hiệu chỉnh là \([3, 3, 3, 3, 3, 3, 3]\), trả về \([0, 1, 1, 1, 1, 1, 1]\).

Nếu gọi detect_convenience_values([-2, 0, 0, 0, 0, 0, 0]), chiều cao hiệu chỉnh là \([1, 1, 4, 1, 5, 9, 2]\), trả về \([0, 1, 2, 1, 1, 1, 0]\).

Cuối cùng, find_information phải trả về:

([0, 0, 1, 1, 2, 2], [-2, 1, -2, 2, 6, -1])

Chấm điểm

Ở subtask 8, điểm số phụ thuộc vào số lần gọi detect_convenience_values. Gọi \(Q\) là số lần gọi tối đa trong bất kỳ lần thực thi find_information nào trong subtask:

Nếu detect_convenience_values được gọi với đối số không hợp lệ, hoặc find_information trả về đáp án sai, điểm subtask đó sẽ là \(0\).