#1149436 (C++23) No.5023 Airlines Optimization

• 問題: No.5023 Airlines Optimization
• ユーザー: mogura3.0
• 提出日時: 2026-02-25 23:59:12
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 906 ms / 1,000 ms
• コード長: 14,651 bytes
• コンパイル時間: 4,280 ms
• コンパイル使用メモリ: 269,316 KB
• 実行使用メモリ: 7,848 KB
• スコア: 44,237,313
• 最終ジャッジ日時: 2026-02-26 00:02:19
• 合計ジャッジ時間: 100,165 ms
• ジャッジサーバーID （参考情報）: judge7 / judge3

ファイルパターン	結果
other	AC * 100

ソースコード

#include <algorithm>
#include <array>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <limits>
#include <string>
#include <utility>
#include <vector>

using namespace std;

struct City {
    int x, y;
    long long w;
};

struct Flight {
    int u, v;   // 0-indexed cities
    int s, t;   // minutes from 00:00
};

struct PlanePlan {
    int spoke;      // 0-indexed city, must be != hub
    int phaseSlot;  // 0..11 => 0..55 minutes offset from 06:00
    bool startHub;
};

static constexpr int DAY_START = 6 * 60;      // 06:00
static constexpr int DAY_END = 21 * 60;       // 21:00
static constexpr int Q = 21;                  // 11:00..21:00 every 30 min
static constexpr int INF_NEG = -1'000'000'000;

int parse_time_token(const string& tok) {
    auto pos = tok.find(':');
    if (pos == string::npos) return stoi(tok);  // fallback
    int hh = stoi(tok.substr(0, pos));
    int mm = stoi(tok.substr(pos + 1));
    return hh * 60 + mm;
}

void print_time(int minute) {
    int hh = minute / 60;
    int mm = minute % 60;
    cout << setw(2) << setfill('0') << hh << ':'
         << setw(2) << setfill('0') << mm;
    cout << setfill(' ');
}

int calc_duration_minutes(const City& c1, const City& c2) {
    // Need exact 5-minute ceil of (3 * distance / 40 + 40).
    long long dx = (long long)c1.x - (long long)c2.x;
    long long dy = (long long)c1.y - (long long)c2.y;
    long long d2 = dx * dx + dy * dy;

    // Max possible distance <= 2000 => duration <= 190.
    for (int dur = 40; dur <= 300; dur += 5) {
        long long lhs = 40LL * dur - 1600LL;  // >= 0
        if (lhs * lhs >= 9LL * d2) return dur;
    }
    return 300;  // unreachable under constraints
}

struct Solver {
    int N = 0, R = 0;
    int M = 0, K = 0;
    vector<City> cities;
    vector<Flight> squareFlights;

    vector<vector<int>> dur;
    vector<vector<unsigned char>> eligible;
    vector<vector<unsigned long long>> pairW;
    unsigned __int128 denomWeight = 0;  // all eligible OD weights * Q

    array<int, Q> targetTimes{};
    vector<int> sqLatest;  // [q][dst][src] flattened

    vector<int> hubOrder;
    vector<vector<int>> spokeOrder;  // per hub, sorted candidates

    chrono::steady_clock::time_point t0;
    double internalTimeLimitSec = 0.90;  // deep-dive preset

    int idx3(int q, int dst, int src) const {
        return (q * N + dst) * N + src;
    }

    bool time_over() const {
        double elapsed = chrono::duration<double>(chrono::steady_clock::now() - t0).count();
        return elapsed >= internalTimeLimitSec;
    }

    void read_input() {
        cin >> N >> R;
        cities.resize(N);
        for (int i = 0; i < N; ++i) {
            cin >> cities[i].x >> cities[i].y >> cities[i].w;
        }

        cin >> M;
        squareFlights.reserve(M);
        for (int i = 0; i < M; ++i) {
            int a, b;
            string sTok, tTok;
            cin >> a >> sTok >> b >> tTok;
            int s = parse_time_token(sTok);
            int t = parse_time_token(tTok);
            squareFlights.push_back(Flight{a - 1, b - 1, s, t});
        }

        cin >> K;

        for (int q = 0; q < Q; ++q) targetTimes[q] = 11 * 60 + 30 * q;
    }

    void precompute_geometry() {
        dur.assign(N, vector<int>(N, 0));
        eligible.assign(N, vector<unsigned char>(N, 0));
        pairW.assign(N, vector<unsigned long long>(N, 0));

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (i != j) dur[i][j] = calc_duration_minutes(cities[i], cities[j]);

                long long dx = (long long)cities[i].x - (long long)cities[j].x;
                long long dy = (long long)cities[i].y - (long long)cities[j].y;
                long long d2 = dx * dx + dy * dy;

                // distance >= 0.25R  <=>  16*d^2 >= R^2
                if (16LL * d2 >= 1LL * R * R) {
                    eligible[i][j] = 1;
                    pairW[i][j] = (unsigned long long)cities[i].w * (unsigned long long)cities[j].w;
                }
            }
        }

        unsigned __int128 oneQuery = 0;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (eligible[i][j]) oneQuery += (unsigned __int128)pairW[i][j];
            }
        }
        denomWeight = oneQuery * (unsigned __int128)Q;
    }

    void precompute_orders() {
        vector<pair<long double, int>> hubs;
        hubs.reserve(N);
        spokeOrder.assign(N, {});

        for (int h = 0; h < N; ++h) {
            long double acc = 0.0L;
            vector<pair<long double, int>> cand;
            cand.reserve(max(0, N - 1));
            for (int v = 0; v < N; ++v) {
                if (v == h) continue;
                long double s = (long double)cities[v].w / (long double)dur[h][v];
                cand.push_back({s, v});
                acc += s;
            }
            sort(cand.begin(), cand.end(), [&](const auto& a, const auto& b) {
                if (a.first != b.first) return a.first > b.first;
                return a.second < b.second;
            });
            spokeOrder[h].reserve(cand.size());
            for (auto& p : cand) spokeOrder[h].push_back(p.second);

            long double hubScore = acc * (long double)cities[h].w;
            hubs.push_back({hubScore, h});
        }

        sort(hubs.begin(), hubs.end(), [&](const auto& a, const auto& b) {
            if (a.first != b.first) return a.first > b.first;
            return a.second < b.second;
        });
        hubOrder.clear();
        hubOrder.reserve(N);
        for (auto& p : hubs) hubOrder.push_back(p.second);
    }

    void precompute_square_latest() {
        vector<Flight> fs = squareFlights;
        sort(fs.begin(), fs.end(), [&](const Flight& a, const Flight& b) {
            if (a.s != b.s) return a.s > b.s;
            if (a.t != b.t) return a.t > b.t;
            if (a.u != b.u) return a.u < b.u;
            return a.v < b.v;
        });

        sqLatest.assign(Q * N * N, INF_NEG);
        vector<int> best(N);

        for (int q = 0; q < Q; ++q) {
            int T = targetTimes[q];
            for (int dst = 0; dst < N; ++dst) {
                fill(best.begin(), best.end(), INF_NEG);
                best[dst] = T;

                for (const auto& f : fs) {
                    if (best[f.v] >= f.t && best[f.u] < f.s) {
                        best[f.u] = f.s;
                    }
                }
                for (int src = 0; src < N; ++src) {
                    sqLatest[idx3(q, dst, src)] = best[src];
                }
            }
        }
    }

    vector<Flight> build_circle_flights(int hub, const vector<PlanePlan>& plans) const {
        vector<Flight> flights;
        flights.reserve(K * 16);

        for (int p = 0; p < K; ++p) {
            int spoke = plans[p].spoke;
            if (spoke == hub) continue;  // safety fallback

            int cur = plans[p].startHub ? hub : spoke;
            int tm = DAY_START + 5 * plans[p].phaseSlot;

            while (true) {
                int nxt = (cur == hub ? spoke : hub);
                int arr = tm + dur[cur][nxt];
                if (arr > DAY_END) break;
                flights.push_back(Flight{cur, nxt, tm, arr});
                cur = nxt;
                tm = arr;
            }
        }

        sort(flights.begin(), flights.end(), [&](const Flight& a, const Flight& b) {
            if (a.s != b.s) return a.s > b.s;
            if (a.t != b.t) return a.t > b.t;
            if (a.u != b.u) return a.u < b.u;
            return a.v < b.v;
        });
        return flights;
    }

    unsigned __int128 evaluate_vci(int hub, const vector<PlanePlan>& plans) const {
        vector<Flight> flights = build_circle_flights(hub, plans);
        vector<int> best(N);

        unsigned __int128 vci = 0;
        for (int q = 0; q < Q; ++q) {
            int T = targetTimes[q];
            for (int dst = 0; dst < N; ++dst) {
                fill(best.begin(), best.end(), INF_NEG);
                best[dst] = T;

                for (const auto& f : flights) {
                    if (best[f.v] >= f.t && best[f.u] < f.s) {
                        best[f.u] = f.s;
                    }
                }

                int base = (q * N + dst) * N;
                for (int src = 0; src < N; ++src) {
                    if (!eligible[src][dst]) continue;
                    if (sqLatest[base + src] < best[src]) {
                        vci += (unsigned __int128)pairW[src][dst];
                    }
                }
            }
        }
        return vci;
    }

    vector<PlanePlan> initial_plans_for_hub(int hub) const {
        vector<PlanePlan> plans(K);
        const auto& order = spokeOrder[hub];
        int m = (int)order.size();
        for (int p = 0; p < K; ++p) {
            plans[p].spoke = order[p % m];
            plans[p].phaseSlot = p % 12;
            plans[p].startHub = (p % 2 == 0);
        }
        return plans;
    }

    struct SearchResult {
        int hub = 0;
        vector<PlanePlan> plans;
        unsigned __int128 vci = 0;
    };

    SearchResult optimize_one_hub(int hub) {
        static constexpr int MAX_PASSES = 3;        // deep-dive preset
        static constexpr int SPOKE_CAND_LIMIT = 18; // deep-dive preset

        SearchResult res;
        res.hub = hub;
        res.plans = initial_plans_for_hub(hub);
        res.vci = evaluate_vci(hub, res.plans);

        bool any = true;
        for (int pass = 0; pass < MAX_PASSES && any && !time_over(); ++pass) {
            any = false;

            for (int p = 0; p < K; ++p) {
                if (time_over()) break;

                // 1) Spoke coordinate
                {
                    int curSpoke = res.plans[p].spoke;
                    int bestSpoke = curSpoke;
                    unsigned __int128 bestVal = res.vci;

                    int tried = 0;
                    for (int cand : spokeOrder[hub]) {
                        if (cand == hub || cand == curSpoke) continue;
                        res.plans[p].spoke = cand;
                        unsigned __int128 val = evaluate_vci(hub, res.plans);
                        if (val > bestVal) {
                            bestVal = val;
                            bestSpoke = cand;
                        }
                        ++tried;
                        if (tried >= SPOKE_CAND_LIMIT) break;
                        if ((tried & 3) == 0 && time_over()) break;
                    }

                    res.plans[p].spoke = bestSpoke;
                    if (bestVal > res.vci) {
                        res.vci = bestVal;
                        any = true;
                    }
                }

                if (time_over()) break;

                // 2) Phase coordinate (0..11 => 0..55 minutes)
                {
                    int curPhase = res.plans[p].phaseSlot;
                    int bestPhase = curPhase;
                    unsigned __int128 bestVal = res.vci;

                    for (int ph = 0; ph < 12; ++ph) {
                        if (ph == curPhase) continue;
                        res.plans[p].phaseSlot = ph;
                        unsigned __int128 val = evaluate_vci(hub, res.plans);
                        if (val > bestVal) {
                            bestVal = val;
                            bestPhase = ph;
                        }
                        if ((ph & 3) == 3 && time_over()) break;
                    }

                    res.plans[p].phaseSlot = bestPhase;
                    if (bestVal > res.vci) {
                        res.vci = bestVal;
                        any = true;
                    }
                }

                if (time_over()) break;

                // 3) Start direction coordinate
                {
                    bool curDir = res.plans[p].startHub;
                    bool bestDir = curDir;
                    unsigned __int128 bestVal = res.vci;

                    res.plans[p].startHub = !curDir;
                    unsigned __int128 val = evaluate_vci(hub, res.plans);
                    if (val > bestVal) {
                        bestVal = val;
                        bestDir = !curDir;
                    }

                    res.plans[p].startHub = bestDir;
                    if (bestVal > res.vci) {
                        res.vci = bestVal;
                        any = true;
                    }
                }
            }
        }

        return res;
    }

    SearchResult solve() {
        t0 = chrono::steady_clock::now();

        read_input();
        precompute_geometry();
        precompute_orders();
        precompute_square_latest();

        SearchResult bestAll;
        bool initialized = false;

        int hubTrials = min(N, 3);  // deep-dive preset
        for (int i = 0; i < hubTrials; ++i) {
            if (time_over()) break;
            int hub = hubOrder[i];
            SearchResult cand = optimize_one_hub(hub);
            if (!initialized || cand.vci > bestAll.vci) {
                bestAll = std::move(cand);
                initialized = true;
            }
        }

        if (!initialized) {
            int hub = hubOrder.empty() ? 0 : hubOrder[0];
            bestAll = optimize_one_hub(hub);
        }
        return bestAll;
    }

    void output_answer(const SearchResult& ans) const {
        // Rebuild grouped by plane for output in required format.
        vector<vector<Flight>> perPlane(K);
        for (int p = 0; p < K; ++p) {
            int spoke = ans.plans[p].spoke;
            if (spoke == ans.hub) continue;

            int cur = ans.plans[p].startHub ? ans.hub : spoke;
            int tm = DAY_START + 5 * ans.plans[p].phaseSlot;

            while (true) {
                int nxt = (cur == ans.hub ? spoke : ans.hub);
                int arr = tm + dur[cur][nxt];
                if (arr > DAY_END) break;
                perPlane[p].push_back(Flight{cur, nxt, tm, arr});
                cur = nxt;
                tm = arr;
            }
        }

        for (int p = 0; p < K; ++p) {
            cout << perPlane[p].size() << '\n';
            for (const auto& f : perPlane[p]) {
                cout << (f.u + 1) << ' ';
                print_time(f.s);
                cout << ' ' << (f.v + 1) << ' ';
                print_time(f.t);
                cout << '\n';
            }
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    Solver solver;
    auto ans = solver.solve();
    solver.output_answer(ans);
    return 0;
}