Submission #1252267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252267		christhegamechanger	Migrations (IOI25_migrations)	C++20	0 / 100	29 ms	1000 KiB

migrations

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int MAXN = 10000 + 5;
constexpr int LOG  = 14;                 // 2^14 > 10000

/* -------- lưu giữa các lần gọi -------- */
namespace {
    int Nglob = 0;
    int depth_[MAXN];
    int up[LOG][MAXN];

    int A = 0, B = 0, D = 0;             // hai đầu đường kính tạm
    int lastSentD = 0;                   // D của lần gửi gần nhất (0 = chưa)
    int messagesSent = 0;
}

/* ---------- hàm tiện ---------- */
int climb(int v, int k) {
    for (int b = 0; k; ++b, k >>= 1)
        if (k & 1) v = up[b][v];
    return v;
}
int lca(int u, int v) {
    if (depth_[u] < depth_[v]) swap(u, v);
    u = climb(u, depth_[u] - depth_[v]);
    if (u == v) return u;
    for (int b = LOG - 1; b >= 0; --b)
        if (up[b][u] != up[b][v]) {
            u = up[b][u];
            v = up[b][v];
        }
    return up[0][u];
}
inline int dist(int u, int v) {
    int w = lca(u, v);
    return depth_[u] + depth_[v] - 2 * depth_[w];
}

/* ===========================================================
   ==========  1.  HÀM ĐOÀN KHẢO SÁT  ======================== */
int send_message(int N, int i, int Pi) {
    if (i == 1) {                        // khởi tạo lần đầu
        Nglob = N;
        depth_[0] = 0;
        for (int b = 0; b < LOG; ++b) up[b][0] = 0;
    }

    /* -- cập nhật bảng tổ tiên cho đỉnh i -- */
    depth_[i] = depth_[Pi] + 1;
    up[0][i]  = Pi;
    for (int b = 1; b < LOG; ++b)
        up[b][i] = up[b - 1][ up[b - 1][i] ];

    /* -- kiểm tra đường kính -- */
    if (i == 1) {                        // bước đầu: A=0, B=1
        A = 0; B = 1; D = 1;
    } else {
        int d1 = dist(i, A);
        int d2 = dist(i, B);
        if (d1 >= d2 && d1 > D) { B = i; D = d1; }
        else if (d2 > d1 && d2 > D) { A = i; D = d2; }
    }

    /* -- quyết định có gửi hay không -- */
    bool send = false;
    int remainingNodes  = Nglob - 1 - i;
    int remainingBudget = 50 - messagesSent;

    if (lastSentD == 0)                          send = true;
    else if (D >= 2 * lastSentD)                 send = true;
    else if (remainingNodes <= remainingBudget - 1) send = true;

    if (!send) return 0;                         // không gửi

    int other = (A == i ? B : A);
    ++messagesSent;
    lastSentD = D;
    return other + 1;                            // 1 … 10000
}

/* ===========================================================
   ==========  2.  HÀM BẢO TÀNG  ============================== */
std::pair<int,int> longest_path(std::vector<int> S) {
    for (int i = (int)S.size() - 1; i >= 1; --i)
        if (S[i] > 0)                            // thông điệp cuối
            return {i, S[i] - 1};
    return {0,0};                                // N = 1
}

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