#include "migrations.h"
#include <vector>
#include <utility>
// ------- Persistent state across send_message calls within the first run -------
namespace {
static int depth_arr[10005];
static int bestV = 0;
static int bestD = 0;
static bool initialized = false;
}
// Research team procedure
int send_message(int N, int i, int Pi) {
if (!initialized) {
initialized = true;
depth_arr[0] = 0;
bestV = 0;
bestD = 0;
}
// Compute depth of current node i (since P[i] < i, depth[Pi] is already known)
depth_arr[i] = depth_arr[Pi] + 1;
// Track deepest node from root (site 0)
if (depth_arr[i] > bestD) {
bestD = depth_arr[i];
bestV = i;
}
// Send exactly one message at the last site: encode bestV as bestV+1
if (i == N - 1) {
return bestV + 1; // in [1..N] ≤ 10000 ≤ 20000
}
return 0;
}
// Museum procedure
std::pair<int,int> longest_path(std::vector<int> S) {
int N = (int)S.size();
int last_nonzero_idx = -1;
for (int i = 1; i < N; ++i) if (S[i] != 0) last_nonzero_idx = i;
if (last_nonzero_idx == -1) {
// Fallback (no message found)
return {0, 0};
}
int code = S[last_nonzero_idx]; // expected: bestV+1
int v = code - 1;
return {0, v};
}
