Submission #1296888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296888		Unforgettablepl	Migrations (IOI25_migrations)	C++20	79.12 / 100	41 ms	1452 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
    vector<vector<int>> adj;
    pair<int,int> dfs(int x,int p){
        pair<int,int> ans = {-1,x};
        for(int&i:adj[x])if(i!=p){
            ans = max(ans,dfs(i,x));
        }
        ans.first++;
        return ans;
    }
    int currL,currR,currBest;
}


int send_message(int N, int i, int Pi) {
    if(i==1)adj.resize(N);
    adj[i].emplace_back(Pi);
    adj[Pi].emplace_back(i);
    if(i==9978){
        currL = dfs(0,-1).second;
        currR = dfs(currL,-1).second;
        currBest = dfs(currL,-1).first;
        return 0;
    }
    if(i>9978 and i<9986){ // sending L phase
        if(dfs(currR,-1).first!=currBest){
            // replacing L
            currL = i;
            currBest++;
            return 0;
        }
        if(dfs(currL,-1).first!=currBest){
            currR = i;
            currBest++;
        }
        int bits = (i-9978-1)*2;
        return ((currL>>bits)&3)+1;
    }
    if(i>9985){ // sending R phase
        int offset = 0;
        if(dfs(currR,-1).first!=currBest){
            // replacing L
            currL = i;
            currBest++;
            offset = 2;
        }
        if(dfs(currL,-1).first!=currBest){
            currR = i;
            currBest++;
            return 0;
        }
        int bits = (i-9985-1);
        return (((currR>>bits)&1) + offset)+1;
    }
    return 0;
}

pair<int,int> longest_path(vector<int> S){
    int currL = 0;
    int currR = 0;
    for(int i=9979;i<9986;i++){
        // reading currL
        if(S[i]==0)currL=i;
        else {
            int c = S[i]-1;
            int bits = (i-9978-1)*2;
            currL|=c<<bits;
        }
    }
    for(int i=9986;i<10000;i++){
        // reading currR
        if(S[i]==0)currR=i;
        else {
            int c = S[i]-1;
            if(c&2){
                currL = i;
                c&=1;
            }
            int bits = (i-9985-1);
            currR|=c<<bits;
        }
    }
    return {currL,currR};
}

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