Submission #1305117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305117		Math4Life2020	Migrations (IOI25_migrations)	C++20	0 / 100	698 ms	1376 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;

const ll Nm = 10000; const ll Mm = 28;
const ll INF = 1e8;

vector<ll> fadj[Nm];
ll radj[Nm];
vector<ll> adj[Nm];

pair<ll,vector<ll>> mdist(ll x0) {
    vector<ll> cdist(Nm,INF);
    cdist[x0]=0;
    queue<ll> q0;
    q0.push(x0);
    while (!q0.empty()) {
        ll y = q0.front(); q0.pop();
        for (ll z: adj[y]) {
            if (cdist[z]==INF) {
                cdist[z]=cdist[y]+1;
                q0.push(z);
            }
        }
    }
    ll cmax = -1; vector<ll> cv;
    for (ll x=0;x<Nm;x++) {
        if (cdist[x]!=INF) {
            if (cdist[x]>=cmax) {
                if (cdist[x]>cmax) {
                    cmax = cdist[x];
                    cv.clear();
                }
                cv.push_back(x);
            }
        }
    }
    return {cmax,cv};
}

ll MTR = 0;

pair<ll,pii> gld() {
    pii pc = {-1,-1};
    ll dc = -1;
    for (ll x=0;x<Nm;x++) {
        auto A0 = mdist(x);
        if (A0.first>dc) {
            dc = A0.first;
            pc = {x,A0.second[0]};
        }
    }
    return {dc,pc};
}

int send_message(int N, int i, int Pi) {
    radj[i]=Pi;
    fadj[Pi].push_back(i);
    adj[Pi].push_back(i);
    adj[i].push_back(Pi);
    ll dc; pii pc;
    if (i==(N-Mm)) {
        auto A0 = gld();
        dc = A0.first; pc = A0.second;
        MTR = ((pc.first)<<14)+pc.second;
    }
    if (i>=(N-Mm)) {
        ll bt = (MTR>>(i-N+Mm))&1;
        ll ct = -1;
        auto A0 = mdist(i);
        ll dn = A0.first; 
        vector<ll> vc = A0.second;
        if (dn<=dc) {
            ct = 0;
        } else {
            dc = dn;
            for (ll x: vc) {
                if (x==pc.first) {
                    pc.second = i;
                    ct = 1;
                    break;
                }
                if (x==pc.second) {
                    pc.first = i;
                    ct = 2;
                    break;
                }
            }
            assert(ct!=-1);
        }
        return (3*bt+ct);
    }
    return 0;
}

pair<int,int> longest_path(vector<int> S) {
    ll N = S.size();
    vector<ll> bv,cv;
    for (ll i=(N-Mm);i<N;i++) {
        ll bt = S[i]/3; ll ct = S[i]%3;
        bv.push_back(bt); cv.push_back(ct);
    }
    pii pc = {0,0};
    for (ll i=0;i<14;i++) {
        pc.second += ((bv[i])<<i);
        pc.first += ((bv[i+14])<<i);
    }
    for (ll i=(N-Mm);i<N;i++) {
        ll i1 = i-(N-Mm);
        if (cv[i1]==1) {
            pc.second=i;
        } else if (cv[i1]==2) {
            pc.first=i;
        }
    }
    return pc;
}

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