Submission #1275584

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

migrations

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

using namespace std;

// --------------------- Internal state for run #1 (send_message) ---------------------
namespace {
    bool inited = false;
    int Nglob = 0, LOGv = 0;
    int startIdx = 1;                   // start of the last-50 suffix

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

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

    // Suffix init bookkeeping
    bool sentInitA = false;
    bool sentInitB = false;

    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;

        int K = (Nglob >= 2 ? 50 : max(1, Nglob - 1));
        startIdx = max(1, Nglob - K);

        sentInitA = false;
        sentInitB = false;
    }

    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];
    }
}

int send_message(int N, int i, int Pi) {
    // New test case begins at i == 1 (per problem statement).
    if (!inited || i == 1) reset_test(N);

    // add node i to 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);
    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; }

    // default: no message
    int out = 0;

    // Communicate only in the last-50 suffix.
    if (i >= startIdx) {
        if (i == startIdx && !sentInitA) {
            // First deterministic init: A
            out = A + 1;               // in [1..N] ≤ 10000
            sentInitA = true;
        } else if (i == startIdx + 1 && !sentInitB) {
            // Second deterministic init: B
            out = B + 1;
            sentInitB = true;
        } else if (changed) {
            // Any real change inside suffix: send other endpoint
            out = other + 1;
        }
        // else: silent
    }

    // 0 or [1..20000] is allowed; here values are ≤ 10000 by construction.
    return out;
}

// --------------------- Run #2 (Museum) ---------------------
std::pair<int,int> longest_path(std::vector<int> S) {
    int N = (int)S.size();
    if (N <= 1) return {0, 0};

    int K = (N >= 2 ? 50 : max(1, N - 1));
    int startIdxLocal = max(1, N - K);

    // Find the last message sent at or after startIdxLocal+2 (i.e., any "change" after the two inits)
    int lastIdx = -1;
    for (int i = N - 1; i >= startIdxLocal + 2; --i) {
        if (S[i] != 0) { lastIdx = i; break; }
    }

    if (lastIdx != -1) {
        // This is a real change message: (lastIdx, S[lastIdx]-1)
        return { lastIdx, S[lastIdx] - 1 };
    }

    // Otherwise, no changes occurred in the suffix after the two inits.
    // Use the two deterministic init messages placed at startIdxLocal and startIdxLocal+1.
    // (They are guaranteed to be sent by the team code.)
    int u = (S[startIdxLocal] > 0 ? S[startIdxLocal] - 1 : 0);
    int v = (S[startIdxLocal + 1] > 0 ? S[startIdxLocal + 1] - 1 : 0);
    return { u, v };
}

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