Submission #1258110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258110		jamesbamber	Migrations (IOI25_migrations)	C++20	0 / 100	612 ms	1160 KiB

migrations

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

using namespace std;

int LOG = 14;

int d1, d2;
int to_send_1, to_send_2;
int diam_length;
vector<vector<int>> ad;
vector<int> dist;

void dfs(int v, int p) {
    if(p != -1) dist[v] = dist[p] + 1;

    for(int u: ad[v]) {
        if(u == p) continue;
        dfs(u, v);
    }
}

int send_message(int N, int i, int Pi) {
    if(i == 1) {
        ad.resize(N);
        d1 = 0, d2 = 0;
        diam_length = 0;
    }

    int new_diam = 0; // 0 if not new, 1 if new d1 2 if new d2

    ad[i].push_back(Pi);
    ad[Pi].push_back(i);

    dist.assign(N, 0);
    dfs(i, -1);

    int mx_dist = *max_element(dist.begin(), dist.end());

    if(mx_dist > diam_length) {
        diam_length = mx_dist;
        if(dist[d2] == mx_dist) {
            new_diam = 1;
            d1 = i;
        }
        else if(dist[d1] == mx_dist) {
            new_diam = 2;
            d2 = i;
        }
    }

    if(i + 2*LOG < N) return 0;
    if(i + 2*LOG == N) to_send_1 = d1, to_send_2 = d2;

    
    int message = 1;
    // message modulo 2 gives info on diam
    // message/3 gives info on new diam
    
    if(i + LOG < N) {
        // send 1
        int bit = N - LOG - i - 1;
        message += (to_send_1 >> bit) & 1;
        message += 2*new_diam;
    }
    else {
        // send 2
        int bit = N - i - 1;
        message += (to_send_2 >> bit) & 1;
        message += 2*new_diam;
    }

    cerr << to_send_1 << " " << to_send_2 << endl;

    return message;
}

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

    int d1 = 0, d2 = 0;

    for(int i=0; i<N; i++) S[i]--;

    for(int bit=0; bit<LOG; bit++) {
        int i1 = N - LOG - 1 - bit;
        d1 += (S[i1] % 2) << bit; 

        int i2 = N - 1 - bit;
        d2 += (S[i2] % 2) << bit; 
    }

    for(int i=N-2*LOG; i<N; i++) {
        if(S[i] < 0) continue;
        if(S[i]/3 == 1) d1 = i;
        if(S[i]/3 == 2) d2 = i;
    }

    return {d1, d2};
}

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