Submission #1258095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258095		jamesbamber	Migrations (IOI25_migrations)	C++20	30 / 100	28 ms	456 KiB

migrations

#include "migrations.h"
#include <iostream>

using namespace std;

int LOG = 14;

int d1, d2;
int to_send;
vector<int> depth;

int send_message(int N, int i, int Pi) {
    if(i == 1) {
        depth.assign(N, 0);
        d1 = 0;
    }

    bool new_diam = 0;

    depth[i] = depth[Pi] + 1;
    if(depth[i] > depth[d2]) d2 = i, new_diam = 1;

    if(i + LOG < N) return 0;

    if(i + LOG == N) to_send = d2;
    int bit = N - i - 1;

    cerr << to_send << endl;

    int message = 1;
    message += (to_send >> bit) & 1;
    if(new_diam) message += 2;

    return message;
}

std::pair<int, int> longest_path(std::vector<int> S) {
    int N = S.size();

    int edge = -1;
    for(int i=0; i<N; i++) {
        S[i]--;
        if(S[i] < 0) continue;
        if((S[i] >> 1) & 1) edge = i;
    }

    if(edge != -1) return {0, edge};

    edge = 0;

    for(int bit=0; bit<LOG; bit++) {
        int i = N - 1 - bit;

        edge += (S[i] % 2) << bit; 
    }

    return {0, edge};
}

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