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

• 問題: No.5023 Airlines Optimization
• ユーザー: mogura3.0
• 提出日時: 2026-02-25 23:18:46
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: RE
• 実行時間: -
• コード長: 3,796 bytes
• コンパイル時間: 2,356 ms
• コンパイル使用メモリ: 209,288 KB
• 実行使用メモリ: 1,484,608 KB
• スコア: 0
• 最終ジャッジ日時: 2026-02-25 23:19:03
• 合計ジャッジ時間: 5,437 ms
• ジャッジサーバーID （参考情報）: judge7 / judge3

ファイルパターン	結果
other	RE * 1 MLE * 1 -- * 98

ソースコード

#include <algorithm>
#include <cmath>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

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

struct Flight {
    int a, s, b, t;
};

static constexpr int DAY_START = 6 * 60;   // 06:00
static constexpr int DAY_END = 21 * 60;    // 21:00

int calc_duration_minutes(const City& c1, const City& c2) {
    long double dx = (long double)c1.x - (long double)c2.x;
    long double dy = (long double)c1.y - (long double)c2.y;
    long double d = sqrtl(dx * dx + dy * dy);
    long double raw = 60.0L * d / 800.0L + 40.0L;
    long double slots = ceill((raw - 1e-12L) / 5.0L);
    int dur = (int)(slots * 5.0L);
    return dur;
}

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

    int N, R;
    cin >> N >> R;
    vector<City> cities(N);
    for (int i = 0; i < N; ++i) {
        cin >> cities[i].x >> cities[i].y >> cities[i].w;
    }

    int M;
    cin >> M;
    for (int i = 0; i < M; ++i) {
        int a, s, b, t;
        cin >> a >> s >> b >> t;
        (void)a;
        (void)s;
        (void)b;
        (void)t;
    }

    int K;
    cin >> K;

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

    // Greedy hub selection: prioritize large population and short average travel time to others.
    int hub = 0;
    long double bestHubScore = -1.0L;
    for (int h = 0; h < N; ++h) {
        long double acc = 0.0L;
        for (int j = 0; j < N; ++j) {
            if (j == h) continue;
            acc += (long double)cities[j].w / (long double)dur[h][j];
        }
        long double score = acc * (long double)cities[h].w;
        if (score > bestHubScore) {
            bestHubScore = score;
            hub = h;
        }
    }

    // Greedy spoke ordering: heavy population + short cycle time gets priority.
    vector<pair<long double, int>> cand;
    cand.reserve(max(0, N - 1));
    for (int v = 0; v < N; ++v) {
        if (v == hub) continue;
        long double score = (long double)cities[v].w / (long double)dur[hub][v];
        cand.push_back({score, v});
    }
    sort(cand.begin(), cand.end(), [&](const auto& lhs, const auto& rhs) {
        if (lhs.first != rhs.first) return lhs.first > rhs.first;
        return lhs.second < rhs.second;
    });

    vector<int> assigned(K, hub);
    if (!cand.empty()) {
        for (int i = 0; i < K; ++i) {
            assigned[i] = cand[i % (int)cand.size()].second;
        }
    } else {
        // Degenerate fallback (should not happen under official constraints).
        for (int i = 0; i < K; ++i) assigned[i] = (hub + 1) % N;
    }

    vector<vector<Flight>> ans(K);

    // Build simple shuttle schedules with staggered phases/orientations.
    for (int p = 0; p < K; ++p) {
        int spoke = assigned[p];
        int phase = (p % 6) * 5;           // 0,5,...,25 (fits 30-min scoring grid diversification)
        bool startFromHub = (p % 2 == 0);  // alternate directions

        int curCity = startFromHub ? hub : spoke;
        int curTime = DAY_START + phase;

        while (true) {
            int nxtCity = (curCity == hub ? spoke : hub);
            int t = curTime + dur[curCity][nxtCity];
            if (t > DAY_END) break;
            ans[p].push_back(Flight{curCity + 1, curTime, nxtCity + 1, t});
            curCity = nxtCity;
            curTime = t;  // no turnaround time required
        }
    }

    for (int i = 0; i < K; ++i) {
        cout << ans[i].size() << '\n';
        for (const auto& f : ans[i]) {
            cout << f.a << ' ' << f.s << ' ' << f.b << ' ' << f.t << '\n';
        }
    }
    return 0;
}