Submission #1275572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275572		mehrzad	Migrations (IOI25_migrations)	C++17	0 / 100	40 ms	824 KiB

migrations

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

// ---------------------- Research team ----------------------
int send_message(int N, int i, int Pi) {
    // Persistent state across calls in the FIRST run
    static bool inited = false;
    static int N_glob = 0, LOG = 0;
    static vector<int> depth;
    static vector<array<int, 15>> up;   // 2^14 = 16384 > 10000
    static int a = 0, b = 0, diam = 0;  // current diameter endpoints and length
    static int sent = 0;                // messages sent (cap at 50)

    if (!inited) {
        inited = true;
        N_glob = N;
        LOG = 0;
        while ((1 << LOG) <= max(1, N_glob)) ++LOG; // <= 14 for N<=10000
        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;
        sent = 0;
    }

    // Update ancestry 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];

    auto lift = [&](int u, int d) {
        for (int k = 0; k < LOG; ++k) if (d & (1 << k)) u = up[u][k];
        return u;
    };
    auto lca = [&](int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        u = lift(u, depth[u] - depth[v]);
        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];
    };

    int ans = 0;

    // Check if the new node extends the diameter
    int du = dist(i, a);
    int dv = dist(i, b);

    if (du > diam || dv > diam) {
        // New diameter is (i, other), where other is the farther of (a,b)
        int other;
        if (du > dv) { other = a; b = i; diam = du; }
        else         { other = b; a = i; diam = dv; }

        // Send at most 50 messages, encode endpoint as other+1 in [1..N]
        if (sent < 50) {
            ans = other + 1;  // 1..10000 ≤ 20000
            ++sent;
        }
    }

    return ans; // 0 = no message
}

// ---------------------- Museum ----------------------
std::pair<int,int> longest_path(std::vector<int> S) {
    // Find the last non-zero message; its index is one endpoint, the value-1 the other
    for (int i = (int)S.size() - 1; i >= 1; --i) {
        if (S[i] != 0) {
            return { i, S[i] - 1 };
        }
    }
    // Fallback: if no messages (should not happen), tree has only node 0 or trivial
    return {0, 0};
}

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