#include <vector>
#include <utility>
// Global state kept between successive calls of send_message
static std::vector<int> _depth;
static int _maxDepth = 0;
static int _farthest = 0;
static int _suffix_start = 0;
static int _N = 0;
static bool _initialized = false;
int send_message(int N, int i, int Pi) {
// first call – initialise the global structures
if (!_initialized) {
_N = N;
_depth.assign(N, 0); // depth[0] = 0
_maxDepth = 0;
_farthest = 0;
// we need 14 bits for any index 0..9999
_suffix_start = N - 14;
if (_suffix_start < 0) { // N is always 10000, but be safe
_suffix_start = 0;
}
_initialized = true;
}
// depth of the current site
int d = _depth[Pi] + 1;
_depth[i] = d;
// does this site become the new deepest one ?
if (d > _maxDepth) {
_maxDepth = d;
_farthest = i;
}
// -----------------------------------------------------------------
// decide what to send
if (i < _suffix_start) {
// still before the reserved suffix – nothing can be sent yet
return 0;
}
// we are inside the suffix
if (_farthest >= _suffix_start) {
// the farthest site lies inside the suffix → use a marker
if (i == _farthest) {
return 2; // marker
} else {
return 0;
}
} else {
// farthest site is before the suffix → encode its bits
int bit_index = i - _suffix_start; // 0 … 13 (least significant first)
if ((_farthest >> bit_index) & 1) {
return 1; // bit = 1
} else {
return 0; // bit = 0
}
}
}
std::pair<int, int> longest_path(std::vector<int> S) {
int N = static_cast<int>(S.size());
int suffix_start = N - 14;
if (suffix_start < 0) {
suffix_start = 0;
}
// -------------------------------------------------------------
// 1) look for the rightmost marker (value 2)
int marker = -1;
for (int idx = N - 1; idx >= 0; --idx) {
if (S[idx] == 2) {
marker = idx;
break;
}
}
if (marker != -1) {
// marker case – the farthest site is exactly this index
return {0, marker};
}
// -------------------------------------------------------------
// 2) no marker → the farthest site is before the suffix,
// reconstruct it from the 14 bits stored there
int far = 0;
for (int b = 0; b < 14; ++b) {
int pos = suffix_start + b;
if (pos < N && S[pos] == 1) {
far |= (1 << b);
}
}
return {0, far};
}
