Submission #1276455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276455		seannaren	Migrations (IOI25_migrations)	C++17	20 / 100	35 ms	912 KiB

migrations

#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;
}
/*  ----------  Museum routine  ---------- */
std::pair<int,int> longest_path(std::vector<int> S) {
    int N = (int)S.size();          // S[0] is always 0, length equals N
    if (N <= 2) return {0, N - 1}; // trivial cases

    int a = S[N - 2] - 1;           // endpoint transmitted from site N-2
    int v = S[N - 1];
    int leaf = N - 1;

    if (v <= N) {                  // unchanged case
        int b = v - 1;
        return {a, b};
    }
    if (v == 20000) {              // leaf + a case
        return {a, leaf};
    }
    // leaf + b case: v = b + N + 1
    int b = v - (N + 1);
    return {b, leaf};
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 30
• Subtask 2: 10 / 70