Submission #1276458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276458		mehrzad	Migrations (IOI25_migrations)	C++17	22.09 / 100	42 ms	912 KiB

migrations

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

static const int LOG = 15;                // 2^14 = 16384 > 10000

/* ------------------------------------------------------------------ */
/*  Team side: send_message                                          */
/* ------------------------------------------------------------------ */
int send_message(int N, int i, int Pi) {
    // static data that survives across calls of the same test case
    static bool initialized = false;
    static int Nglob = -1;
    static vector<int> depth;
    static vector<array<int, LOG>> up;
    static int cur_u, cur_v, cur_d;        // current diameter ends and length
    static bool vChangedAtNminus2;         // true iff cur_v became N-2 at step N-2

    // first call for a test case (i == 1) -> initialise everything
    if (!initialized || i == 1) {
        initialized = true;
        Nglob = N;
        depth.assign(N, 0);
        up.assign(N, {});
        for (int k = 0; k < LOG; ++k) up[0][k] = 0;   // ancestors of root are root
        cur_u = cur_v = 0;
        cur_d = 0;
        vChangedAtNminus2 = false;
    }

    /* ---- add node i to the tree ----------------------------------- */
    depth[i] = depth[Pi] + 1;
    up[i][0] = Pi;
    for (int k = 1; k < LOG; ++k) {
        int anc = up[i][k - 1];
        up[i][k] = up[anc][k - 1];
    }

    // helper: LCA using binary lifting
    auto lca = [&](int a, int b) -> int {
        if (depth[a] < depth[b]) swap(a, b);
        int diff = depth[a] - depth[b];
        for (int k = LOG - 1; k >= 0; --k)
            if (diff & (1 << k)) a = up[a][k];
        if (a == b) return a;
        for (int k = LOG - 1; k >= 0; --k) {
            if (up[a][k] != up[b][k]) {
                a = up[a][k];
                b = up[b][k];
            }
        }
        return up[a][0];
    };
    auto dist = [&](int a, int b) -> int {
        int w = lca(a, b);
        return depth[a] + depth[b] - 2 * depth[w];
    };

    // update the diameter
    int du = dist(i, cur_u);
    int dv = dist(i, cur_v);
    if (du > cur_d) {
        cur_v = i;
        cur_d = du;
    } else if (dv > cur_d) {
        cur_u = i;
        cur_d = dv;
    }

    /* ---- decide what to send ------------------------------------- */
    // tiny instances
    if (N <= 3) {
        if (i == N - 1) {
            // encode the final pair (cur_u,cur_v) into a small integer
            int code = cur_u * N + cur_v + 1;   // 1 … N*N (≤ 9 for N=3)
            return code;
        }
        return 0;
    }

    // N >= 4
    if (i == Nglob - 3) {
        // store the current cur_v (after processing i = N-3)
        return cur_v + 1;
    }
    if (i == Nglob - 2) {
        // remember whether cur_v became the new leaf N-2
        vChangedAtNminus2 = (cur_v == i);
        // store cur_u after processing i = N-2
        return cur_u + 1;
    }
    if (i == Nglob - 1) {
        int c1 = 0;                 // change type at the last step
        if (cur_u == i) c1 = 2;
        else if (cur_v == i) c1 = 1;
        else c1 = 0;
        int c2 = vChangedAtNminus2 ? 1 : 0;
        int flag = 1 + c1 + 3 * c2; // value between 1 and 6
        return flag;
    }
    return 0;                       // no message
}

/* ------------------------------------------------------------------ */
/*  Museum side: longest_path                                        */
/* ------------------------------------------------------------------ */
std::pair<int, int> longest_path(std::vector<int> S) {
    int N = (int)S.size();

    if (N == 1) return {0, 0};
    if (N == 2) return {0, 1};

    if (N == 3) {
        // the only non‑zero entry is S[2]
        int code = S[2];
        int x = code - 1;
        int u = x / N;
        int v = x % N;
        return {u, v};
    }

    // N >= 4
    int u_saved = S[N - 2] - 1;   // cur_u after step N-2
    int v_saved = S[N - 3] - 1;   // cur_v after step N-3 (may be outdated)
    int flag = S[N - 1] - 1;      // 0 … 5

    int c1 = flag % 3;            // 0 unchanged, 1 cur_v → N-1, 2 cur_u → N-1
    int c2 = flag / 3;            // 0 cur_v not N-2, 1 cur_v = N-2 after N-2

    int other = (c2 == 1) ? (N - 2) : v_saved;

    if (c1 == 0) {
        return {u_saved, other};
    } else if (c1 == 1) {
        return {u_saved, N - 1};
    } else { // c1 == 2
        return {other, N - 1};
    }
}

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