Submission #1251567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251567		fv3	Migrations (IOI25_migrations)	C++20	30 / 100	28 ms	576 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 10000;
vector<int> P(N), dist(N);

int mx_dist = 0;
int B = 0;

bool new_best = false;

int send_message(int N_, int i, int Pi) {
    assert(N_ == 10000);

    P[i] = Pi;
    dist[i] = dist[Pi] + 1;

    if (i >= N - 20) {
        if (dist[i] > mx_dist) {
            mx_dist = dist[i];
            new_best = true;
            return 2;
        } else if (new_best) {
            return 0;
        }

        int b = i - (N - 20);
        return ((B & (1 << b)) ? 1 : 0);
    } else if (dist[i] > mx_dist) {
        B = i;
        mx_dist = dist[i];
    }

    return 0;
}

pair<int, int> longest_path(vector<int> S) {
    int b = 0;

    for (int i = 0; i < 20; i++) {
        int j = N - 20 + i;
        if (S[j] == 2) {
            b = j;
        } else {
            b |= (S[j] << i);
        }
    }

    return {0, b};
}

//#include "grader.cpp"

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