#include "migrations.h"
#include <vector>
#include <algorithm>
using namespace std;
const int N_MAX = 10000;
const int LOG = 14; // 2^14 = 16384 > 10000
static vector<vector<int>> up(LOG, vector<int>(N_MAX, -1));
static vector<int> depth(N_MAX, 0);
static int A = 0, B = 0; // current diameter endpoints
static int msg_sent = 0; // number of messages sent so far (not needed)
const int KEEP_A = 1, KEEP_B = 2; // codes for update
int send_message(int N, int i, int Pi) {
// add node i with parent Pi
up[0][i] = Pi;
depth[i] = depth[Pi] + 1;
for (int k = 1; k < LOG; ++k) {
int mid = up[k-1][i];
up[k][i] = (mid == -1) ? -1 : up[k-1][mid];
}
// compute distances to current endpoints
auto dist = [&](int u, int v) -> int {
if (u == v) return 0;
int du = depth[u], dv = depth[v];
// lift deeper node
if (du < dv) {
for (int k = LOG-1; k >= 0; --k)
if (dv - (1<<k) >= du && up[k][v] != -1)
v = up[k][v];
swap(u, v);
} else if (du > dv) {
for (int k = LOG-1; k >= 0; --k)
if (du - (1<<k) >= dv && up[k][u] != -1)
u = up[k][u];
}
// now same depth
for (int k = LOG-1; k >= 0; --k)
if (up[k][u] != -1 && up[k][u] != -1 && up[k][u] == up[k][v])
u = up[k][u], v = up[k][v];
if (u == v) return depth[i] + depth[i]; // actually distance is du + dv - 2*depth[lca]
return depth[i] + depth[i] - 2*depth[u];
};
// But we only need distances from i to A and B, and from A to B.
// We can recompute quickly:
auto lca = [&](int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
for (int k = LOG-1; k >= 0; --k)
if (depth[u] - (1<<k) >= depth[v] && up[k][u] != -1)
u = up[k][u];
if (u == v) return u;
for (int k = LOG-1; k >= 0; --k)
if (up[k][u] != -1 && up[k][u] != up[k][v])
u = up[k][u], v = up[k][v];
return up[0][u];
};
int dA = depth[i] + depth[A] - 2*depth[lca(i, A)];
int dB = depth[i] + depth[B] - 2*depth[lca(i, B)];
int oldDiam = depth[A] + depth[B] - 2*depth[lca(A, B)];
// Determine if diameter increases and which endpoint stays
int code = 0; // no change
if (max(dA, dB) > oldDiam) {
if (dA >= dB) {
code = KEEP_A; // B becomes i
} else {
code = KEEP_B; // A becomes i
}
}
// Decision for messages: we will use the last 50 nodes.
const int START = N - 50; // 9950 for N=10000
int msg = 0;
if (i >= START) {
if (i == START) {
// send A before any changes in this segment
msg = A;
} else if (i == START+1) {
// send B before any changes in this segment
msg = B;
} else {
// send the code for this node
msg = code; // 0,1,2
}
}
// Apply the update to (A,B) if code != 0
if (code == KEEP_A) {
B = i;
} else if (code == KEEP_B) {
A = i;
}
// else keep unchanged
return msg;
}
pair<int, int> longest_path(vector<int> S) {
int N = S.size();
const int START = N - 50;
int A = S[START];
int B = S[START+1];
// process the remaining nodes
for (int i = START+2; i < N; ++i) {
int code = S[i];
if (code == 0) {
// no change, nothing to do
} else if (code == 1) {
B = i;
} else { // code == 2
A = i;
}
}
return {A, B};
}
