Submission #1296855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296855		cnam9	Migrations (IOI25_migrations)	C++20	97.45 / 100	31 ms	1160 KiB

migrations

// #ifndef __TASK_CPP
// #define __TASK_CPP

#include <vector>
#include <algorithm>
#include <cassert>
#include <math.h>

using namespace std;

constexpr int N = 1e4;
constexpr int logN = static_cast<int>(log2(N));

constexpr int NUM_TRANSMITTER = 9;

pair<int, int> maxopt = {0, 0};
int depth[N] = {0};
int up[N][logN + 1];

const static int c[NUM_TRANSMITTER + 1] = {0,
    181, 30, 6, 1, 1, 2, 1, 1, 1
};
const static int l[NUM_TRANSMITTER + 1] = {9842,
    440, 70, 20, 5, 2, 4, 5, 2, 1
};
const static int r[NUM_TRANSMITTER + 1] = {10146,
    715, 95, 25, 26, 27, 5, 2, 3, 1
};
const static int il[NUM_TRANSMITTER + 1] = {0,
    38, 11, 5, 5, 5, 1, 1, 5, 2
};
const static int ir[NUM_TRANSMITTER + 1] = {0,
    19, 11, 5, 1, 1, 9, 5, 1, 3
};
int checkpoint[NUM_TRANSMITTER + 1];

int diameter;
int L, R;
vector<int> Lposs, Rposs;

inline long long ceildiv(long long a, long long b) {
    return (a + b - 1) / b;
}

void init() {
    diameter = 0;
    L = 0, R = 0;

    maxopt = {0, 0};
    depth[0] = 0;

    int Nstart = N + 1;
    for (int i = 1; i <= NUM_TRANSMITTER; i++) {
        Nstart -= c[i];
    }

    Lposs = Rposs = {0};
}

int lca(int u, int v) {
    if (u == -1) return v;
    if (v == -1) return u;
 
    if (depth[u] < depth[v]) swap(u, v);
 
    for (int i = logN; i >= 0; i--) {
        if (depth[u] - (1 << i) >= depth[v]) {
            u = up[u][i];
        }
    }
 
    if (u == v) return u;
 
    for (int i = logN; i >= 0; i--) {
        if (up[u][i] == up[v][i]) continue;
        u = up[u][i];
        v = up[v][i];
    }
    return up[u][0];
}

int distance(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
 
int send_message(int n, int i, int p) {
    if (i == 1) init();

    depth[i] = depth[p] + 1;
    up[i][0] = p;
    for (int j = 0; j < logN; j++) {
        up[i][j + 1] = up[up[i][j]][j];
    }

    if (distance(i, L) > diameter) {
        diameter = distance(i, L);
        R = i;
        // cout << "!!!!!!!!! R-diameter has changed! to " << L << ", " << i << " (= " << diameter << ")" << endl;
    } else if (distance(i, R) > diameter) {
        diameter = distance(i, R);
        L = i;
        // cout << "!!!!!!!!! L-diameter has changed! to " << i << ", " << R << " (= " << diameter << ")" << endl;
    }

    Lposs.push_back(i);
    Rposs.push_back(i);

    int skipped = 0, transmitter;
    for (transmitter = NUM_TRANSMITTER; transmitter; transmitter--) {
        skipped += c[transmitter];
        if (i >= N - skipped) break;
    }

    if (transmitter == 0) {
        return 0;
    }

    if (i == N - skipped) {
        int lpos = lower_bound(Lposs.begin(), Lposs.end(), L) - Lposs.begin();
        int rpos = lower_bound(Rposs.begin(), Rposs.end(), R) - Rposs.begin();

        // cout << "Lposs = " << Lposs.size() << endl;
        // cout << "Rposs = " << Rposs.size() << endl;
        int newLposs = l[transmitter];
        int newRposs = r[transmitter];
        int ldiv = ceildiv(Lposs.size(), il[transmitter]);
        int rdiv = ceildiv(Rposs.size(), ir[transmitter]);
        int lsent = lpos / ldiv;
        int rsent = rpos / rdiv;
        checkpoint[transmitter] = lsent * ir[transmitter] + rsent;
        // cout << "hi " << transmitter << ": " << rsent * ir[transmitter] << ' ' << min<size_t>(Rposs.size(), (rsent + 1) * ir[transmitter]) << endl;
        // cout << "transmitter #" << transmitter << " sent: " << checkpoint[transmitter] << ' ' << lsent << ' ' << rsent << endl;
        // cout << i << endl;
        Lposs = vector<int>(Lposs.begin() + lsent * ldiv, min(Lposs.end(), Lposs.begin() + (lsent + 1) * ldiv));
        Rposs = vector<int>(Rposs.begin() + rsent * rdiv, min(Rposs.end(), Rposs.begin() + (rsent + 1) * rdiv));
    }

    if (i == N - skipped + checkpoint[transmitter] / 4) {
        return 1 + (checkpoint[transmitter] & 3);
    }
    return 0;
}


pair<int, int> longest_path(vector<int> S) {
    init();

    int skipped = 0;
    for (int transmitter = NUM_TRANSMITTER; transmitter; transmitter--) {
        skipped += c[transmitter];
    }

    int last = 1;

    for (int transmitter = 1; transmitter <= NUM_TRANSMITTER; transmitter++) {
        for (int i = last; i <= N - skipped; i++) {
            Lposs.push_back(i);
        }
        for (int i = last; i <= N - skipped; i++) {
            Rposs.push_back(i);
        }
        last = N - skipped + 1;
        int msg = 4 * c[transmitter];
        for (int i = N - skipped; i < N - skipped + c[transmitter]; i++) {
            if (S[i]) {
                msg = (i - (N - skipped)) * 4 + (S[i] - 1);
                break;
            }
        }
        // cout << "there were " << Lposs.size() << " * " << Rposs.size() << " posibilies" << endl;
        int newLposs = l[transmitter];
        int newRposs = r[transmitter];
        int lsent = msg / ir[transmitter];
        int rsent = msg % ir[transmitter];
        int ldiv = ceildiv(Lposs.size(), il[transmitter]);
        int rdiv = ceildiv(Rposs.size(), ir[transmitter]);
        // cout << "transmitter #" << transmitter << " revce: " << msg << ' ' << lsent << ' ' << rsent << endl;
        Lposs = vector<int>(Lposs.begin() + lsent * ldiv, min(Lposs.end(), Lposs.begin() + (lsent + 1) * ldiv));
        Rposs = vector<int>(Rposs.begin() + rsent * rdiv, min(Rposs.end(), Rposs.begin() + (rsent + 1) * rdiv));

        skipped -= c[transmitter];
    }
    assert(Lposs.size() == 1);
    assert(Rposs.size() == 1);
    return {Lposs[0], Rposs[0]};
}

// #include "IOI25_migrations_gen2.cpp"

// #endif

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