Submission #1251968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251968		Zbyszek99	Migrations (IOI25_migrations)	C++20	79.12 / 100	35 ms	1724 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9;

vi graph[10000];
int dist[10000];
int a = 0,b = 0,cur_dim = 0;

pii dfs_dist(int v, int pop, int d)
{
    dist[v] = d++;
    pii ans = {dist[v],v};
    forall(it,graph[v])
    {
        if(it != pop)
        {
            ans = max(ans,dfs_dist(it,v,d));
        }
    }
    return ans;
}

int send_message(int n, int i, int Pi) 
{
    int mes = i-(10000-21);
    if(mes < 0) 
    {
        graph[i].pb(Pi);
        graph[Pi].pb(i);
        return 0;
    }
    if(mes == 0)
    {
        a = dfs_dist(0,0,0).ss;
        pii x = dfs_dist(a,a,0);
        b = x.ss;
        cur_dim = x.ff;
    }
    graph[i].pb(Pi);
    graph[Pi].pb(i);
    pii new_dim = dfs_dist(i,i,0);
    if(new_dim.ff > cur_dim)
    {
        if(dist[a] == new_dim.ff)
        {
            b = i;
        }
        else
        {
            a = i;
        }
        cur_dim = new_dim.ff;
    }
    if(mes < 7)
    {
        int a2 = a;
        rep(i,mes)
        {
            a2 /= 4;
        }
        int dig = a2%4;
        if(a == i) return 4;
        return dig;
    }
    else
    {
        int b2 = b;
        rep(i,mes-7)
        {
            b2 /= 2;
        }
        int dig = b2%2;
        if(b == i) return 2;
        if(a == i) return 3+dig;
        return dig;
    }
}

pii longest_path(vi S) 
{
    int a = 0;
    int b = 0;
    bool was_a = 0;
    bool was_b = 0;
    rep2(i,10000-21,9999)
    {
        int mes = i - (10000-21);
        if(mes < 7)
        {
            if(was_a)
            {
                if(S[i] == 4) a = i;
            }
            else
            {
                if(S[i] == 4)
                {
                    a = i;
                    was_a = 1;
                }
                else
                {
                    a += (1 << (mes*2))*S[i];
                }
            }
        }
        else
        {
            if(S[i] == 3 || S[i] == 4) a = i;
            if(was_b)
            {
                if(S[i] == 2) b = i;
            }
            else
            {
                if(S[i] == 2)
                {
                    b = i;
                    was_b = 1;
                }
                else
                {
                    int val = 0;
                    if(S[i] == 1 || S[i] == 4) val = 1;
                    b += (1 << (mes-7))*val;
                }
            }
        }
    }
    return {a,b};
}

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