#include <vector>
#include <utility>
static const int MAX_VAL = 20000;
// These globals are shared across all calls of send_message
static int gN = -1; // size of the current test case
static std::vector<int> depth; // depth[i] = distance from site 0
static int farthest = 0; // index of the deepest node seen so far
int send_message(int N, int i, int Pi) {
// Initialise or re-initialise for a new test case
if (gN != N) {
gN = N;
depth.assign(N, 0); // depth[0] = 0, others will be filled later
farthest = 0;
}
// Compute depth of the current node
int d = depth[Pi] + 1;
depth[i] = d;
// Update the deepest node seen so far
if (d > depth[farthest]) {
farthest = i;
}
// Send a single message only when we are at the last site
if (i == N - 1) {
int V = farthest; // the farthest node from site 0
int i_msg = N - 1; // index of the message
int Y = (i_msg - V) % MAX_VAL; // Y may be negative in C++
if (Y < 0) Y += MAX_VAL; // make Y in [0, 19999]
int X = Y + 1; // ensure 1 <= X <= 20000
return X;
} else {
return 0; // no message
}
}
std::pair<int, int> longest_path(std::vector<int> S) {
int i_msg = -1;
int X = 0;
for (int idx = 0; idx < (int)S.size(); ++idx) {
if (S[idx] != 0) {
i_msg = idx;
X = S[idx];
}
}
// If there is no message (should not happen for N > 1), fall back to (0, 0)
if (i_msg == -1) {
return {0, 0};
}
int Y = X - 1; // recover Y = (i_msg - V) mod 20000
int V = (i_msg - Y) % MAX_VAL; // decode V = index of farthest node
if (V < 0) V += MAX_VAL;
int N = (int)S.size();
// Guard against any accidental overflow
if (V >= N) {
V %= N;
}
// The diameter pair is (0, V) because site 0 is guaranteed to be an endpoint.
return {0, V};
}
