#1150700 (C++14) No.5023 Airlines Optimization

• 問題: No.5023 Airlines Optimization
• ユーザー: ebicochineal
• 提出日時: 2026-02-28 16:28:56
• 言語: C++14 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 805 ms / 1,000 ms
• コード長: 3,458 bytes
• コンパイル時間: 1,588 ms
• コンパイル使用メモリ: 130,328 KB
• 実行使用メモリ: 7,848 KB
• スコア: 33,674,857
• 最終ジャッジ日時: 2026-02-28 16:30:35
• 合計ジャッジ時間: 87,507 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

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

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <random>
#include <chrono>
#include <cstdio>

using namespace std;

const int TIME_MIN = 6 * 60;
const int TIME_MAX = 21 * 60;

struct City { int id; long long x, y, w; };
struct Flight { int from, to, s, t; };

int calc_dur(const City& a, const City& b) {
    double d = sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
    return (int)ceil((60.0 * d / 800.0 + 40.0) / 5.0) * 5;
}

double get_dist(const City& a, const City& b) {
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

class Solver {
    int N, M, K;
    double R;
    vector<City> cities;
    vector<vector<Flight>> schedule;
    vector<int> start_offsets;
    vector<int> target_spokes;

    void update_schedule(int k, int hub_id) {
        schedule[k].clear();
        int cur_t = TIME_MIN + start_offsets[k];
        int spoke_id = target_spokes[k];
        int cur_loc = hub_id;
        while (true) {
            int dest = (cur_loc == hub_id) ? spoke_id : hub_id;
            int d = calc_dur(cities[cur_loc - 1], cities[dest - 1]);
            if (cur_t + d > TIME_MAX) break;
            schedule[k].push_back({cur_loc, dest, cur_t, cur_t + d});
            cur_t += d;
            cur_loc = dest;
        }
    }

public:
    void solve() {
        if (!(cin >> N >> R)) return;
        cities.resize(N);
        for (int i = 0; i < N; ++i) {
            cities[i].id = i + 1;
            cin >> cities[i].x >> cities[i].y >> cities[i].w;
        }
        cin >> M;
        for (int i = 0; i < M; ++i) {
            int a, b, sh, sm, th, tm; char c;
            cin >> a >> sh >> c >> sm >> b >> th >> c >> tm;
        }
        cin >> K;

        vector<pair<long long, int>> pop_rank;
        for (int i = 0; i < N; ++i) pop_rank.push_back({cities[i].w, i + 1});
        sort(pop_rank.rbegin(), pop_rank.rend());

        int hub_id = pop_rank[0].second;
        vector<int> valid_spokes;
        for (int i = 0; i < N; ++i) {
            if (cities[i].id == hub_id) continue;
            if (get_dist(cities[hub_id - 1], cities[i]) >= 0.25 * R) {
                valid_spokes.push_back(cities[i].id);
            }
        }

        schedule.resize(K);
        start_offsets.assign(K, 0);
        target_spokes.resize(K);

        for (int k = 0; k < K; ++k) {
            target_spokes[k] = valid_spokes[k % valid_spokes.size()];
            start_offsets[k] = (k % 6) * 5;
            update_schedule(k, hub_id);
        }

        auto start_time = chrono::system_clock::now();
        mt19937 engine(42);
        while (true) {
            auto now = chrono::system_clock::now();
            if (chrono::duration_cast<chrono::milliseconds>(now - start_time).count() > 800) break;

            int k = engine() % K;
            int old_offset = start_offsets[k];
            int diff = (engine() % 2 == 0 ? 5 : -5);
            int new_offset = old_offset + diff;

            if (new_offset >= 0 && new_offset <= 30) {
                start_offsets[k] = new_offset;
                update_schedule(k, hub_id);
            }
        }

        for (int k = 0; k < K; ++k) {
            printf("%d\n", (int)schedule[k].size());
            for (auto& f : schedule[k]) {
                printf("%d %02d:%02d %d %02d:%02d\n", f.from, f.s / 60, f.s % 60, f.to, f.t / 60, f.t % 60);
            }
        }
    }
};

int main() {
    Solver s;
    s.solve();
    return 0;
}