Submission #1275578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275578		mehrzad	Migrations (IOI25_migrations)	C++17	28.09 / 100	35 ms	912 KiB

migrations

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

int send_message(int N, int i, int Pi) {
    // ---------- static data kept between calls ----------
    static bool initialized = false;
    static int N_glob, LOG, startIdx;
    static vector<int> depth;
    static vector<array<int, 15>> up;          // LOG ≤ 14 for N ≤ 10000
    static int a, b, diam;                     // current diameter ends and length
    static bool initDone;                      // have we sent the first init message ?
    static bool pendingSecond;                 // second init still waiting ?
    static int pendingSecondVal;               // its value (b+1)
    static bool firstCall = true;

    if (!initialized) {
        N_glob = N;
        LOG = 0;
        while ((1 << LOG) <= N_glob) ++LOG;    // LOG = ceil(log2(N+1))
        depth.assign(N_glob, 0);
        up.assign(N_glob, array<int,15>{});
        for (int k = 0; k < LOG; ++k) up[0][k] = 0;
        a = b = 0;
        diam = 0;
        startIdx = max(1, N_glob - 50);        // first vertex of the suffix
        initDone = false;
        pendingSecond = false;
        pendingSecondVal = 0;
        initialized = true;
    }

    // ----- store depth and ancestors of vertex 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];

    // ----- auxiliary LCA / distance functions -----
    auto lca = [&](int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        int diff = depth[u] - depth[v];
        for (int k = 0; k < LOG; ++k)
            if (diff & (1 << k)) 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];
    };
    auto dist = [&](int u, int v) {
        int w = lca(u, v);
        return depth[u] + depth[v] - 2 * depth[w];
    };

    // ----- evaluate possible diameter change -----
    int du = dist(i, a);
    int dv = dist(i, b);
    bool changed = false;
    int other = -1;               // the other endpoint of the new diameter

    if (du > diam) {
        changed = true;
        other = a;                // a stays, b becomes i
        b = i;
        diam = du;
    } else if (dv > diam) {
        changed = true;
        other = b;                // b stays, a becomes i
        a = i;
        diam = dv;
    }

    // ----- decide what to send -----
    int answer = 0;               // 0 → no message

    if (i >= startIdx) {
        if (!initDone) {                          // first vertex of the suffix
            if (changed) {
                answer = other + 1;               // change already, send it
                initDone = true;
            } else {
                answer = a + 1;                   // store first endpoint
                initDone = true;
                pendingSecond = true;
                pendingSecondVal = b + 1;          // second endpoint to be sent later
            }
        } else if (pendingSecond) {               // we still have to send the second init value
            if (changed) {
                answer = other + 1;               // a real change – we do not need the second init any more
                pendingSecond = false;
            } else {
                answer = pendingSecondVal;
                pendingSecond = false;
            }
        } else {                                  // normal part of the suffix
            if (changed) {
                answer = other + 1;               // a real change
            } else {
                answer = 0;
            }
        }
    }

    return answer;        // 0 means “no message”, otherwise 1 … 20000
}

/* ------------------------------------------------------------------ */

std::pair<int,int> longest_path(std::vector<int> S) {
    vector<pair<int,int>> msgs;          // (index , value)
    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};                    // should never happen

    if (msgs.size() == 1) {
        return { msgs[0].first , msgs[0].second - 1 };
    }

    if (msgs.size() == 2) {
        int i1 = msgs[0].first, v1 = msgs[0].second;
        int i2 = msgs[1].first, v2 = msgs[1].second;
        // case: second message is a real change
        if (v2 == v1)                     // init + change (both values equal)
            return { i2 , v2 - 1 };
        if (v2 - 1 == i1)                // change that points to the first vertex
            return { i2 , v2 - 1 };
        // otherwise two initial messages → the pair of endpoints
        return { v1 - 1 , v2 - 1 };
    }

    // three or more messages → the last one is a real change
    return { msgs.back().first , msgs.back().second - 1 };
}

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