Submission #1269557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269557		SamAnd	Migrations (IOI25_migrations)	C++20	79.12 / 100	1954 ms	1744 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 10004;

vector<int> g[N];
int dfs(int x, int p, int y, int d)
{
    if (x == y)
        return d;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (h == p)
            continue;
        int dd = dfs(h, x, y, d + 1);
        if (dd != -1)
            return dd;
    }
    return -1;
}

int dist(int x, int y)
{
    return dfs(x, x, y, 0);
}

int a, b;

int send_message(int n, int x, int p)
{
    g[x].push_back(p);
    g[p].push_back(x);

    int d = dist(a, b);
    int da = dist(x, a);
    int db = dist(x, b);

    if (x < n - 21)
    {
        if (da > db)
        {
            if (da > d)
            {
                b = x;
            }
        }
        else
        {
            if (db > d)
            {
                a = x;
            }
        }
        return 0;
    }
    if (x < n - 14)
    {
        if (da > db)
        {
            if (da > d)
            {
                b = x;
            }
        }
        else
        {
            if (db > d)
            {
                a = x;
                return 4;
            }
        }
        if (a >= n - 21)
            return 0;
        int i = x - (n - 21);
        int aa = a;
        for (int j = 0; j < i; ++j)
            aa /= 4;
        return aa % 4;
    }
    {
        if (da > db)
        {
            if (da > d)
            {
                b = x;
                return 2;
            }
        }
        else
        {
            if (db > d)
            {
                a = x;
                int i = x - (n - 14);
                if ((b & (1 << i)))
                    return 3;
                return 4;
            }
        }
        if (b >= n - 14)
            return 0;
        int i = x - (n - 14);
        if ((b & (1 << i)))
            return 1;
        return 0;
    }
}

std::pair<int, int> longest_path(std::vector<int> S)
{
    int n = sz(S);
    int a = 0;
    int t = 1;
    for (int x = n - 21; x < n - 14; ++x)
    {
        if (S[x] == 4)
            a = x;
        else
        {
            if (a < n - 21)
            {
                a = a + t * S[x];
            }
        }
        t *= 4;
    }
    int b = 0;
    for (int x = n - 14; x < n; ++x)
    {
        if (S[x] == 2)
            b = x;
        else if (S[x] < 2)
        {
            if (b < n - 14)
            {
                int i = x - (n - 14);
                if (S[x] == 1)
                    b |= (1 << i);
            }
        }
        else
        {
            a = x;
            if (b < n - 14)
            {
                int i = x - (n - 14);
                if (S[x] == 3)
                    b |= (1 << i);
            }
        }
    }
    return m_p(a, b);
}

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