Submission #1256175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256175		TheScrasse	Migrations (IOI25_migrations)	C++20	30 / 100	28 ms	456 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> opt = {-INF, -1};

int send_message(int N, int i, int Pi) {
    // 30 punti
    if (parent.empty()) {
        parent.resize(N, -1);
        dist.resize(N, 0);
    }
    
    dist[i] = dist[Pi] + 1;
    opt = max(opt, {dist[i], i});

    if (i < N - 40) return 0;

    ll b = N - 1 - i;
    auto [max_dist, id] = opt;
    if (id == i) return 3;
    
    return ((id >> b) & 1) + 1;
}

std::pair<int, int> longest_path(std::vector<int> S) {
    ll N = S.size();
    for (ll i = N - 1; i >= 0; i--) {
        if (S[i] == 3) return {0, i};
    }

    ll ans = 0;
    for (ll i = N - 40; i < N; i++) {
        ll b = N - 1 - i;
        ll val = S[i] - 1;
        ans += (val << b);
    }

    return {0, ans};
}

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