#include <vector>
#include <utility>
#include <algorithm>
// ------------------------------------------------------------
// Dinosaur migration – optimal communication (Z <= 4, M <= 18)
// ------------------------------------------------------------
// constants
const int BASE = 3; // we encode in base 3, digits 0,1,2
const int MAX_L = 9; // 3**9 = 19683 > 10000
// ------------------------------------------------------------
// global state (kept alive between the N-1 calls of send_message)
// ------------------------------------------------------------
int _cur_N = -1; // current N, to detect a new test case
std::vector<int> _depth; // depth[i] for the current tree
int _max_depth = -1;
int _deepest_node = 0; // deepest leaf seen so far
int _L = 0; // actual block length (min(MAX_L, N-1))
int _block_start = 0; // first index of the block = N - _L
std::vector<int> _digits; // list of L base-3 digits (used only in encode mode)
bool _encode_started = false; // have we already computed the digits ?
// ------------------------------------------------------------
int send_message(int N, int i, int Pi) {
// ---- initialise for a new test case ---------------------------------
if (_cur_N != N) {
_cur_N = N;
_depth.assign(N, 0); // depth[0] stays 0
_max_depth = 0;
_deepest_node = 0;
_L = std::min(MAX_L, N - 1); // length of the block, never zero for N>=2
_block_start = N - _L;
_digits.clear();
_encode_started = false;
}
// ---- compute depth of the current node -------------------------------
_depth[i] = _depth[Pi] + 1;
// ---- update deepest leaf --------------------------------------------
if (_depth[i] > _max_depth) {
_max_depth = _depth[i];
_deepest_node = i;
}
// ---- before the block: never send a message -------------------------
if (i < _block_start) {
return 0;
}
// ---- we are inside the last _L nodes --------------------------------
if (_deepest_node >= _block_start) {
// deepest leaf is inside the block -> sentinel mode
if (i == _deepest_node) { // only the deepest leaf sends the sentinel
return 1;
}
return 0;
} else {
// deepest leaf is before the block -> encode mode
if (!_encode_started) {
// compute base-3 digits of the deepest leaf (fixed L digits)
int D = _deepest_node;
_digits.assign(_L, 0);
for (int pos = 0; pos < _L; ++pos) {
_digits[pos] = D % BASE;
D /= BASE;
}
_encode_started = true;
}
// send the corresponding digit (0..2) encoded as 2..4
int idx = i - _block_start; // 0 .. L-1
int digit = _digits[idx]; // 0,1,2
return digit + 2; // 2,3,4
}
}
// ------------------------------------------------------------
std::pair<int, int> longest_path(std::vector<int> S) {
int N = S.size();
int L = std::min(MAX_L, N - 1); // same block length as in send_message
int block_start = N - L;
// --- if a sentinel (value 1) exists, the last one is the deepest leaf ---
for (int i = N - 1; i >= 0; --i) {
if (S[i] == 1) {
return {0, i};
}
}
// --- otherwise the block contains the base-3 digits ----------------------
int D = 0;
int power = 1;
for (int j = 0; j < L; ++j) {
int val = S[block_start + j]; // expected 0,2,3,4
int digit = (val != 0) ? (val - 2) : 0; // 0,1,2
D += digit * power;
power *= BASE;
}
return {0, D};
}
