Submission #1251962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251962		canadavid1	Migrations (IOI25_migrations)	C++20	30 / 100	29 ms	636 KiB

migrations

#include "migrations.h"


/*
    to get some longest path: choose the two oldest candidates
    upon update, at one of the previous is still included, and the other is the new node
    => Z = 2, M=N solution

*/

std::vector<int> P{{0}},d{{0}},gp{{0}};
int curA=0,curD=0;
int lca(int a,int b) {
    int ct = 0;
    if (d[a] < d[b]) std::swap(a,b);
    while(d[a] > d[b]) 
        if (d[gp[a]] >= d[b]) a = gp[a];
        else a = P[a];
    while (a != b)
        if (gp[a] != gp[b]) a = gp[a],b=gp[b];
        else a = P[a],b=P[b];
    return a;
}
int dist(int a,int b) {
    return d[a] + d[b] - 2*d[lca(a,b)];
}

// using the last M messages, encode which two
// can change during, but then do some skip-code thing
/*
    subtask 1:
    last M messages encode the bits of the end. if it suddenly changes to current node, encode with 0.


*/
const int M = 16; 
int send_message(int N, int i, int Pi) { // this can retain information across calls
    P.push_back(Pi);
    d.push_back(d[Pi]+1);
    if(d[gp[gp[Pi]]] - 2*d[gp[Pi]] + d[Pi] == 0) gp.push_back(gp[gp[Pi]]);
    else gp.push_back(Pi);
    if (d[i] > curD) {curA = i;curD = d[i];}
    int idx = N-1-i;
    if (idx >= M) return 0;
    if(curA == i) return 2;
    if (curA >= N-M) return 0;
    return (curA >> idx) & 1;
}

std::pair<int, int> longest_path(std::vector<int> S) {
    int curA = 0;
    const int N = S.size();
    for(int idx = 0; idx < M; idx++) {
        auto v = S[N-1-idx];
        if(v == 2) return {0,N-1-idx};
        curA |= v << idx;
    }
    return {0,curA};
}

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