Submission #1274809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274809		mehrzad	Migrations (IOI25_migrations)	C++17	Compilation error	0 ms	0 KiB

migrations

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

static bool initialized = false;
static int N_global = 0;
static const int LOGV = 15;                 // 2^14 = 16384 > 10000
static vector<int> parentArr;
static vector<int> depthArr;
static vector<array<int, LOGV>> upArr;

static int endA = 0, endB = 0, curDist = 0; // current diameter endpoints and length
static int repl_Nminus2 = -1;               // replacement code for node N-2 (0/1/2)

static int lca(int u, int v) {
    if (depthArr[u] < depthArr[v]) swap(u, v);
    int diff = depthArr[u] - depthArr[v];
    for (int k = 0; diff; ++k) {
        if (diff & 1) u = upArr[u][k];
        diff >>= 1;
    }
    if (u == v) return u;
    for (int k = LOGV - 1; k >= 0; --k) {
        if (upArr[u][k] != upArr[v][k]) {
            u = upArr[u][k];
            v = upArr[v][k];
        }
    }
    return upArr[u][0];
}
static int dist(int u, int v) {
    int w = lca(u, v);
    return depthArr[u] + depthArr[v] - 2 * depthArr[w];
}

/*  return code of what happened when node x is added:
    0 – no change,
    1 – endpoint A is replaced by x,
    2 – endpoint B is replaced by x   */
static int update_diameter(int x) {
    int da = dist(x, endA);
    int db = dist(x, endB);
    if (da > curDist) {
        endB = x;
        curDist = da;
        return 2;
    } else if (db > curDist) {
        endA = x;
        curDist = db;
        return 1;
    }
    return 0;
}

int send_message(int N, int i, int Pi) {
    if (!initialized) {
        N_global = N;
        parentArr.assign(N, -1);
        depthArr.assign(N, 0);
        upArr.assign(N, array<int, LOGV>{});
        for (int k = 0; k < LOGV; ++k) upArr[0][k] = 0;   // root
        endA = endB = 0;
        curDist = 0;
        repl_Nminus2 = -1;
        initialized = true;
    }

    // add node i
    parentArr[i] = Pi;
    depthArr[i] = depthArr[Pi] + 1;
    upArr[i][0] = Pi;
    for (int k = 1; k < LOGV; ++k)
        upArr[i][k] = upArr[ upArr[i][k - 1] ][k - 1];

    // handle tiny N specially
    if (N_global == 2) {
        update_diameter(i);
        return 0;
    }
    if (N_global == 3) {
        if (i == 1) {
            update_diameter(i);
            return 0;
        } else { // i == 2, last node
            update_diameter(i);
            int a = endA, b = endB;
            if (a > b) swap(a, b);
            int code = a * N_global + b + 1; // fits into [1,9] for N=3
            return code;
        }
    }

    // general case N >= 4
    if (i == N_global - 3) {
        // after processing this node, send endpoint A
        update_diameter(i);
        return endA + 1;
    }
    if (i == N_global - 2) {
        // store current endpoint B before possible change
        int storedB = endB;
        repl_Nminus2 = update_diameter(i);
        return storedB + 1;
    }
    if (i == N_global - 1) {
        int repl_last = update_diameter(i);
        int code = repl_Nminus2 * 3 + repl_last; // 0..8
        return code + 1;                         // 1..9
    }
    // all other nodes
    update_diameter(i);
    return 0;
}

std::pair<int, int> longest_path(std::vector<int> S) {
    int N = (int)S.size();
    if (N == 2) return {0, 1};
    if (N == 3) {
        int code = -1;
        for (int i = 0; i < N; ++i) if (S[i] != 0) { code = S[i] - 1; break; }
        int a = code / N;
        int b = code % N;
        return {a, b};
    }
    // N >= 4
    int a = S[N - 3] - 1;
    int b = S[N - 2] - 1;
    int code = S[N - 1] - 1;
    int r2 = code / 3;
    int r3 = code % 3;
    if (r2 == 1) a = N - 2;
    else if (r2 == 2) b = N - 2;
    if (r3 == 1) a = N - 1;
    else if (r3 == 2) b = N - 1;
    return {a, b};
}
"
"#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;

/* ---------- global data kept between calls of send_message ---------- */
static int curN = -1;                       // current N
static int LOGN = 0;                        // number of binary‑lifting levels
static vector<array<int,15>> up;            // up[v][k] = 2^k ancestor
static vector<int> depth;                   // depth from the root

static int curA = 0, curB = 0, curLen = 0;   // current diameter endpoints
static int savedA = -1, savedB = -1;        // endpoints after processing N-3

/* ---------- LCA utilities ---------- */
static int lca(int u, int v) {
    if (u == -1 || v == -1) return -1;
    if (depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v];
    for (int k = 0; diff; ++k) {
        if (diff & 1) u = up[u][k];
        diff >>= 1;
    }
    if (u == v) return u;
    for (int k = LOGN - 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[u] + depth[v] - 2 * depth[w];
}

/* ---------- the research team ---------- */
int send_message(int N, int i, int Pi) {
    /* (re)initialisation for a new test case */
    if (curN != N) {
        curN = N;
        LOGN = 0;
        while ((1 << LOGN) <= N) ++LOGN;          // enough for N ≤ 10000
        up.assign(N, array<int,15>());
        depth.assign(N, 0);
        for (int v = 0; v < N; ++v)
            for (int k = 0; k < LOGN; ++k) up[v][k] = -1;

        curA = curB = 0;
        curLen = 0;
        savedA = savedB = -1;
    }

    /* set depth and binary lifting table for the new vertex i */
    depth[i] = depth[Pi] + 1;
    up[i][0] = Pi;
    for (int k = 1; k < LOGN; ++k) {
        int mid = up[i][k - 1];
        up[i][k] = (mid == -1) ? -1 : up[mid][k - 1];
    }

    /* update current diameter */
    int dA = dist(i, curA);
    int dB = dist(i, curB);
    if (dA > curLen) {
        curB = i;
        curLen = dA;
    } else if (dB > curLen) {
        curA = i;
        curLen = dB;
    }

    /* ----- send the three messages ----- */
    if (N >= 4 && i == N - 3) {          // first old endpoint
        savedA = curA;
        savedB = curB;
        return savedA + 1;                // 1 … 20000
    }
    if (N >= 4 && i == N - 2) {          // second old endpoint
        return savedB + 1;                // 1 … 20000
    }
    if (N >= 4 && i == N - 1) {          // final flag
        int finalA = curA;
        int finalB = curB;
        auto same_pair = [&](int x, int y, int u, int v) {
            return (x == u && y == v) || (x == v && y == u);
        };
        int flag;
        if (same_pair(finalA, finalB, savedA, savedB)) {
            flag = 5;                     // unchanged
        } else if (finalA == N - 1 && (finalB == savedA || finalB == savedB)) {
            flag = (finalB == savedA) ? 1 : 2;
        } else if (finalB == N - 1 && (finalA == savedA || finalA == savedB)) {
            flag = (finalA == savedA) ? 1 : 2;
        } else if (finalA == N - 2 && (finalB == savedA || finalB == savedB)) {
            flag = (finalB == savedA) ? 3 : 4;
        } else if (finalB == N - 2 && (finalA == savedA || finalA == savedB)) {
            flag = (finalA == savedA) ? 3 : 4;
        } else if (same_pair(finalA, finalB, N - 2, N - 1)) {
            flag = 6;                     // (N-2 , N-1)
        } else {
            flag = 5;                     // should never happen
        }
        return flag;                     // 1 … 6
    }

    return 0;                            // no message
}

/* ---------- the museum ---------- */
pair<int, int> longest_path(std::vector<int> S) {
    int N = (int)S.size();

    if (N < 4) {                         // not required for the official sub‑task
        if (N == 2) return {0, 1};
        return {0, 0};
    }

    int a = S[N - 3] - 1;                // first old endpoint
    int b = S[N - 2] - 1;                // second old endpoint
    int flag = S[N - 1];

    switch (flag) {
        case 5:  return {a, b};                 // unchanged
        case 1:  return {a, N - 1};
        case 2:  return {b, N - 1};
        case 3:  return {a, N - 2};
        case 4:  return {b, N - 2};
        case 6:  return {N - 2, N - 1};
        default:                                    // never reached
            return {a, b};
    }
}
"

Compilation message (stderr)

migrations.cpp:137:1: warning: missing terminating " character
  137 | "
      | ^
migrations.cpp:137:1: error: missing terminating " character
migrations.cpp:138:24: warning: missing terminating " character
  138 | "#include "migrations.h"
      |                        ^
migrations.cpp:138:24: error: missing terminating " character
migrations.cpp:271:1: warning: missing terminating " character
  271 | "
      | ^
migrations.cpp:271:1: error: missing terminating " character
migrations.cpp:138:1: error: expected unqualified-id before user-defined string literal
  138 | "#include "migrations.h"
      | ^~~~~~~~~~~~~~~~~~~~~
migrations.cpp:152:12: error: redefinition of 'int lca(int, int)'
  152 | static int lca(int u, int v) {
      |            ^~~
migrations.cpp:15:12: note: 'int lca(int, int)' previously defined here
   15 | static int lca(int u, int v) {
      |            ^~~
migrations.cpp:169:19: error: redefinition of 'int dist(int, int)'
  169 | static inline int dist(int u, int v) {
      |                   ^~~~
migrations.cpp:31:12: note: 'int dist(int, int)' previously defined here
   31 | static int dist(int u, int v) {
      |            ^~~~
migrations.cpp:175:5: error: redefinition of 'int send_message(int, int, int)'
  175 | int send_message(int N, int i, int Pi) {
      |     ^~~~~~~~~~~~
migrations.cpp:55:5: note: 'int send_message(int, int, int)' previously defined here
   55 | int send_message(int N, int i, int Pi) {
      |     ^~~~~~~~~~~~
migrations.cpp:248:16: error: redefinition of 'std::pair<int, int> longest_path(std::vector<int>)'
  248 | pair<int, int> longest_path(std::vector<int> S) {
      |                ^~~~~~~~~~~~
migrations.cpp:115:21: note: 'std::pair<int, int> longest_path(std::vector<int>)' previously defined here
  115 | std::pair<int, int> longest_path(std::vector<int> S) {
      |                     ^~~~~~~~~~~~