Submission #1274833

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274833		mehrzad	Migrations (IOI25_migrations)	C++17	0 / 100	31 ms	1336 KiB

migrations

#include "migrations.h"
#include <vector>
#include <algorithm>
#include <cmath>

// Globals for the research team's (send_message) phase
namespace {
    // Constants for the messaging protocol
    const int BITS_PER_NODE = 14;
    const int MSGS_PER_NODE = (BITS_PER_NODE + 1) / 2; // Each message (1-4) carries 2 bits
    const int TOTAL_MSGS_PER_PAIR = 2 * MSGS_PER_NODE;

    // Tree-related data structures
    int N_val;
    std::vector<int> parent;
    std::vector<int> depth;
    std::vector<std::vector<int>> up;
    int log_N;

    // Current diameter endpoints
    int current_U;
    int current_V;

    // Payload for the final transmission
    std::vector<int> msg_payload;
}

// Initializes global state for the research team
void init_globals(int N) {
    N_val = N;
    log_N = (N > 1) ? floor(log2(N)) + 1 : 1;
    parent.assign(N, -1);
    depth.assign(N, 0);
    up.assign(N, std::vector<int>(log_N, 0));
    current_U = 0;
    current_V = 0;
}

// Finds the Lowest Common Ancestor of two nodes
int get_lca(int u, int v) {
    if (depth[u] < depth[v]) std::swap(u, v);
    
    for (int j = log_N - 1; j >= 0; --j) {
        if (depth[u] - (1 << j) >= depth[v]) {
            u = up[u][j];
        }
    }

    if (u == v) return u;

    for (int j = log_N - 1; j >= 0; --j) {
        if (up[u][j] != up[v][j]) {
            u = up[u][j];
            v = up[v][j];
        }
    }
    return parent[u];
}

// Calculates distance between two nodes in the tree
int get_dist(int u, int v) {
    if (u == -1 || v == -1) return -1;
    int lca = get_lca(u, v);
    return depth[u] + depth[v] - 2 * depth[lca];
}

// Research team's procedure
int send_message(int N, int i, int Pi) {
    if (i == 1) {
        init_globals(N);
    }
    
    // Update tree structure with the new node i
    parent[i] = Pi;
    depth[i] = depth[Pi] + 1;
    up[i][0] = Pi;
    for (int j = 1; j < log_N; ++j) {
        up[i][j] = up[up[i][j - 1]][j - 1];
    }
    
    // Online update of the diameter
    int dist_UV = get_dist(current_U, current_V);
    int dist_iU = get_dist(i, current_U);
    int dist_iV = get_dist(i, current_V);

    if (dist_iU > dist_UV && dist_iU >= dist_iV) {
        current_V = i;
        std::swap(current_U, current_V);
    } else if (dist_iV > dist_UV) {
        current_U = i;
    }

    // At a pre-determined point, compute the current diameter and schedule it for transmission
    int decision_idx = (N - 1) - TOTAL_MSGS_PER_PAIR;

    if (i == decision_idx) {
        int U_to_send = current_U;
        int V_to_send = current_V;
        if (U_to_send > V_to_send) std::swap(U_to_send, V_to_send);

        msg_payload.clear();
        for (int k = 0; k < MSGS_PER_NODE; ++k) {
            int u_bits = (U_to_send >> (2 * k)) & 3;
            msg_payload.push_back(u_bits + 1);
        }
        for (int k = 0; k < MSGS_PER_NODE; ++k) {
            int v_bits = (V_to_send >> (2 * k)) & 3;
            msg_payload.push_back(v_bits + 1);
        }
    }
    
    // Send the scheduled messages in the final slots
    if (i > decision_idx) {
        int msg_idx = i - (decision_idx + 1);
        if (msg_idx >= 0 && msg_idx < msg_payload.size()) {
            return msg_payload[msg_idx];
        }
    }

    return 0; // No message sent
}

// Museum's procedure
std::pair<int, int> longest_path(std::vector<int> S) {
    int N = S.size();
    if (N == 0) return {0, 0};

    // The sender sends messages only in the last few slots.
    // We collect messages from these specific slots.
    std::vector<int> received_msgs;
    int start_idx = (N - 1) - TOTAL_MSGS_PER_PAIR + 1;
    if (start_idx < 1) start_idx = 1;

    for (int i = start_idx; i < N; ++i) {
        received_msgs.push_back(S[i]);
    }

    if (received_msgs.empty()) return {0, 0};
    
    int U = 0, V = 0;
    
    // Decode the first node ID
    int msgs_for_U = std::min((int)received_msgs.size(), MSGS_PER_NODE);
    for(int k = 0; k < msgs_for_U; ++k) {
        if (received_msgs[k] == 0) continue;
        int bits = received_msgs[k] - 1;
        U |= (bits << (2 * k));
    }
    
    // Decode the second node ID
    if (received_msgs.size() > MSGS_PER_NODE) {
        for(size_t k = 0; k < received_msgs.size() - MSGS_PER_NODE; ++k) {
            if (received_msgs[k + MSGS_PER_NODE] == 0) continue;
            int bits = received_msgs[k + MSGS_PER_NODE] - 1;
            V |= (bits << (2 * k));
        }
    }

    if (U > V) std::swap(U, V);
    return {U, V};
}

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