Submission #1275583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275583		mehrzad	Migrations (IOI25_migrations)	C++17	0 / 100	30 ms	1168 KiB

migrations

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

/*
Robust, low-chatter, unambiguous protocol.

—we maintain the current diameter (A,B) online with LCA.
—we only transmit in the last K=50 insertions: startIdx = max(1, N-K).
—on a REAL diameter change at i, we send EVEN = (other_endpoint + 1) forced even.
—otherwise (no change), we send exactly TWO ODD inits once in the suffix:
     1) (A + 1) forced odd
     2) (B + 1) forced odd (skipped if a change happens before sending it)

Museum decoding:
—if any EVEN message exists, take the LAST EVEN → (U = that i, V = value-1).
—else take the LAST TWO ODD messages → (U = odd1-1, V = odd2-1).

Key fix vs. previous attempts: LCA lifting loops are BOUNDED by LOGv.
*/

namespace {
    // per-test state
    bool inited = false;
    int Nglob = 0, LOGv = 0;
    int K = 50, startIdx = 1;

    vector<int> depth;
    vector<vector<int>> up; // up[v][k], k in [0..LOGv-1]

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

    bool sentInit1 = false, sentInit2Pending = false;
    int init2Val = 0;

    inline void reset_test(int N){
        inited = true;
        Nglob = N;
        LOGv = 0; while ((1 << LOGv) <= max(1, Nglob)) ++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;
        K = min(50, max(1, Nglob - 1));
        startIdx = max(1, Nglob - K);

        sentInit1 = false;
        sentInit2Pending = false;
        init2Val = 0;
    }

    inline int lca(int u, int v){
        if (depth[u] < depth[v]) swap(u, v);
        int diff = depth[u] - depth[v];
        // lift u by bounded bits of diff
        for (int k = 0; k < LOGv; ++k){
            if (diff & (1 << k)) u = up[u][k];
        }
        if (u == v) return u;
        // jump both up
        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];
    }

    inline int force_even(int x){ return (x & 1) ? x + 1 : x; }
    inline int force_odd (int x){ return (x & 1) ? x     : x + 1; }
}

int send_message(int N, int i, int Pi){
    // Reinit per test when i==1 (new test case)
    if (!inited || i == 1) reset_test(N);

    // Fill lifting info for node i
    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);
    int 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 (changed){
            // Real change → EVEN-coded other+1
            int v = other + 1;          // 1..N ≤ 10000
            v = force_even(v);          // make it even to mark "change"
            // v ≤ 10000, so ≤ 20000 bound always satisfied
            out = v;
            // once a real change occurs, we skip pending init2
            sentInit2Pending = false;
        } else if (!sentInit1){
            // First init → ODD-coded A+1
            int v = force_odd(A + 1);
            out = v;
            sentInit1 = true;
            sentInit2Pending = true;
            init2Val = force_odd(B + 1);
        } else if (sentInit2Pending){
            // Second init → ODD-coded B+1
            out = init2Val;
            sentInit2Pending = false;
        }
        // else: stay silent
    }
    return out; // 0 = no message
}

std::pair<int,int> longest_path(std::vector<int> S){
    // Collect nonzero messages
    vector<pair<int,int>> msgs;
    msgs.reserve(S.size());
    for (int i = 0; i < (int)S.size(); ++i)
        if (S[i] != 0) msgs.emplace_back(i, S[i]);

    if (msgs.empty()) return {0, 0}; // degenerate tiny trees

    // Prefer the last EVEN message → final real change
    for (int t = (int)msgs.size() - 1; t >= 0; --t){
        if ((msgs[t].second & 1) == 0){
            int idx = msgs[t].first;
            int v = msgs[t].second - 1; // decode other endpoint
            return { idx, v };
        }
    }
    // Otherwise, use the last two ODD messages (the two init endpoints)
    int found = 0;
    int v_last = -1, v_prev = -1;
    for (int t = (int)msgs.size() - 1; t >= 0 && found < 2; --t){
        if ((msgs[t].second & 1) == 1){
            if (found == 0) v_last = msgs[t].second - 1;
            else            v_prev = msgs[t].second - 1;
            ++found;
        }
    }
    if (found == 2) return { v_prev, v_last };

    // Fallback: single odd message — interpret as (idx, val-1)
    auto [idx, val] = msgs.back();
    return { idx, val - 1 };
}

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