Submission #1261701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261701		Faggi	Migrations (IOI25_migrations)	C++20	30 / 100	28 ms	516 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], pr = 1;

void ini()
{
    init = 1;
    ll i, cant = 3;
    preg[MAXN - 1] = 1;
    for (i = MAXN - 1 - 4; i > 0; i)
    {
        pr++;
        preg[i] = 1;
        cant = (cant + 1) * 4;
        i -= cant;
        i--;
    }
}
ll ant = -1;
int send_message(int N, int i, int Pi)
{
    if (init == 0)
        ini();
    dist[i] = dist[Pi] + 1;
    if (ma < dist[i])
    {
        ma = dist[i];
        nod = i;
    }
    if (preg[i])
    {
        if (ant == nod)
            return 0;
        ant = nod;
        ll x = abs(i - nod) + 1, j = i;
        while (x > 4)
        {
            x -= 4;
            j++;
        }
        prog[j] = x;
    }
    if (prog[i] > 0)
        return prog[i];
    return 0;
}
ll calc(ll i, vector<int>&s)
{
    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)
        {
            act=act+s[i];
            dis=act;
            break;
        }
        act = act + 4;
    }
    if(dis==-1)
        return 0;
    dis--;
    in=in-dis;
    return in;
}

std::pair<int, int> longest_path(std::vector<int> S)
{
    pair<ll, ll> p = {0, 0};
    ll i, MAXN=1e4;
    ll cant=3;
    vector<bool>preg(MAXN,0);
    preg[MAXN - 1] = 1;
    for (i = MAXN - 1 - 4; i > 0; i)
    {
        pr++;
        preg[i] = 1;
        cant = (cant + 1) * 4;
        i -= cant;
        i--;
    }
    for (i = 0; i < MAXN; i++)
    {
        if (preg[i])
        {
            p.se = max(p.se, calc(i,S));
        }
    }
    pair<int,int>an=p;
    return an;
}

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