Submission #1252040

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

migrations

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

/*
    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,curB=1,curD=1;
enum {
    neither,
    cA,
    cB,
    both
} seen;

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.

    M = 29 Z <= 4:
        14+14 bits to encode ends: first and second. 
            If second is interrupted by POI:  +1 end bit direction
            If first is interrupted by POI:  +1 end bit.

        0/1 -> normal bit
        2/3 -> POI + normal bit
        4 -> second POI. mode switch.
        after 4, have seen both. 2 -> new of the older, 4 -> new of the newer.
        
        else:
            1 extra:
                if none were interrupted:
                    0 -> normal
                    1 -> this is end A
                    2 -> this is end B
                if some were interrupted:
                    0/1 -> which end is to be kept (normal)
                    2/3 -> this is one end, which end is to be kept
                    4 -> this is the second POI. last 2/3 is the first one.

*/
const int M = 29; 
bool B_4 = false;
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);
    bool newA = dist(i,curB) > curD;
    bool newB = !newA && dist(i,curA) > curD;
    if (newB) {
        curD++;
        curB = i;
    }
    else if (newA) {
        curD++;
        curA = i;
    }
    if (i < N-M) return 0;
    //STDCERR << i << " " << curA << " " << curB << " " << newA << " " << newB << " " << seen << "\n";
    int idx = N-i;
    if (idx == 1) {
        switch (seen)
        {
        case neither:
            return 2*newB + newA;
        
        case cA:
            if (newB) return 4;
            return 2*newA;
        case cB:
            if (newA) return 4;
            return 2*newB+1;
        case both:
            return 2*newB + newA;
        }
    }
    int retval = 0;
    if(idx & 1) {
        retval = (curA >> (idx / 2 - 1))&1;
    } else {
        retval = (curB >> (idx / 2 - 1))&1;
    }
    if (seen == both) retval = 0;
    if (newA) {
        switch (seen)
        {
        case neither:
        case cA:
            //STDCERR << " nA cA\n";
            retval += 2;
            seen = cA;
            break;
        case cB:
            //STDCERR << " nA cB\n";
            seen = both;
            retval = 4;
            break;
        case both:
            //STDCERR << " nA b\n";
            retval = 2 - B_4;
            break;
        }
    }
    if (newB) {
        switch (seen)
        {
        case neither:
        case cB:
            //STDCERR << " nB cB\n";
            retval += 2;
            seen = cB;
            break;
        case cA:
            //STDCERR << " nB cA\n";
            seen = both;
            retval = 4;
            B_4 = true;
            break;
        case both:
            //STDCERR << " nB cB\n";
            retval = 1 + B_4;
            break;
        }
    }
    return retval;
}

std::pair<int, int> longest_path(std::vector<int> S) {
    //STDCERR << "---------\n";
    int cur[2] = {0,0};
    int prev = -1;
    const int N = S.size();
    bool any_4 = false;
    for(int i = N-M; i < N; i++) any_4 |= S[i] == 4;
    //STDCERR << "any_4: " << any_4 << "\n";
    if (any_4) {
        // both are >= N-M
        int A = -1;
        int i;
        for(i = N-M; i < N; i++) {
            if (S[i] < 2) continue;
            if (S[i] == 4) break;
            A = i;  
        }
        int B = i;
        for(;i < N; i++) {
            if (S[i] == 1) A = i;
            if (S[i] == 2) B = i;
        }
        return {A,B};
    }
    for(int idx = M; idx > 1; idx--) {
        if (S[N-idx] >= 2) prev = N-idx;
        cur[idx&1] |= (S[N-idx]&1) << (idx / 2 - 1);
    }
    //STDCERR << cur[0] << " " << cur[1] << " " << prev << "\n";
    if (prev == -1) {
        switch (S.back())
        {
        case 0:
            return {cur[0],cur[1]};
        case 1:
            return {N-1,cur[1]};
        case 2:
            return {cur[0],N-1};
        default:
            return {-1,-1};
        }
    }
    if (S.back() > 1) prev = N-1;
    return {prev,cur[S.back()&1]};
    
}

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