結果

問題 No.5023 Airlines Optimization
コンテスト
ユーザー Moegi
提出日時 2026-02-25 21:12:58
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 4 ms / 1,000 ms
コード長 2,871 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,140 ms
コンパイル使用メモリ 350,128 KB
実行使用メモリ 7,848 KB
スコア 36,438,156
最終ジャッジ日時 2026-02-25 21:13:09
合計ジャッジ時間 10,744 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

static string to_hhmm(int minutes) {
    int h = minutes / 60;
    int m = minutes % 60;
    ostringstream oss;
    oss << setw(2) << setfill('0') << h << ":" << setw(2) << setfill('0') << m;
    return oss.str();
}

static int flight_duration_5min_ceil(long long x1, long long y1, long long x2, long long y2) {
    long double dx = (long double)x1 - (long double)x2;
    long double dy = (long double)y1 - (long double)y2;
    long double dist = sqrtl(dx*dx + dy*dy);                  // Euclidean distance d
    long double raw = 60.0L * dist / 800.0L + 40.0L;          // 60*d/800 + 40
    long double units = raw / 5.0L;
    // floating誤差で本来ちょうど整数のときに+εになって切り上がり過ぎるのを防ぐ
    long long k = (long long)ceill(units - 1e-12L);
    return (int)(k * 5);                                      // minutes, multiple of 5
}

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

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

    int N;
    long long R;
    if (!(cin >> N >> R)) return 0;

    vector<City> c(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> c[i].x >> c[i].y >> c[i].w;
    }

    int M;
    cin >> M;
    for (int i = 0; i < M; i++) {
        int a, b;
        string s, t;
        cin >> a >> s >> b >> t; // スクエア航空は読んで捨てる（今回使わない）
    }

    int K;
    cin >> K;

    const int START = 6 * 60;   // 06:00
    const int END   = 21 * 60;  // 21:00

    int hub = 1;
    // 行き先を 2..N の先頭から K 個（足りなければ巡回）
    vector<int> dests;
    for (int v = 2; v <= N; v++) dests.push_back(v);
    if (dests.empty()) {
        // N=1は起こらないはずだが念のため：全機0便
        for (int i = 0; i < K; i++) cout << 0 << "\n";
        return 0;
    }

    for (int p = 0; p < K; p++) {
        int dest = dests[p % (int)dests.size()];

        // 1機のフライト列を作る
        vector<tuple<int,int,int,int>> flights; // (a, s_min, b, t_min)
        int cur_city = hub;
        int cur_time = START;

        while (cur_time <= END) {
            int nxt_city = (cur_city == hub ? dest : hub);
            int dur = flight_duration_5min_ceil(
                c[cur_city].x, c[cur_city].y, c[nxt_city].x, c[nxt_city].y
            );

            if (cur_time + dur > END) break; // 到着が21:00超なら打ち切り
            flights.emplace_back(cur_city, cur_time, nxt_city, cur_time + dur);
            cur_time += dur;
            cur_city = nxt_city;
        }

        cout << flights.size() << "\n";
        for (auto &f : flights) {
            int a, smin, b, tmin;
            tie(a, smin, b, tmin) = f;
            cout << a << " " << to_hhmm(smin) << " " << b << " " << to_hhmm(tmin) << "\n";
        }
    }

    return 0;
}
0