Submission #1275581

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

migrations

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

/*
Unambiguous low-Z protocol (Z ≤ 3):

Tail-window streaming (W = 24):
- At i == N-W: send 0  (RESET marker; inside the tail window only)
- For i in (N-W+1) .. (N-1):
    * Maintain online diameter endpoints (A,B) via LCA.
    * If (A,B) changed since last emitted symbol -> send 0 (RESET) and restart stream.
    * Else emit base-3 digits (mapped as out = digit+1 in {1,2,3}) interleaved LSB-first:
          u0, v0, u1, v1, ..., u8, v8   (18 digits total; 9 per index as 3^9 >= 10000)
      After 18 digits are sent, emit padding value '1' (digit 0) for the rest of the window.
- Outside the window: always return 0 (no message).
Museum:
- In the last W positions, find the LAST 0 (reset). Then read the FIRST 18 nonzero symbols
  after it, map to digits (value-1), and reconstruct U, V from interleaved base-3 LSB-first.
*/

namespace {
    // per-test state
    bool inited = false;
    int Nglob = 0, LOGv = 0;
    const int W = 24;                    // tail window size: 1 reset + 18 digits + slack
    int tailStart = 1;

    // tree lifting
    vector<int> depth;
    vector<vector<int>> up;

    // diameter tracking
    int A = 0, B = 0, D = 0;

    // streaming state
    bool streaming = false;
    int stream_pos = -1;                 // 0..17 for the 18 digits; >=18 means padding
    int lastA = 0, lastB = 0;

    // base-3 powers up to 3^9
    int pow3[10];

    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;
        tailStart = max(1, Nglob - W);

        streaming = false;
        stream_pos = -1;
        lastA = lastB = 0;

        pow3[0] = 1;
        for (int i=1;i<10;++i) pow3[i] = pow3[i-1] * 3;
    }

    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; diff; ++k, diff >>= 1) if (diff & 1) 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];
    }
    inline int get_digit_base3(int x, int d){ // d-th digit (LSB-first) in base-3
        // x / 3^d % 3
        return (x / pow3[d]) % 3;
    }
}

int send_message(int N, int i, int Pi){
    if (!inited || i == 1) reset_test(N);

    // build lifting 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), dB = dist(i, B);
    if (dA > D){ B = i; D = dA; }
    else if (dB > D){ A = i; D = dB; }

    int out = 0;

    if (i == tailStart){
        // start of tail window → RESET
        out = 0; // reset marker
        streaming = false;
        stream_pos = -1;
        lastA = A; lastB = B;
    } else if (i > tailStart){
        bool changed = (A != lastA) || (B != lastB);
        if (changed){
            // reset and restart for new endpoints
            out = 0;
            streaming = false;
            stream_pos = -1;
            lastA = A; lastB = B;
        } else {
            if (!streaming){ streaming = true; stream_pos = 0; }
            if (stream_pos < 18){
                // interleave U and V base-3 digits: u0,v0,u1,v1,...,u8,v8
                int which = stream_pos;
                int digit;
                if ((which & 1) == 0){ // even → U
                    int du = which/2;
                    digit = get_digit_base3(A, du);
                } else {               // odd → V
                    int dv = which/2;
                    digit = get_digit_base3(B, dv);
                }
                out = digit + 1; // 1..3
                ++stream_pos;
            } else {
                // padding: keep Z low and avoid new resets
                out = 1; // digit 0
            }
        }
    } else {
        // outside tail window: silent
        out = 0;
    }

    return out; // 0..3 (0 used only as reset inside the tail)
}

std::pair<int,int> longest_path(std::vector<int> S){
    int N = (int)S.size();
    const int W = 24;
    int tailStart = max(1, N - W);

    // Find last RESET (0) inside the tail window
    int lastReset = -1;
    for (int i = N-1; i >= tailStart; --i){
        if (S[i] == 0){ lastReset = i; break; }
    }
    if (lastReset == -1){
        // Fallback: no reset found (shouldn't happen) → return a safe default
        return {0, 0};
    }

    // Collect the FIRST 18 nonzero digits after lastReset
    vector<int> digs;
    digs.reserve(18);
    for (int i = lastReset + 1; i < N && (int)digs.size() < 18; ++i){
        if (S[i] >= 1 && S[i] <= 3) digs.push_back(S[i] - 1); // map to 0..2
        // ignore any accidental values outside {1,2,3}
    }
    while ((int)digs.size() < 18) digs.push_back(0); // pad if tiny N

    // Reconstruct U and V from interleaved base-3 digits (LSB-first)
    int pow3[10]; pow3[0] = 1; for (int i=1;i<10;++i) pow3[i] = pow3[i-1]*3;
    int U = 0, V = 0;
    for (int pos = 0; pos < 18; ++pos){
        int d = digs[pos];
        if ((pos & 1) == 0){ // U digit
            int k = pos/2;
            U += d * pow3[k];
        } else { // V digit
            int k = pos/2;
            V += d * pow3[k];
        }
    }
    // Clamp to [0, N-1] just in case
    if (U >= N) U = N - 1;
    if (V >= N) V = N - 1;
    return {U, V};
}

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