Submission #1255192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255192		otarius	Migrations (IOI25_migrations)	C++20	79.12 / 100	1823 ms	1096 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rngl(chrono::steady_clock::now().time_since_epoch().count());

// #define int long long
// #define int unsigned long long

// #define ordered_set(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
// #define ordered_multiset(T) tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>

// const ll mod = 1e9 + 7;
// const ll mod = 998244353;

const ll inf = 1e9;
const ll biginf = 1e18;
const int maxN = 10005;

vector<int> g[maxN];
int dist[maxN], x, y = 1;
int bfs(int x, int y) {
    for (int i = 0; i < maxN; i++) dist[i] = inf;
    queue<int> q; q.push(x); dist[x] = 0;
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int u : g[v]) {
            if (dist[u] == inf) {
                dist[u] = dist[v] + 1; q.push(u);
            }
        }
    } return dist[y];
}
int send_message(int n, int i, int pi) {
    g[pi].pb(i); g[i].pb(pi);
    if (i < n - 21) {
        if (bfs(i, x) > bfs(x, y)) y = i;
        if (bfs(i, y) > bfs(x, y)) x = i;
        return 0;
    }

    if (i < n - 14) {
        if (bfs(i, x) > bfs(x, y)) {
            y = x; x = i; return 4;
        }

        if (bfs(i, y) > bfs(x, y)) {
            x = i; return 4;
        }

        int tmp = x, pos = n - i - 15;
        while (pos--) tmp /= 4;
        return (tmp % 4);
    }

    int tmp = y, pos = n - i - 1;
    while (pos--) tmp /= 2;

    if (bfs(i, x) > bfs(x, y)) {
        y = i; return 0;
    }

    if (bfs(i, y) > bfs(x, y)) {
        x = i; return tmp % 2 + 1;
    }

    return tmp % 2 + 3;
}

pair<int, int> longest_path(vector<int> s) {
    int x = 0, y = 0, n = s.size();
    for (int i = 1; i < n; i++) {
        if (i < n - 21) continue;
        if (i < n - 14) {
            if (s[i] == 4) x = i;
            else {
                int tmp = x, pos = n - i - 15, cur = 1;
                while (pos--) tmp /= 4, cur *= 4;
                x = x - (tmp % 4) * cur + s[i] * cur;
            } continue;
        }
        
        if (s[i] == 0) y = i;
        else if (s[i] <= 2) {
            x = i;
            int tmp = y, pos = n - i - 1, cur = 1;
            while (pos--) tmp /= 2, cur *= 2;
            y = y - (tmp % 2) * cur + (s[i] - 1) * cur;
        } else {
            int tmp = y, pos = n - i - 1, cur = 1;
            while (pos--) tmp /= 2, cur *= 2;
            y = y - (tmp % 2) * cur + (s[i] - 3) * cur;
        }
    }


    return {x, y};
}
// int main() {
//   int N;
//   assert(1 == scanf("%d", &N));

//   std::vector<int> P(N, 0);
//   for (int i = 1; i < N; ++i) {
//     assert(1 == scanf("%d", &P[i]));
//   }

//   std::vector<int> S(N, 0);
//   for (int i = 1; i < N; ++i) {
//     S[i] = send_message(N, i, P[i]);
//   }
//   for (int i = 1; i < N; ++i) {
//     printf("%d%c", S[i], " \n"[i + 1 == N]);
//   }

//   auto [U, V] = longest_path(S);
//   printf("%d %d\n", U, V);
//   fclose(stdout);

//   return 0;
// }

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