Submission #1275589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275589		mehrzad	Migrations (IOI25_migrations)	C++17	28.09 / 100	31 ms	1168 KiB

migrations

#include "migrations.h"
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

// Toggle this to try for higher score without sacrificing correctness.
// false  => Stable baseline (~28), always correct.
// true   => Hybrid: usually Z<=4 (~50+), but falls back to big value on very-late change (still correct).
static constexpr bool AGGRESSIVE = false;

/* ===================== Shared online tree + diameter ===================== */

namespace {
    bool inited = false;
    int Nglob = 0, LOGv = 0;

    // LCA tables
    vector<int> depth;
    vector< vector<int> > up;  // up[v][k]

    // Online diameter
    int A = 0, B = 0, D = 0;   // endpoints and length

    inline void reset_test(int N) {
        inited = true;
        Nglob = N;
        LOGv = 0; while ((1 << LOGv) <= (Nglob > 0 ? Nglob : 1)) ++LOGv;
        depth.assign(Nglob, 0);
        up.assign(Nglob, vector<int>(LOGv, 0));
        for (int k = 0; k < LOGv; ++k) up[0][k] = 0;
        A = B = 0; D = 0;
    }

    inline int lca(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        int diff = depth[u] - depth[v];
        for (int k = 0; k < LOGv; ++k) if (diff & (1 << k)) u = up[u][k];
        if (u == v) return u;
        for (int k = LOGv - 1; k >= 0; --k) {
            if (up[u][k] != up[v][k]) {
                u = up[u][k];
                v = up[v][k];
            }
        }
        return up[u][0];
    }
    inline int dist(int u, int v) {
        int w = lca(u, v);
        return depth[u] + depth[v] - 2 * depth[w];
    }
}

/* ===================== Mode A: Stable baseline (Z~N, ~28 pts) ===================== */

namespace stable_mode {
    // Talk window (smaller window slightly reduces M without changing Z)
    static constexpr int K = 32; // safe tweak; set to 50 if you prefer

    // Suffix bookkeeping
    int startIdx = 1;
    bool sentInitA = false, sentInitB = false;

    inline void begin_case(int N){
        reset_test(N);
        int Kuse = (Nglob >= 2 ? K : max(1, Nglob - 1));
        startIdx = max(1, Nglob - Kuse);
        sentInitA = sentInitB = false;
    }

    inline int send_msg(int i, int Pi){
        // Build lifting
        depth[i] = depth[Pi] + 1;
        up[i][0] = Pi;
        for (int k = 1; k < LOGv; ++k) up[i][k] = up[ up[i][k-1] ][k-1];

        // Online diameter update
        int dA = dist(i, A), dB = dist(i, B);
        bool changed = false; int other = -1;
        if (dA > D) { changed = true; other = A; B = i; D = dA; }
        else if (dB > D) { changed = true; other = B; A = i; D = dB; }

        int out = 0;
        if (i >= startIdx) {
            if (i == startIdx && !sentInitA) {
                out = A + 1; sentInitA = true;
            } else if (i == startIdx + 1 && !sentInitB) {
                out = B + 1; sentInitB = true;
            } else if (changed) {
                out = other + 1;
            }
        }
        return out; // 0 or 1..10000
    }

    inline pair<int,int> decode(const vector<int>& S){
        int N = (int)S.size();
        int Kuse = (N >= 2 ? K : max(1, N - 1));
        int start = max(1, N - Kuse);
        // Prefer any message strictly after the two inits (true change)
        for (int i = N - 1; i >= start + 2; --i) {
            if (S[i] != 0) return { i, S[i] - 1 };
        }
        // Else use the two deterministic inits
        int u = (S[start]     > 0 ? S[start]     - 1 : 0);
        int v = (S[start + 1] > 0 ? S[start + 1] - 1 : 0);
        return { u, v };
    }
}

/* ===================== Mode B: Hybrid (usually Z<=4; fallback for correctness) ===================== */

namespace hybrid_mode {
    // Use a larger tail window so we almost always finish the 14 digits
    static constexpr int W = 50;
    int tailStart = 1;

    // Streaming state
    int stream_pos = -1;   // 0..13 for 14 base-4 digits
    bool have_reset = false;
    int lastA = 0, lastB = 0;

    inline int get_digit_base4(int x, int d){ // d-th digit, LSB-first
        return (x >> (2*d)) & 3; // 2 bits per base-4 digit
    }

    inline void begin_case(int N){
        reset_test(N);
        tailStart = max(1, Nglob - W);
        stream_pos = -1; have_reset = false;
        lastA = lastB = 0;
    }

    inline int send_msg(int i, int Pi){
        // Build lifting
        depth[i] = depth[Pi] + 1;
        up[i][0] = Pi;
        for (int k = 1; k < LOGv; ++k) up[i][k] = up[ up[i][k-1] ][k-1];

        // Online diameter update
        int dA = dist(i, A), dB = dist(i, B);
        bool changed = false; int other = -1;
        if (dA > D) { changed = true; other = A; B = i; D = dA; }
        else if (dB > D) { changed = true; other = B; A = i; D = dB; }

        int out = 0;
        if (i >= tailStart){
            if (!have_reset){
                // Emit a RESET (0) once at the start of the window
                out = 0;
                have_reset = true;
                stream_pos = 0;
                lastA = A; lastB = B;
                return out;
            }
            if (changed){
                int slots_left = (Nglob - 1) - i; // how many indices remain after i
                if (slots_left >= 14){
                    // Reset and restart streaming the new final endpoints
                    out = 0; stream_pos = 0; lastA = A; lastB = B;
                    return out;
                } else {
                    // Too late to complete → fallback once (correctness over score)
                    // Encode 'other+1' as a big number (≤ 20000)
                    return 10000 + (other + 1);
                }
            }
            // No change → stream digits for (A,B), interleaved, base-4 (map 0..3 -> 1..4)
            if (stream_pos < 14){
                int which = stream_pos++;
                int digit = (which & 1)
                    ? get_digit_base4(B, which/2)
                    : get_digit_base4(A, which/2);
                out = digit + 1; // 1..4
            } else {
                out = 1; // optional padding; keeps Z ≤ 4 if no fallback
            }
        }
        return out; // 0..20000
    }

    inline pair<int,int> decode(const vector<int>& S){
        int N = (int)S.size();
        int tail = max(1, N - W);

        // If any fallback (>4) exists, the last such gives (i, other)
        for (int i = N - 1; i >= tail; --i){
            if (S[i] > 4){
                int other = S[i] - 10000 - 1;
                if (other < 0) other = 0;
                if (other >= N) other = N - 1;
                return { i, other };
            }
        }
        // Otherwise, decode base-4 digits after the last RESET (0)
        int lastReset = -1;
        for (int i = N - 1; i >= tail; --i) if (S[i] == 0){ lastReset = i; break; }
        if (lastReset == -1) return {0, 0}; // extremely unlikely fallback

        vector<int> digs;
        for (int i = lastReset + 1; i < N; ++i){
            if (S[i] >= 1 && S[i] <= 4) digs.push_back(S[i] - 1);
        }
        // Take the last 14 digits (pad with zeros if not enough)
        if ((int)digs.size() < 14) digs.insert(digs.begin(), 14 - (int)digs.size(), 0);
        else digs.erase(digs.begin(), digs.end() - 14);

        int U = 0, V = 0;
        for (int pos = 0; pos < 14; ++pos){
            int d = digs[pos] & 3;
            if ((pos & 1) == 0){ U |= (d << (2 * (pos/2))); }
            else               { V |= (d << (2 * (pos/2))); }
        }
        if (U >= N) U = N - 1;
        if (V >= N) V = N - 1;
        return {U, V};
    }
}

/* ===================== Public API ===================== */

int send_message(int N, int i, int Pi) {
    if (!inited || i == 1) {
        if (AGGRESSIVE) hybrid_mode::begin_case(N);
        else            stable_mode::begin_case(N);
    }
    return AGGRESSIVE ? hybrid_mode::send_msg(i, Pi)
                      : stable_mode::send_msg(i, Pi);
}

std::pair<int,int> longest_path(std::vector<int> S) {
    return AGGRESSIVE ? hybrid_mode::decode(S)
                      : stable_mode::decode(S);
}

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