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

• 問題: No.5023 Airlines Optimization
• ユーザー: mogura3.0
• 提出日時: 2026-02-25 23:37:21
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 885 ms / 1,000 ms
• コード長: 17,626 bytes
• コンパイル時間: 4,542 ms
• コンパイル使用メモリ: 280,708 KB
• 実行使用メモリ: 7,848 KB
• スコア: 36,522,007
• 最終ジャッジ日時: 2026-02-25 23:39:02
• 合計ジャッジ時間: 99,328 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

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

ソースコード

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

using namespace std;

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

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

struct PlanePlan {
    int group;      // 0 or 1
    int spoke;      // 0-indexed city, must be != hubs[group]
    int phaseSlot;  // 0..11 => 0..55 min 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);
    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) {
    // Exact 5-minute ceil of 40 + 3*sqrt(d2)/40 using integer comparisons.
    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;
    for (int dur = 40; dur <= 300; dur += 5) {
        long long lhs = 40LL * dur - 1600LL;
        if (lhs * lhs >= 9LL * d2) return dur;
    }
    return 300;
}

struct Solver {
    int N = 0, R = 0, 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;

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

    vector<int> hubOrder;
    vector<vector<int>> spokeOrder;

    chrono::steady_clock::time_point t0;
    double internalTimeLimitSec = 0.88;

    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;
            squareFlights.push_back(Flight{a - 1, b - 1, parse_time_token(sTok), parse_time_token(tTok)});
        }

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

    void precompute_orders() {
        spokeOrder.assign(N, {});
        vector<pair<long double, int>> hubs;
        hubs.reserve(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 sc = (long double)cities[v].w / (long double)dur[h][v];
                cand.push_back({sc, v});
                acc += sc;
            }
            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(const array<int, 2>& hubs, const vector<PlanePlan>& plans) const {
        vector<Flight> flights;
        flights.reserve(K * 16);

        for (int p = 0; p < K; ++p) {
            const auto& pl = plans[p];
            int hub = hubs[pl.group];
            int spoke = pl.spoke;
            if (spoke == hub) continue;

            int cur = pl.startHub ? hub : spoke;
            int tm = DAY_START + 5 * pl.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(const array<int, 2>& hubs, const vector<PlanePlan>& plans) const {
        vector<Flight> flights = build_circle_flights(hubs, 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;
    }

    int first_valid_spoke_for_hub(int hub) const {
        for (int v : spokeOrder[hub]) {
            if (v != hub) return v;
        }
        return (hub + 1) % N;
    }

    vector<PlanePlan> initial_plans_for_hubs(const array<int, 2>& hubs) const {
        vector<PlanePlan> plans(K);
        array<int, 2> usedCnt{0, 0};
        array<int, 2> pickIdx{0, 0};

        for (int p = 0; p < K; ++p) {
            int g = (p % 2);  // balanced 13/12 split
            int hub = hubs[g];
            int otherHub = hubs[1 - g];

            int spoke;
            if (usedCnt[g] == 0) {
                // Seed an inter-hub shuttle for each group.
                spoke = otherHub;
            } else {
                const auto& ord = spokeOrder[hub];
                while (pickIdx[g] < (int)ord.size() && ord[pickIdx[g]] == hub) ++pickIdx[g];
                if (pickIdx[g] < (int)ord.size()) {
                    spoke = ord[pickIdx[g]++];
                } else {
                    spoke = first_valid_spoke_for_hub(hub);
                }
            }
            if (spoke == hub) spoke = first_valid_spoke_for_hub(hub);

            plans[p] = PlanePlan{g, spoke, p % 12, (p % 2 == 0)};
            ++usedCnt[g];
        }
        return plans;
    }

    struct SearchResult {
        array<int, 2> hubs{0, 1};
        vector<PlanePlan> plans;
        unsigned __int128 vci = 0;
    };

    SearchResult optimize_hub_pair(const array<int, 2>& hubs) {
        static constexpr int MAX_PASSES = 1;
        static constexpr int SPOKE_CAND_LIMIT = 10;
        static constexpr int MIN_GROUP_SIZE = 1;

        SearchResult res;
        res.hubs = hubs;
        res.plans = initial_plans_for_hubs(hubs);
        res.vci = evaluate_vci(hubs, res.plans);

        array<int, 2> groupCnt{0, 0};
        for (const auto& pl : res.plans) ++groupCnt[pl.group];

        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) Group toggle (single try)
                {
                    int curG = res.plans[p].group;
                    int nxtG = 1 - curG;
                    if (groupCnt[curG] > MIN_GROUP_SIZE) {
                        PlanePlan backup = res.plans[p];
                        int nxtHub = hubs[nxtG];
                        res.plans[p].group = nxtG;
                        if (res.plans[p].spoke == nxtHub) {
                            res.plans[p].spoke = first_valid_spoke_for_hub(nxtHub);
                        }
                        unsigned __int128 val = evaluate_vci(hubs, res.plans);
                        if (val > res.vci) {
                            --groupCnt[curG];
                            ++groupCnt[nxtG];
                            res.vci = val;
                            any = true;
                        } else {
                            res.plans[p] = backup;
                        }
                    }
                }

                if (time_over()) break;

                // 2) Spoke coordinate for current group
                {
                    int g = res.plans[p].group;
                    int hub = hubs[g];
                    int curSpoke = res.plans[p].spoke;
                    int bestSpoke = curSpoke;
                    unsigned __int128 bestVal = res.vci;

                    int tried = 0;
                    bool testedOtherHub = false;
                    int otherHub = hubs[1 - g];

                    for (int cand : spokeOrder[hub]) {
                        if (cand == hub || cand == curSpoke) continue;
                        if (cand == otherHub) testedOtherHub = true;

                        res.plans[p].spoke = cand;
                        unsigned __int128 val = evaluate_vci(hubs, res.plans);
                        if (val > bestVal) {
                            bestVal = val;
                            bestSpoke = cand;
                        }

                        ++tried;
                        if (tried >= SPOKE_CAND_LIMIT) break;
                        if ((tried & 3) == 0 && time_over()) break;
                    }

                    // Explicitly test the other hub as spoke (bridge shuttle) even if rank is low.
                    if (!time_over() && otherHub != hub && otherHub != curSpoke && !testedOtherHub) {
                        res.plans[p].spoke = otherHub;
                        unsigned __int128 val = evaluate_vci(hubs, res.plans);
                        if (val > bestVal) {
                            bestVal = val;
                            bestSpoke = otherHub;
                        }
                    }

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

                if (time_over()) break;

                // 3) Phase coordinate
                {
                    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(hubs, 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;

                // 4) Start direction toggle
                {
                    bool curDir = res.plans[p].startHub;
                    res.plans[p].startHub = !curDir;
                    unsigned __int128 val = evaluate_vci(hubs, res.plans);
                    if (val > res.vci) {
                        res.vci = val;
                        any = true;
                    } else {
                        res.plans[p].startHub = curDir;
                    }
                }
            }
        }

        return res;
    }

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

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

        vector<array<int, 2>> pairs;
        int hubCand = min(N, 6);
        for (int i = 0; i < hubCand; ++i) {
            for (int j = i + 1; j < hubCand; ++j) {
                pairs.push_back({hubOrder[i], hubOrder[j]});
            }
        }
        if (pairs.empty()) {
            if (N >= 2) pairs.push_back({0, 1});
            else pairs.push_back({0, 0});
        }

        struct SeedCand {
            array<int, 2> hubs;
            unsigned __int128 vci;
        };
        vector<SeedCand> seeds;
        seeds.reserve(pairs.size());

        for (const auto& hubs : pairs) {
            if (time_over()) break;
            auto initPlans = initial_plans_for_hubs(hubs);
            unsigned __int128 v = evaluate_vci(hubs, initPlans);
            seeds.push_back(SeedCand{hubs, v});
        }
        if (seeds.empty()) {
            auto hubs = pairs.front();
            auto initPlans = initial_plans_for_hubs(hubs);
            seeds.push_back(SeedCand{hubs, evaluate_vci(hubs, initPlans)});
        }

        sort(seeds.begin(), seeds.end(), [&](const SeedCand& a, const SeedCand& b) {
            return a.vci > b.vci;
        });

        SearchResult bestAll;
        bool initialized = false;

        int pairTrials = min<int>(seeds.size(), 4);
        for (int i = 0; i < pairTrials; ++i) {
            if (time_over()) break;
            SearchResult cand = optimize_hub_pair(seeds[i].hubs);
            if (!initialized || cand.vci > bestAll.vci) {
                bestAll = std::move(cand);
                initialized = true;
            }
        }

        if (!initialized) {
            bestAll = optimize_hub_pair(seeds[0].hubs);
        }
        return bestAll;
    }

    void output_answer(const SearchResult& ans) const {
        vector<vector<Flight>> perPlane(K);

        for (int p = 0; p < K; ++p) {
            const auto& pl = ans.plans[p];
            int hub = ans.hubs[pl.group];
            int spoke = pl.spoke;
            if (spoke == hub) continue;

            int cur = pl.startHub ? hub : spoke;
            int tm = DAY_START + 5 * pl.phaseSlot;
            while (true) {
                int nxt = (cur == hub ? spoke : 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;
}