Submission #1258838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258838		Timosh	Migrations (IOI25_migrations)	C++20	91.23 / 100	33 ms	1780 KiB

migrations

#include "bits/stdc++.h"
#include "migrations.h"

using namespace std;
int n = 1e4;
vector<vector<int>> p(n, vector<int>(20, -1));
vector<int> d(n), x(n), y(n);
int a, b;

int C(int n, int k)
{
    int res = 1;
    for (int i = 1; i <= k; i++)
        res = res * (n - i + 1) / i;
    return res;
}

vector<int> encode(int k, int r, int g)
{
    vector<int> ans(r);
    int left = g;
    for (int i = 0; i < r; i++)
    {
        int x = C(r - i - 1, left);
        if (x <= k)
            k -= x, left--, ans[i] = 1;
    }
    return ans;
}

int decode(vector<int> v, int r, int g)
{
    int k = 0;
    int left = g;
    for (int i = 0; i < r; i++)
        if (v[i])
            k += C(r - i - 1, left--);
    return k;
}

vector<int> chosen;

int kup(int a, int k)
{
    for (int i = 19; i >= 0; i--)
    {
        if ((k >> i) & 1)
            a = p[a][i];
        if (a == -1)
            return -1;
    }
    return a;
}

int lca(int a, int b)
{
    if (d[a] > d[b])
        swap(a, b);
    b = kup(b, d[b] - d[a]);
    if (a == b)
        return a;
    for (int i = 19; i >= 0; i--)
        if (p[a][i] != p[b][i])
            a = p[a][i], b = p[b][i];
    return p[a][0];
}

int dist(int a, int b)
{
    return d[a] + d[b] - 2 * d[lca(a, b)];
}

int send_message(int N, int i, int Pi)
{
    y[i] = y[i - 1];
    x[i] = x[i - 1];
    p[i][0] = Pi;
    d[i] = d[Pi] + 1;
    for (int j = 1; j < 20; j++)
        if (p[i][j - 1] != -1)
            p[i][j] = p[p[i][j - 1]][j - 1];
    if (dist(i, x[i]) > dist(x[i], y[i]))
        y[i] = i;
    else if (dist(i, y[i]) > dist(x[i], y[i]))
        x[i] = i;
    // 60 3 3 1 1
    // y x _
    // _ y _
    // _ x y
    // y _ x
    // _ y x
    if (i < N - 68)
        return 0;
    if (i == N - 68)
    {
        b = x[i] + y[i] * n;
        chosen = encode(b / 256, 60, 4);
        b %= 256;
    }
    if (i < N - 8)
    {
        if (chosen[i - (N - 68)])
        {
            int ret = b % 4 + 1;
            b /= 4;
            return ret;
        }
        return 0;
    }
    if (i == N - 8)
    {
        b = N - 68;
        while (x[b] != x[i])
            b++;
        b -= N - 68;
    }
    if (i < N - 5)
    {
        if (x[i] != x[i - 1])
            return 0;
        int ret = b % 4 + 1;
        b /= 4;
        return ret;
    }
    if (i == N - 5)
    {
        b = N - 68;
        while (y[b] != y[i])
            b++;
        b -= N - 68;
    }
    if (i < N - 2)
    {
        if (y[i] != y[i - 1])
            return 0;
        int ret = b % 4 + 1;
        b /= 4;
        return ret;
    }
    if (i == N - 2)
    {
        b = N - 6;
        while (x[b] != x[i])
            b++;
        b -= N - 6;
        return b;
    }
    if (i == N - 1)
    {
        if (x[i] == x[i - 1])
        {
            if (y[i] == y[i - 2])
                return 0;
            if (y[i] == y[i - 1])
                return 1;
            return 2;
        }
        if (y[i] == y[i - 2])
            return 3;
        return 4;
    }
    return 0;
}

pair<int, int> longest_path(vector<int> S)
{
    int b, mult;
    pair<int, int> ans = {0, 0};
    vector<int> v;

    b = 0, mult = 1;
    for (int i = n - 68; i < n - 8; i++)
        v.push_back(S[i]);
    ans.first = decode(v, 60, 4) * 256;
    for (int i = 0; i < 60; i++)
        if (v[i])
            ans.first += (v[i] - 1) * mult, mult *= 4;
    ans.second = ans.first / n;
    ans.first %= n;

    b = 0, mult = 1;
    for (int i = n - 8; i < n - 5; i++)
    {
        b += (S[i] - 1) * mult;
        mult *= 4;
        if (S[i] == 0)
            ans.first = i, b = -1e4;
    }
    if (b > 0)
        ans.first = n - 68 + b;
    b = 0;
    mult = 1;
    for (int i = n - 5; i < n - 2; i++)
    {
        b += (S[i] - 1) * mult;
        mult *= 4;
        if (S[i] == 0)
            ans.second = i, b = -1e4;
    }
    if (b > 0)
        ans.second = n - 68 + b;
    if (S[n - 2])
        ans.first = n - 6 + S[n - 2];
    if (S[n - 1] == 1)
        ans.second = n - 2;
    if (S[n - 1] == 2)
        ans.second = n - 1;
    if (S[n - 1] == 3)
        ans.first = n - 1;
    if (S[n - 1] == 4)
        ans.first = n - 1, ans.second = n - 2;
    return ans;
}

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