Submission #1275576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275576		mehrzad	Migrations (IOI25_migrations)	C++17	20.01 / 100	42 ms	1172 KiB

migrations

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

/*
Protocol (suffix-only, K=50):
- While visiting the last K nodes (i >= N-K):
  * If adding node i changes the current diameter (u,v) to include i, send
    S[i] = other_endpoint + 1               // 1..10000  (UNTAGGED)
  * Else, if we have not yet sent the two "init" messages, send:
      first init:  S[i] = 10000 + (a + 1)   // 10001..20000 (TAGGED)
      second init: S[i] = 10000 + (b + 1)   // 10001..20000 (TAGGED)
    (We skip the second init if a real change occurs before we send it.)
- Outside the suffix: send 0.

Decoding:
- If there exists at least one UNTAGGED message (<=10000), take the last one:
    answer = (last_index, S[last_index] - 1)
- Else, take the last two TAGGED messages (>10000):
    answer = ( (S1-10000)-1 , (S2-10000)-1 )
This is unambiguous and within bounds.
*/

namespace {
    // Per-test static state
    bool inited = false;
    int Nglob = 0, LOG = 0, K = 50, startIdx = 1;

    // Tree state
    vector<int> depth;
    vector<array<int, 20>> up; // 20 > ceil(log2(10000))=14; keep slack

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

    // Suffix init bookkeeping
    bool sentInit1 = false, sentInit2Pending = false;
    int init2Val = 0;

    // Lift / LCA helpers
    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 = LOG - 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 void reset_test(int N) {
        inited = true;
        Nglob = N;
        LOG = 0; while ((1 << LOG) <= max(1, Nglob)) ++LOG;
        depth.assign(Nglob, 0);
        up.assign(Nglob, {});
        for (int k = 0; k < LOG; ++k) up[0][k] = 0;

        A = B = 0; D = 0;
        K = min(50, max(1, Nglob - 1));              // talk in the last up to 50 edges
        startIdx = max(1, Nglob - K);

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

int send_message(int N, int i, int Pi) {
    // Per-test reinitialization when a new test case starts (first edge i==1)
    if (!inited || i == 1) {
        reset_test(N);
    }

    // Build lifting info for node i
    depth[i] = depth[Pi] + 1;
    up[i][0] = Pi;
    for (int k = 1; k < LOG; ++k) up[i][k] = up[ up[i][k-1] ][k-1];

    // Check if adding i changes current diameter
    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;
    const int TAG_BASE = 10000; // tag threshold

    if (i >= startIdx) {
        if (changed) {
            // Real change: send untagged other+1 (<= 10000)
            out = other + 1;
            // Any pending second init becomes unnecessary/ambiguous → cancel it
            sentInit2Pending = false;
        } else if (!sentInit1) {
            // First time we speak in the suffix, and no change yet: send tagged A
            out = TAG_BASE + (A + 1);
            sentInit1 = true;
            sentInit2Pending = true;
            init2Val = TAG_BASE + (B + 1);
        } else if (sentInit2Pending) {
            // Send the second tagged init, unless a change already happened (handled above)
            out = init2Val;
            sentInit2Pending = false;
        } // else remain silent
    }

    // Sanity: keep within bounds (debug guard; not needed in grader)
    // if (out < 0 || out > 20000) out = 0;

    return out;
}

std::pair<int,int> longest_path(std::vector<int> S) {
    // Gather all messages (index, value)
    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 there is any UNTAGGED change message (<=10000), the last one encodes (i, other)
    int lastChangeIdx = -1, lastChangeVal = -1;
    for (int t = (int)msgs.size() - 1; t >= 0; --t) {
        if (msgs[t].second <= 10000) { lastChangeIdx = msgs[t].first; lastChangeVal = msgs[t].second; break; }
    }
    if (lastChangeIdx != -1) {
        return { lastChangeIdx, lastChangeVal - 1 };
    }

    // Otherwise, we must have sent two TAGGED inits (>10000). Use the last two.
    int tagged1 = -1, tagged2 = -1; // last then previous
    for (int t = (int)msgs.size() - 1; t >= 0; --t) {
        if (msgs[t].second > 10000) {
            if (tagged1 == -1) tagged1 = msgs[t].second;
            else { tagged2 = msgs[t].second; break; }
        }
    }
    if (tagged1 != -1 && tagged2 != -1) {
        int u = (tagged2 - 10000) - 1;
        int v = (tagged1 - 10000) - 1;
        return {u, v};
    }

    // Extremely degenerate edge cases (shouldn't occur with N=10000/K>=2), fallback:
    if (!msgs.empty()) {
        int i = msgs.back().first, v = msgs.back().second;
        if (v <= 10000) return { i, v - 1 };
        int u = (v - 10000) - 1;
        // Pair with something plausible; this path should never trigger on official tests.
        return { 0, max(0, u) };
    }
    return {0, 0};
}

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