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

• 問題: No.5023 Airlines Optimization
• ユーザー: mogura3.0
• 提出日時: 2026-02-25 23:24:07
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 6 ms / 1,000 ms
• コード長: 4,702 bytes
• コンパイル時間: 2,813 ms
• コンパイル使用メモリ: 213,692 KB
• 実行使用メモリ: 7,848 KB
• スコア: 36,114,215
• 最終ジャッジ日時: 2026-02-25 23:24:15
• 合計ジャッジ時間: 8,713 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

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

ソースコード

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <string>
#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 parse_time_token(const string& tok) {
    auto pos = tok.find(':');
    if (pos == string::npos) {
        // Fallback: if input is plain integer minutes.
        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) {
    long long dx = (long long)c1.x - (long long)c2.x;
    long long dy = (long long)c1.y - (long long)c2.y;
    long long D = dx * dx + dy * dy;  // squared distance

    // Exact rounding to 5-minute units:
    // duration = smallest multiple of 5 such that duration >= 40 + 3*sqrt(D)/40
    for (int dur = 40; dur <= 10000; dur += 5) {
        long long A = 40LL * dur - 1600LL;  // >= 0 for dur >= 40
        if (A * A >= 9LL * D) return dur;
    }
    return 10000;  // unreachable for official constraints
}

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, b;
        string sTok, tTok;
        cin >> a >> sTok >> b >> tTok;
        int s = parse_time_token(sTok);
        int t = parse_time_token(tTok);
        (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 << ' ';
            print_time(f.s);
            cout << ' ' << f.b << ' ';
            print_time(f.t);
            cout << '\n';
        }
    }
    return 0;
}