제출 #1251239

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251239		bronze_coder	Migrations (IOI25_migrations)	C++20	0 / 100	1 ms	436 KiB

migrations

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

int dist[10000];
int high = 0;
const int abcd = 3;
int P[10000];
int binary[10000][14];
int first = 0;
int second = 0;


int lca(int i,int j){
    if(dist[i]<dist[j]){
        swap(i,j);
    }
    for(int k=13;k>=0;k--){
        if(dist[i]-(1<<k)>=dist[j]){
            i = binary[i][k];
        }
    }
    if(i==j){
        return i;
    }
    for(int k=13;k>=0;k--){
        if(binary[i][k]!=binary[j][k]){
            i = binary[i][k];
            j = binary[j][k];
        }
    }
    return P[i];
}

int distance(int i,int j){
    return dist[i]+dist[j]-2*dist[lca(i,j)];
}

int send_message(int N, int i, int Pi){
    dist[i] = dist[Pi]+1;

    P[i] = Pi;
    binary[i][0] = Pi;
    for(int j=1;j<14;j++){
        binary[i][j] = binary[binary[i][j-1]][j-1];
    }
    int x = distance(first,second);
    if(distance(first,i)>x){
        second = i;
    }
    if(distance(second,i)>x){
        first = i;
    }
    cout << first << " " << second << endl;
    if(i>=N-2*abcd){
        int x = (N-1-i)/2;
        if(i&1){
            if(first==i){
                return 0;
            }
            int a = 1;
            if(second==i){
                a += 2;
            }
            if(first&(1<<x)){
                a++;
            }
            return a;
        }
        else{
            if(second==i){
                return 0;
            }
            int a = 1;
            if(first==i){
                a += 2;
            }
            if(second&(1<<x)){
                a++;
            }
            return a;
        }
    }
    return 0;


}


pair<int,int> longest_path(vector<int> S){
    int n = S.size();

    pair<int,int> ans;
    ans.first = -1;
    ans.second = -1;
    int a = 0;
    int b = 0;
    for(int i=n-2*abcd;i<n;i++){
        if(i&1){
            if(S[i]==0){
                ans.first = i;
            }
            if(S[i]>=3){
                ans.second = i;
            }
            if(S[i]==2||S[i]==4){
                a += (1<<(n-1-i)/2);
            }
        }
        else{
            if(S[i]==0){
                ans.second = i;
            }
            if(S[i]>=3){
                ans.first = i;
            }
            if(S[i]==2||S[i]==4){
                b += (1<<(n-1-i)/2);
            }
        }
    }
    if(ans.first==-1){
        ans.first = a;
    }
    if(ans.second==-1){
        ans.second = b;
    }
    return ans;
}

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