제출 #1305135

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305135		Math4Life2020	Migrations (IOI25_migrations)	C++20	65 / 100	1080 ms	1580 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};
}

ll dc; pii pc;

int send_message(int N, int i, int Pi) {
    if (i==0) {
        for (ll t=0;t<Nm;t++) {
            fadj[t].clear();
            adj[t].clear();
        }
    }
    assert(Pi>=0);
    assert(Pi<i);
    radj[i]=Pi;
    fadj[Pi].push_back(i);
    adj[Pi].push_back(i);
    adj[i].push_back(Pi);
    if (i==(N-Mm)) {
        auto A0 = gld();
        dc = A0.first; pc = A0.second;
        // cout << "dc="<<dc<<"\n";
        // cout << "pc="<<pc.first<<","<<pc.second<<"\n";
        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;
            // cout << "i="<<i<<", dn="<<dn<<"\n";
            for (ll x: vc) {
                // cout << "x term: "<<x<<"\n";
                // cout << "pc rn = "<<pc.first<<","<<pc.second<<"\n";
                if (x==pc.first) {
                    pc.second = i;
                    //cout << "f1\n";
                    ct = 1;
                    break;
                } else if (x==pc.second) {
                    pc.first = i;
                    //cout << "f2\n";
                    ct = 2;
                    break;
                }
            }
            assert(ct!=-1);
        }
        return (3*bt+ct);
    }
    return 0;
}

pair<int,int> longest_path(vector<int> S) {
    vector<ll> bv,cv;
    for (ll i=(Nm-Mm);i<Nm;i++) {
        ll bt = ((ll)S[i])/3; ll ct = ((ll)S[i])%3;
        // cout << "bt="<<bt<<",ct="<<ct<<"\n";
        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=(Nm-Mm);i<Nm;i++) {
        ll i1 = i-(Nm-Mm);
        if (cv[i1]==1) {
            pc.second=i;
        } else if (cv[i1]==2) {
            pc.first=i;
        }
    }
    return pc;
}

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