Submission #1274331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274331		mehrzad	Migrations (IOI25_migrations)	C++17	20 / 100	36 ms	912 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;

/*  -------  Global data for the first run  ------- */
static int Nglob = -1;                 // number of sites
static int LOG = 0;                    // log2(N)
static vector<int> depth;              // depth of each node
static vector<array<int,15>> up;       // binary lifting table (LOG ≤ 15 for N≤10000)

static int a_node = 0, b_node = 0;     // current diameter ends
static int diam_len = 0;               // current diameter length

static int start_idx = 0;              // first index from which we start sending messages
static bool dummy_a_sent = false;      // have we already sent the dummy for 'a' ?
static bool dummy_b_sent = false;      // have we already sent the dummy for 'b' ?

/*  -------  Helper functions  ------- */
static inline int encode(int nodeIdx, int side) {
    // side = 1 (a) or 2 (b)
    // value is always in [1,20000] because nodeIdx ≤ 9999
    return nodeIdx * 2 + side;
}
static inline int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v];
    for (int k = LOG - 1; k >= 0; --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] != -1 && up[u][k] != up[v][k]) {
            u = up[u][k];
            v = up[v][k];
        }
    }
    return up[u][0];
}
static inline int dist(int u, int v) {
    int w = lca(u, v);
    return depth[u] + depth[v] - 2 * depth[w];
}

/*  -------  The team procedure  ------- */
int send_message(int N, int i, int Pi) {
    // first call: initialise everything
    if (Nglob == -1) {
        Nglob = N;
        LOG = 0;
        while ((1 << LOG) <= N) ++LOG;          // LOG ≤ 15 for N = 10000
        depth.assign(N, 0);
        up.assign(N, array<int,15>{});
        for (int k = 0; k < LOG; ++k) up[0][k] = -1;
        a_node = b_node = 0;
        diam_len = 0;
        dummy_a_sent = dummy_b_sent = false;
        start_idx = max(1, N - 50);              // we have at most 50 nodes at the end
    }

    /* store parent and fill binary lifting table */
    up[i][0] = Pi;
    depth[i] = depth[Pi] + 1;
    for (int k = 1; k < LOG; ++k) {
        int p = up[i][k - 1];
        up[i][k] = (p == -1) ? -1 : up[p][k - 1];
    }

    /* update the current diameter */
    int side = 0;               // 0 = no change, 1 = a becomes i, 2 = b becomes i
    int new_diam = diam_len;
    int da = dist(i, a_node);
    int db = dist(i, b_node);
    if (da > new_diam) {
        new_diam = da;
        side = 2;               // b becomes i
    } else if (db > new_diam) {
        new_diam = db;
        side = 1;               // a becomes i
    }
    if (side == 1) a_node = i;
    else if (side == 2) b_node = i;
    diam_len = new_diam;

    /* decide what to send */
    if (i < start_idx) return 0;          // we send nothing before the tail

    int msg = 0;

    if (i == start_idx) {
        // first node of the tail: dummy message that tells the current value of a
        msg = encode(a_node, 1);
        dummy_a_sent = true;
        // we deliberately ignore a possible side update here; a will be reported later if it changes again
    } else {
        if (!dummy_b_sent) {
            if (side == 0) {
                // we have a quiet step – perfect moment to emit dummy for b
                msg = encode(b_node, 2);
                dummy_b_sent = true;
            } else if (i == Nglob - 2) {
                // we are at the second‑last node and still have not emitted b.
                // Sacrifice this node to send dummy b; a will still be updated later (at the last node)
                msg = encode(b_node, 2);
                dummy_b_sent = true;
                // side update for a is ignored here.
            } else {
                // normal side update
                msg = encode(i, side);
                if (side == 1) dummy_a_sent = true;
                else dummy_b_sent = true;   // side == 2, we have now seen b change
            }
        } else {
            // dummy for b already sent – just report side updates
            if (side != 0) {
                msg = encode(i, side);
                if (side == 1) dummy_a_sent = true;
                else dummy_b_sent = true;
            } else {
                msg = 0;
            }
        }
    }
    return msg;
}

/*  -------  The museum procedure  ------- */
std::pair<int,int> longest_path(std::vector<int> S) {
    int a = 0, b = 0;
    for (size_t i = 1; i < S.size(); ++i) {
        int v = S[i];
        if (v == 0) continue;
        int side = (v % 2 == 0) ? 2 : 1;               // even → side 2 (b), odd → side 1 (a)
        int node = (v - side) / 2;
        if (side == 1) a = node;
        else b = node;
    }
    return {a, b};
}

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