Submission #1256194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256194		TheScrasse	Migrations (IOI25_migrations)	C++20	64.45 / 100	31 ms	1620 KiB

migrations

#include <bits/stdc++.h>
using namespace std;

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 998244353
#define maxn 110

#include "migrations.h"

vector<ll> parent, dist;
array<ll, 2> diam = {-1, -1};
ll to_send = 0;
vector<vector<ll>> adj;

int send_message(int N, int i, int Pi) {
    // ~ 65 punti
    if (parent.empty()) {
        parent.resize(N, -1);
        dist.resize(N, 0);
        adj.resize(N);
    }

    auto calc_dist = [&](ll a, ll b) {
        // cerr << "calc_dist" _ a _ b << nf;
        ll ans = 0;
        if (dist[a] > dist[b]) swap(a, b);
        while (dist[a] < dist[b]) {
            // cerr << a _ b << nf;
            b = parent[b]; ans++;
        }
        while (a != b) {
            // cerr << a _ b << nf;
            a = parent[a]; b = parent[b]; ans += 2;
        }
        return ans;
    };

    auto bfs = [&](ll N, ll start) {
        vector<bool> vis(N, false);
        vector<ll> dist(N, INF);
        function<void(ll)> dfs = [&](ll s) {
            vis[s] = true;
            for (auto u : adj[s]) {
                if (vis[u]) continue;
                dist[u] = dist[s] + 1;
                dfs(u);
            }
        };

        dfs(start);

        array<ll, 2> opt = {-INF, -1};
        for (ll i = 0; i < N; i++) opt = max(opt, {dist[i], i});
        assert(opt[0] != INF);
        return opt[1];
    };

    auto calc_diam = [&](ll N) {
        ll a = bfs(N, 0);
        ll b = bfs(N, a);
        // cerr << "diam" _ a _ b << nf;
        return array<ll, 2>{a, b};
    };
    
    parent[i] = Pi;
    adj[i].pb(Pi); adj[Pi].pb(i);
    dist[i] = dist[Pi] + 1;

    if (i < N - 27) return 0;
    if (i == N - 27) {
        diam = calc_diam(i + 1);
        auto [x, y] = diam;
        to_send = N * x + y;
    }

    auto upd_diam = [&](ll x, ll y, ll nw, ll pos) {
        ll d1 = calc_dist(x, y);
        if (pos == 1) {
            ll d2 = calc_dist(nw, y);
            if (d2 > d1) {
                diam = {nw, y}; return true;
            }
        }
        if (pos == 2) {
            ll d2 = calc_dist(x, nw);
            if (d2 > d1) {
                diam = {x, nw}; return true;
            }
        }

        return false;
    };

    ll b = N - 1 - i;
    ll ans = ((to_send >> b) & 1) + 1;
    if (upd_diam(diam[0], diam[1], i, 1)) ans += 2;
    if (upd_diam(diam[0], diam[1], i, 2)) ans += 4;
    assert(ans <= 6);
    
    // cout << "diam =" _ diam[0] _ diam[1] << nf;
    return ans;
}

std::pair<int, int> longest_path(std::vector<int> S) {
    ll N = S.size();
    ll encoded = 0;
    array<ll, 2> overwrite = {-1, -1};
    for (ll i = 0; i < N; i++) {
        if (S[i] == 0) continue;
        ll message = S[i] - 1;
        ll b = N - i - 1;
        ll val = message % 2;
        ll over_pos = message / 2;
        if (over_pos >= 1) {
            overwrite[over_pos - 1] = i;
        }
        encoded += (val << b);
    }

    assert(encoded < N * N);
    array<ll, 2> ans = {encoded / N, encoded % N};
    for (ll i = 0; i < 2; i++) {
        if (overwrite[i] != -1) ans[i] = overwrite[i];
    }
    
    return {ans[0], ans[1]};
}

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