Submission #1306266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306266		anango	이주 (IOI25_migrations)	C++20	0 / 100	62 ms	3040 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;
deque<pair<int,int>> diameters;
deque<int> lag_queue;

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;
    }
    //find any diameter
    //say that the first r of the n vertices are active at this point
    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()};
    if (diameter.first > diameter.second) diameter = {diameter.second, diameter.first};
    diameters.push_back(diameter); //first diameter is for index N-28, and the last is for index N-1
    if (site < N-14) {
        //so 28 to 15
        //28 to 22 is the 1st number
        //21 to 15 is the 2nd number
        int n1 = diameters[0].first;
        int n2 = diameters[0].second; //keep the order of the parts consistent
        vector<int> first_number = base(n1, 4, 7);
        vector<int> second_number = base(n2, 4, 7);
        lag_queue.push_back(site);
        if (site < N-21) {
            return first_number[site-(N-28)];
        }
        else {
            return second_number[site-(N-21)];
        }
    }
    else {
        lag_queue.push_back(site);
        assert(lag_queue.size());
        int a,b;
        int message = 0;
        a = lag_queue.front(); lag_queue.pop_front(); b = lag_queue.front(), lag_queue.pop_front();
        //int n1 = diameters[0].first;
        //int n2 = diameters[0].second;
        int r1 = diameters[0].first;
        int r2 = diameters[0].second;
        if ((r1 == a && r2 == b) || (r1 == b && r2 == a)) {
            message = 5; //note here, we sort the values always
        }
        else if (r1 == a) {
            message = 1;
        }
        else if (r2 == a) {
            message = 2;
        }
        else if (r1 == b) {
            message = 3;
        }
        else if (r2 == b) {
            message = 4;
        }
        else {
            message = 0;
        }
        diameters.push_front(diameter);
        return message;
    }
    //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();
    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);
    return {real_n1, real_n2};
}

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