Submission #1273681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273681		lucas110550	Migrations (IOI25_migrations)	C++20	0 / 100	30 ms	824 KiB

migrations

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

static const int LOG = 15;               // 2^14 = 16384 > 10000

static int N_global = -1;                // set on first call
static vector<int> parent_arr;           // parent[i]
static vector<int> depth_arr;            // depth[i]
static vector<array<int, LOG>> up;       // binary lifting table

static int endA = 0, endB = 0;           // current diameter endpoints
static int diam = 0;                     // current diameter length

/*---------------------------------------------------------------*/
/*  lowest common ancestor (binary lifting)                      */
static int lca(int u, int v) {
    if (depth_arr[u] < depth_arr[v]) swap(u, v);
    int diff = depth_arr[u] - depth_arr[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];
}

/*---------------------------------------------------------------*/
static inline int dist(int u, int v) {
    int w = lca(u, v);
    return depth_arr[u] + depth_arr[v] - 2 * depth_arr[w];
}

/*---------------------------------------------------------------*/
int send_message(int N, int i, int Pi) {
    /* first call – initialise all structures */
    if (N_global != N) {
        N_global = N;
        parent_arr.assign(N, 0);
        depth_arr.assign(N, 0);
        up.assign(N, {});
        // root 0
        parent_arr[0] = 0;
        depth_arr[0] = 0;
        for (int k = 0; k < LOG; ++k) up[0][k] = 0;
        endA = endB = 0;
        diam = 0;
    }

    /* store the new vertex */
    parent_arr[i] = Pi;
    depth_arr[i] = depth_arr[Pi] + 1;
    up[i][0] = Pi;
    for (int k = 1; k < LOG; ++k)
        up[i][k] = up[ up[i][k - 1] ][k - 1];

    /* update the diameter */
    int d1 = dist(i, endA);
    if (d1 > diam) {
        diam = d1;
        endB = i;                // new diameter (i , endA)
    } else {
        int d2 = dist(i, endB);
        if (d2 > diam) {
            diam = d2;
            endA = i;            // new diameter (i , endB)
        }
    }

    /* we do not send any message */
    return 0;
}

/*---------------------------------------------------------------*/
std::pair<int,int> longest_path(std::vector<int> /*S*/) {
    // the answer has already been computed while processing the tree
    return {endA, endB};
}

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