| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1276453 | seannaren | Migrations (IOI25_migrations) | C++17 | 0 ms | 0 KiB |
#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
/* ---------- Global data for the research team ---------- */
static const int MAX_LOG = 15; // 2^14 = 16384 > 10000
static bool init = false; // first call flag
static int N_glob; // current N
static int LOG; // log value (fixed to MAX_LOG)
static vector<int> depth; // depth of each node
static vector<array<int,MAX_LOG>> up; // binary lifting table
static int a_end, b_end, diam_len; // current diameter ends and length
static int a_old, b_old; // diameter ends after node N-2
static bool old_saved = false; // true after processing N-2
/* ---------- Helper functions (LCA, distance) ---------- */
static int lca_func(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for (int k = 0; k < LOG; ++k)
if (diff & (1 << k)) u = up[u][k];
if (u == v) return u;
for (int k = LOG - 1; k >= 0; --k) {
if (up[u][k] != up[v][k]) {
u = up[u][k];
v = up[v][k];
}
}
return up[u][0];
}
static int dist_func(int u, int v) {
int w = lca_func(u, v);
return depth[u] + depth[v] - 2 * depth[w];
}
/* ---------- Research team routine ---------- */
int send_message(int N, int i, int Pi) {
// Extremely small cases – no need to communicate anything.
if (N <= 2) return 0;
// (Re)initialise when a new test case starts.
if (!init || N != N_glob) {
N_glob = N;
LOG = MAX_LOG;
depth.assign(N_glob, 0);
up.assign(N_glob, array<int,MAX_LOG>());
for (int k = 0; k < LOG; ++k) up[0][k] = -1;
a_end = b_end = 0;
diam_len = 0;
old_saved = false;
init = true;
}
// store parent, depth and binary lifting ancestors
depth[i] = depth[Pi] + 1;
up[i][0] = Pi;
for (int k = 1; k < LOG; ++k) {
int prev = up[i][k-1];
up[i][k] = (prev == -1 ? -1 : up[prev][k-1]);
}
// -----------------------------------------------------------------
// Update the current tree diameter with the new leaf i.
// -----------------------------------------------------------------
int d_to_a = dist_func(i, a_end);
int d_to_b = dist_func(i, b_end);
if (d_to_a > diam_len) {
b_end = a_end;
a_end = i;
diam_len = d_to_a;
} else if (d_to_b > diam_len) {
a_end = i;
diam_len = d_to_b;
}
// After processing node N-2 we remember the current endpoints.
if (i == N_glob - 2) {
a_old = a_end;
b_old = b_end;
old_saved = true;
// Send one endpoint (a_old) as a message.
return a_old + 1; // 1 … N
}
// At the very last node (N-1) we encode the final answer.
if (i == N_glob - 1) {
int leaf = i;
bool leaf_is_endpoint = (a_end == leaf) || (b_end == leaf);
if (!leaf_is_endpoint) {
// Diameter unchanged: send the other old endpoint (b_old).
return b_old + 1;
} else {
// Leaf belongs to the final diameter.
int other = (a_end == leaf) ? b_end : a_end; // the other endpoint
if (other == a_old) {
// leaf + a_old case – use the special constant 20000.
return 20000;
} else {
// leaf + b_old case – encode as other + N + 1.
int val = other + N_glob + 1; // ≤ 2·N ≤ 20000
if (val > 20000) val = 20000; // safety
return val;
}
}
}
// All other sites send nothing.
return 0;
}