Submission #1253166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253166		QwertyPi	Migrations (IOI25_migrations)	C++20	83.69 / 100	31 ms	1568 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
#define int long long
#define all(a) begin(a), end(a)
using namespace std;

const int N = 10'000;
const int LGN = 20;
vector<int> G[N];

pair<int, int> dfs(int v, int pa = -1) {
    int ud = v, d = -1;
    for (int u : G[v]) {
        if (u == pa) continue;
        auto [ud2, d2] = dfs(u, v);
        if (d2 > d) ud = ud2, d = d2;
    }
    return {ud, d + 1};
}

int encrypt(int N, int a, int b) {
    assert(a < b);
    int X = 0;
    for (int i = 0; i < a; i++) X += N - 1 - i;
    for (int i = a + 1; i < b; i++) X++;
    return X;
}

pair<int, int> decrypt(int N, int X) {
    int a = 0, b = 1;
    while (X >= N - 1 - a) X -= N - 1 - a, ++a, b = a + 1;
    while (X >= 1) --X, ++b;
    return {a, b};
}

int msg[N];

vector<int> R {0};
vector<int> C {19, 7, 4}, P {12, 3, 2};

pair<int, int> diameter() {
    auto [u, du] = dfs(0);
    auto [v, d] = dfs(u);
    if (u > v) swap(u, v);
    int a = find(all(R), u) - R.begin();
    int b = find(all(R), v) - R.begin();
    return {a, b};
}

int J1, K1;
vector<vector<int>> M1 {
    {0, 1, 2},
    {2, 3, 4},
    {4, 0, 2},
    {2, 4, 1},
    {1, 3, 0}
};

int _N;
int32_t send_message(int32_t N, int32_t i, int32_t Pi) {
    _N = N;
    for (int x = 0; x < C.size(); x++) {
        int c = C[x], p = P[x];
        if (i == N - c) {
            auto [a, b] = diameter();
            int X = encrypt(R.size(), a, b);
            R = {R[a], R[b]};
            for (int j = 0; j < p; j++) {
                msg[N - c + j] = X % 5;
                X /= 5;
            }
        }
    }
    if (i == N - 2) {
        G[i].push_back(Pi);
        G[Pi].push_back(i);
        R.push_back(i);
        auto [a, b] = diameter();
        for (int j = 0; j < 5; j++) {
            for (int k = 0; k < 2; k++) {
                if (set<int>{a, b} == set<int>{M1[j][k], M1[j][k + 1]}) {
                    msg[N - 2] = j;
                    J1 = j; K1 = k;
                }
            }
        }
    } else if (i == N - 1) {
        G[i].push_back(Pi);
        G[Pi].push_back(i);
        R.push_back(i);
        auto [a, b] = diameter();
        if (b == 5) {
            for (int k = 0; k < 3; k++) {
                if (M1[J1][k] == a) msg[N - 1] = 2 + k;
            }
        } else {
            for (int k = 0; k < 2; k++) {
                if (set<int>{a, b} == set<int>{M1[J1][k], M1[J1][k + 1]}) {
                    msg[N - 1] = k;
                }
            }
        }
    } else {
        G[i].push_back(Pi);
        G[Pi].push_back(i);
        R.push_back(i);
    }
    return msg[i];
}

pair<int32_t, int32_t> longest_path(vector<int32_t> S) {
    R = vector<int>{0};
    int prv = 1;
    for (int x = 0; x < C.size(); x++) {
        int c = C[x], p = P[x];
        while (prv < N - c) R.push_back(prv++);
        int X = 0;
        for (int i = (N - c) + p - 1; i >= (N - c); i--) {
            X = X * 5 + S[i];
        }
        auto [a, b] = decrypt(R.size(), X);
        R = {R[a], R[b]};
    }
    R.push_back(N - 4);
    R.push_back(N - 3);
    R.push_back(N - 2);

    switch (S[N - 1]) {
        case 0:
            return {R[M1[S[N - 2]][0]], R[M1[S[N - 2]][1]]};
        case 1:
            return {R[M1[S[N - 2]][1]], R[M1[S[N - 2]][2]]};
        case 2:
            return {R[M1[S[N - 2]][0]], N - 1};
        case 3:
            return {R[M1[S[N - 2]][1]], N - 1};
        case 4:
            return {R[M1[S[N - 2]][2]], N - 1};
    }
}

Compilation message (stderr)

migrations.cpp: In function 'std::pair<int, int> longest_path(std::vector<int>)':
migrations.cpp:140:1: warning: control reaches end of non-void function [-Wreturn-type]
  140 | }
      | ^

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