Submission #1252256

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

migrations

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

namespace {                       // 〈-- giữ biến giữa các lần gọi
    const int MAXN = 10'000 + 5;
    const int LOG  = 14;          // 2^14 = 16384 > 10000
    const int GAP  = 500;         // khoảng giãn thưa khi còn xa cuối

    int  Nglob   = 0;             // N của test hiện tại
    int  depth_  [MAXN];
    int  up      [LOG][MAXN];

    int  A = 0, B = 0, D = 0;     // hai đầu đường kính tạm thời
    int  lastSentD     = -1;      // độ dài lần gần nhất đã gửi
    int  messagesSent  = 0;       // đếm thông điệp (≤ 50)

    // ---------- LCA & distance ----------
    inline 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];
    }
} // unnamed namespace

/* --------------------------------------------------
 * 1. Hàm của đ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 thông tin 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 xem đường kính có tăng không --- */
    int d1 = dist(i, A);
    int d2 = dist(i, B);
    bool changed = false;
    if (d1 >= d2 && d1 > D) { B = i; D = d1; changed = true; }
    else if (d2 > d1 && d2 > D) { A = i; D = d2; changed = true; }

    /* --- quyết định có gửi thông điệp --- */
    bool sendNow = false;
    if (changed && messagesSent < 50) {
        int remainingNodes  = Nglob - 1 - i;         // còn bao nhiêu đỉnh sẽ tới
        int remainingBudget = 50 - messagesSent;     // còn bao nhiêu thông điệp

        if (remainingNodes <= remainingBudget - 1)
            sendNow = true;               // gần cuối: cứ lần nào tăng là gửi
        else if (lastSentD == -1 || D >= lastSentD + GAP)
            sendNow = true;               // còn xa: giãn thưa
    }

    if (!sendNow) return 0;

    /* --- gửi: mã hoá cặp (U,V) = (i , other) --- */
    int other = (A == i ? B : A);
    ++messagesSent;
    lastSentD = D;
    return other + 1;                     // 1 … 10000
}

/* --------------------------------------------------
 * 2. Hàm của 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)
            return {i, S[i] - 1};         // cặp cuối cùng đã mã hoá đường kính
    return {0, 0};                        // N = 1
}

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