Submission #1261731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261731		Faggi	Migrations (IOI25_migrations)	C++20	0 / 100	32 ms	1476 KiB

migrations

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;

const int MAXN = 1e4;

bool init = 0, preg[MAXN];
ll dist[MAXN], ma = 0, nod = 0, prog[MAXN];

void ini()
{
    init = 1;
    ll i, cant = 1;
    preg[MAXN - 1] = 1;
    for (i = MAXN - 1 - 2; i > 0; i)
    {
        preg[i] = 1;
        cant = (cant + 1) * 2;
        i -= cant;
        i--;
    }
}
ll ant = -1, a = 0, b = 0, nMa = 0, maD = 0;
vector<ll> grafo[MAXN];

ll vis[MAXN];

void dfs(ll nod, ll dis)
{
    vis[nod] = 1;
    if (dis > maD)
    {
        maD = dis;
        nMa = nod;
    }
    else if (dis == maD)
        nMa = max(nMa, nod);
    for (auto k : grafo[nod])
    {
        if (vis[k])
            continue;
        dfs(k, dis + 1);
    }
}

int send_message(int N, int i, int Pi)
{
    if (init == 0)
        ini();
    grafo[i].pb(Pi);
    grafo[Pi].pb(i);
    ll auxA, auxB, dis;
    if (preg[i])
    {
        memset(vis, 0, sizeof(vis));
        auxA = a;
        auxB = b;
        maD = 0;
        nMa = b;
        dfs(a, 0);
        b = nMa;

        memset(vis, 0, sizeof(vis));
        maD = 0;
        nMa = a;
        dfs(b, 0);
        a = nMa;

        if (a < b)
            swap(a, b);
        if (auxA != a)
        {
            ll x = abs(i - a) + 1, j = i;
            while (x > 2)
            {
                x -= 2;
                j++;
            }
            prog[j] = x;
        }
        if (auxB != b)
        {
            ll x = abs(i - b) + 1, j = i;
            while (x > 2)
            {
                x -= 2;
                j++;
            }
            if (prog[j] != 0)
            {
                prog[j] += 2;
            }
            else
                prog[j] = x;
        }
    }
    if (prog[i] > 0)
        return prog[i];
    return 0;
}
pair<ll, ll> calc(ll i, vector<int> &s)
{
    pair<ll, ll> p = {-1, -1};
    ll ap = 0, dis = -1, act = 0, in = i;
    for (i; i < MAXN; i++)
    {
        if (preg[i])
            ap++;
        if (ap > 1)
            break;
        if (s[i] != 0)
        {
            if (s[i] > 2)
            {
                dis = (act + 1) - 1;
                p.fr = in - dis;
                dis = (act + 2) - 1;
                p.se = in - dis;
            }
            else
            {
                act = act + s[i];
                dis = act - 1;
                if (p.fr == -1)
                    p.fr = in - dis;
                else
                    p.se = in - dis;
                act = act - s[i];
            }
        }
        act = act + 2;
    }
    return p;
}

std::pair<int, int> longest_path(std::vector<int> S)
{
    pair<ll, ll> p = {0, 0}, a;
    ll i;
    ini();
    for (i = 0; i < MAXN; i++)
    {
        if (preg[i])
        {
            a = calc(i, S);
            if (a.fr != -1)
                p.fr = a.fr;
            if (a.se != -1)
                p.se = a.se;
        }
    }
    pair<int, int> an = p;
    return an;
}

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