제출 #1306287

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306287		anango	이주 (IOI25_migrations)	C++20	0 / 100	69 ms	3048 KiB

migrations

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

int K = 14;
int n;
vector<int> parent;
vector<int> depth;
vector<vector<int>> adjlist;
vector<vector<int>> lift;
pair<int,int> relev_diameter;
pair<int,int> curr_diameter;
int curr_best_dist = -1;

void prv(vector<int> v) {
    for (auto i:v) {
        cout << i <<" ";
    }
    cout << endl;
}

int LCA(int u, int v) {
    if (u==v) return u;
    if (depth[u] > depth[v]) swap(u,v);
    //u is now at a lower depth than v
    for (int i=K-1; i>=0; i--) {
        if (depth[v] >= depth[u] + (1LL<<i)) {
            v = lift[v][i];
        }
    }
    assert(depth[u] == depth[v]);
    if (u==v) return u;
    for (int i=K-1; i>=0; i--) {
        if (lift[u][i] != lift[v][i]) {
            u = lift[u][i];
            v = lift[v][i];
        }
    }
    u = parent[u];
    v = parent[v];
    assert(u==v);
    return u;

}

int dist(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[LCA(u, v)];
}

vector<int> base(int n, int base, int length) {
    vector<int> res;
    for (int i=0; i<length; i++) {
        res.push_back(n%base);
        n /= base;
    }
    reverse(res.begin(), res.end());
    return res;
}

int antibase(vector<int> based, int base) {
    int su = 0;
    for (int i=0; i<based.size(); i++) {
        su += based[i]; 
        if (i+1 != based.size()) su *= base;
    }
    return su;
}

pair<int,int> diameter;
signed send_message(signed N, signed site, signed Pi) {
    n=N;
    if (site==1) {
        parent = vector<int>(N, -1);
        parent[0] = 0; //careful!
        depth = vector<int>(N, 0);
        adjlist = vector<vector<int>>(N);
        lift = vector<vector<int>>(N, vector<int>(K, -1));
        for (int i=0; i<K; i++) lift[0][i] = 0;
    }
    parent[site] = Pi;
    lift[site][0] = parent[site];
    depth[site] = depth[parent[site]] + 1;
    adjlist[site].push_back(parent[site]);
    adjlist[parent[site]].push_back(site);
    for (int i=1; i<K; i++) {
        lift[site][i] = lift[lift[site][i-1]][i-1];
        //cout << i <<" " << site <<" " << depth[site] <<" " << " " << depth[lift[site][i]] << " " << lift[site][i] << endl;
        assert(depth[lift[site][i]] <= depth[site]);
        assert(depth[lift[site][i]] >= depth[site] - (1LL<<i));
        if (lift[site][i] != 0) {
            assert(depth[lift[site][i]] == depth[site] - (1LL<<i));
        }
    }
    if (site<N-28) {
        return 0;
    }
    //cout << "CURRENTLY PROCESSING " << site <<" " << curr_best_dist << " " << curr_diameter.first <<" " << curr_diameter.second << endl;
    if (site == N-28) {
        int r = site+1;
        vector<int> indices(r); iota(indices.begin(), indices.end(), (int)0);
        sort(indices.begin(), indices.end(), [&](const int u, const int v) {
            return depth[u] < depth[v];
        });
        int furthest = indices.back();
        vector<int> furthest_distances(r); for (int i=0; i<r; i++) furthest_distances[i] = dist(furthest, i);
        sort(indices.begin(), indices.end(), [&](const int u, const int v) {
            return furthest_distances[u] < furthest_distances[v];
        });
        //cout << "SITE " << site << "FURTHEST " << furthest << endl;
        //prv(furthest_distances);
        diameter = {furthest, indices.back()};
        int dist = furthest_distances[indices.back()];
        if (diameter.first > diameter.second) diameter = {diameter.second, diameter.first};
        relev_diameter = diameter;
        curr_best_dist = dist;
    }
    if (site <= N-15 && site >= N-28) {
        //so 28 to 15
        //28 to 22 is the 1st number
        //21 to 15 is the 2nd number
        int n1 = relev_diameter.first;
        int n2 = relev_diameter.second; //keep the order of the parts consistent
        curr_diameter = relev_diameter;
        vector<int> first_number = base(n1, 4, 7);
        vector<int> second_number = base(n2, 4, 7);
        if (site < N-21) {
            return first_number[site-(N-28)];
        }
        else {
            return second_number[site-(N-21)];
        }
    }
    //now we're in the last 14 indices
    int ind1 = curr_diameter.first;
    int ind2 = curr_diameter.second;
    int c = N - (2*(N-site));
    int d = c + 1;
    int r = d + 1;
    //cout << "AIMING "<< "PREV " << ind1 <<" " << ind2 <<" NEW CANDIDATES " << c << " " << d << endl;
    //we need to check if any of these have superseded the current diameter
    //or if they together form a better diameter
    vector<int> dist1(r); for (int i=0; i<r; i++) dist1[i] = dist(ind1, i);
    vector<int> dist2(r); for (int i=0; i<r; i++) dist2[i] = dist(ind2, i);
    vector<int> distc(r); for (int i=0; i<r; i++) distc[i] = dist(c, i);
    vector<int> distd(r); for (int i=0; i<r; i++) distd[i] = dist(d, i);
    assert(distc[d] == distd[c]);
    assert(dist1[ind2] == dist2[ind1]);
    //cout << r <<" "<< c <<" " << d << endl;
    vector<int> message_pots = {curr_best_dist, dist2[c], dist2[d], dist1[c], dist1[d], dist1[ind2]};
    int maximum = *max_element(message_pots.begin(), message_pots.end());
    //cout << "TES " << maximum <<" " << *max_element(dist1.begin(), dist1.end()) << endl;
    assert(maximum >= *max_element(dist1.begin(), dist1.end()));
    curr_best_dist = maximum;
    //int relev_index = -1;
    for (int i=0; i<6; i++) {
        if (message_pots[i] == maximum) {
            if (i==5) {
                curr_diameter = {c, d};
            }
            else if (i==1) {
                curr_diameter = {c, curr_diameter.second};
            }
            else if (i==3) {
                curr_diameter = {curr_diameter.first, d};
            }
            else if (i==2) {
                curr_diameter = {d, curr_diameter.second};
            }
            else if (i==4) {
                curr_diameter = {curr_diameter.first, c};
            }
            return i;
        }
    }

    //if (site==5) cout << "LC" <<" " << LCA(5,1) << endl;
    //if (N-27 <= site && site <= N-)
    assert(false);
}

std::pair<signed, signed> longest_path(std::vector<signed> S) {
    int N = S.size();
    //cout << N << endl;
    vector<int> first_number(S.begin()+(N-28), S.begin()+(N-21));
    assert(first_number.size() == 7);
    vector<int> second_number(S.begin()+(N-21), S.begin()+(N-14));
    assert(second_number.size() == 7);
    //prv(first_number);
    //prv(second_number);
    int real_n1 = antibase(first_number, 4);
    int real_n2 = antibase(second_number, 4);
    pair<int,int> curdiam = {real_n1, real_n2};
    for (int i=N-14; i<N; i++) {
        int ind1 = N - (2*(N-i));
        int ind2 = ind1 + 1;
        if (S[i]==5) {
            curdiam = {ind1, ind2};
        }
        else if (S[i]==1) {
            curdiam = {ind1, curdiam.second};
        }
        else if (S[i]==3) {
            curdiam = {curdiam.first, ind1};
        }
        else if (S[i]==2) {
            curdiam = {ind2, curdiam.second};
        }
        else if (S[i]==4) {
            curdiam = {curdiam.first, ind2};
        }
    }
    return {curdiam.first, curdiam.second};
}

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