Submission #1305712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305712		anango	Migrations (IOI25_migrations)	C++20	10 / 100	45 ms	2864 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;

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]);
    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)];
}

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-4) {
        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];
    });
    pair<int,int> diameter = {furthest, indices.back()};
    if (site>=N-3) {
        return furthest;
    }
    assert(false);
}

std::pair<signed, signed> longest_path(std::vector<signed> S) {
    int furthest = S.back();
    return {0, furthest};
}

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