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

• 問題: No.5023 Airlines Optimization
• ユーザー: YuuuT
• 提出日時: 2026-02-25 22:36:48
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 358 ms / 1,000 ms
• コード長: 7,998 bytes
• コンパイル時間: 3,038 ms
• コンパイル使用メモリ: 225,480 KB
• 実行使用メモリ: 7,848 KB
• スコア: 40,201,483
• 最終ジャッジ日時: 2026-02-25 22:41:46
• 合計ジャッジ時間: 36,052 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

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

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <utility>
#include <climits>
#include <deque>
#include <bitset>
#include <cmath>
#include <string>
#include <cstdlib>
#include <cassert>
#include <chrono>
#include <cstring>
#include <cstdio>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long

class Random {
    static uint32_t xorshift() {
        static uint32_t x = 123456789, y = 362436039, z = 521288629, w = 88675123; 
        uint32_t t = x ^ (x << 11); x = y; y = z; z = w;
        return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    }
public:
    inline static uint32_t randrange(unsigned x) { return xorshift() % x; } // [0, x)
    inline static uint32_t randrange(unsigned x, unsigned y) { return randrange(y - x) + x; } // [x, y)
    inline static float random() { return (xorshift() + 0.5) * (1.0 / UINT_MAX); } // [0.0, 1.0)
};

class Timer {
    chrono::time_point<chrono::steady_clock> start;
public:
    Timer() : start(chrono::steady_clock::now()) {}
    unsigned short get_ms() { // 経過時間を返す
        auto now_time = chrono::steady_clock::now();
        return chrono::duration_cast<chrono::milliseconds>(now_time - start).count();
    }
};
Timer timer;

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

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

constexpr int MAX_N = 47;
constexpr int MAX_M = 400;
constexpr int MAX_K = 25;
constexpr int TARGET_CNT = 21;
constexpr int NEG_INF = -1000000000;
constexpr int DAY_START = 6 * 60;
constexpr int DAY_END = 21 * 60;
constexpr int MAX_C = 64;

int N, R, M, K;
City cities[MAX_N + 1];
Flight square_flights[MAX_M];
int target_times[TARGET_CNT];
int s_sq_latest[MAX_N + 1][MAX_N + 1][TARGET_CNT];
int travel_time_min[MAX_N + 1][MAX_N + 1];
bool valid_pair[MAX_N + 1][MAX_N + 1];
long long pair_score[MAX_N + 1][MAX_N + 1];
bool won[MAX_N + 1][MAX_N + 1][TARGET_CNT];

int plane_now_city[MAX_K];
int plane_now_time[MAX_K];
int plane_cnt[MAX_K];
int out_a[MAX_K][MAX_C];
int out_s[MAX_K][MAX_C];
int out_b[MAX_K][MAX_C];
int out_t[MAX_K][MAX_C];

int parse_time(const string& s) {
    int h = (s[0] - '0') * 10 + (s[1] - '0');
    int m = (s[3] - '0') * 10 + (s[4] - '0');
    return h * 60 + m;
}

string format_time(int t) {
    int h = t / 60;
    int m = t % 60;
    if (m < 0) {
        m += 60;
        h--;
    }
    h = max(0, min(99, h));
    m = max(0, min(59, m));
    char buf[6];
    snprintf(buf, sizeof(buf), "%02d:%02d", h, m);
    return string(buf);
}

void build_target_times() {
    for (int idx = 0; idx < TARGET_CNT; idx++) {
        target_times[idx] = 11 * 60 + idx * 30;
    }
}

void precompute_square_latest_departure() {
    build_target_times();

    int latest_from[MAX_N + 1];
    for (int dst = 1; dst <= N; dst++) {
        for (int tid = 0; tid < TARGET_CNT; tid++) {
            for (int city = 1; city <= N; city++) latest_from[city] = NEG_INF;
            latest_from[dst] = target_times[tid];

            bool updated = true;
            while (updated) {
                updated = false;
                for (int f = 0; f < M; f++) {
                    const Flight& fl = square_flights[f];
                    if (fl.t <= latest_from[fl.b] && latest_from[fl.a] < fl.s) {
                        latest_from[fl.a] = fl.s;
                        updated = true;
                    }
                }
            }

            for (int src = 1; src <= N; src++) {
                s_sq_latest[src][dst][tid] = latest_from[src];
            }
        }
    }
}

void precompute_city_info() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (i == j) {
                travel_time_min[i][j] = 0;
                valid_pair[i][j] = false;
                pair_score[i][j] = 0;
                continue;
            }
            const double dx = static_cast<double>(cities[i].x - cities[j].x);
            const double dy = static_cast<double>(cities[i].y - cities[j].y);
            const double d = sqrt(dx * dx + dy * dy);
            const double raw = 60.0 * d / 800.0 + 40.0;
            travel_time_min[i][j] = static_cast<int>(ceil(raw / 5.0)) * 5;
            valid_pair[i][j] = (d >= 0.25 * static_cast<double>(R));
            pair_score[i][j] = 1LL * cities[i].w * cities[j].w;
        }
    }
}

void build_greedy_schedule() {
    memset(won, 0, sizeof(won));
    for (int p = 0; p < K; p++) {
        plane_now_city[p] = 0;
        plane_now_time[p] = DAY_START;
        plane_cnt[p] = 0;
    }

    while (true) {
        int p = -1;
        int best_time = DAY_END;
        for (int i = 0; i < K; i++) {
            if (plane_now_time[i] < best_time) {
                best_time = plane_now_time[i];
                p = i;
            }
        }
        if (p == -1 || best_time >= DAY_END) break;

        const int now = plane_now_time[p];
        double best_eval = -1.0;
        long long best_gain = -1;
        int best_u = -1, best_v = -1, best_s = -1, best_arr = -1;

        const int u_l = (plane_now_city[p] == 0 ? 1 : plane_now_city[p]);
        const int u_r = (plane_now_city[p] == 0 ? N : plane_now_city[p]);

        for (int u = u_l; u <= u_r; u++) {
            for (int v = 1; v <= N; v++) {
                if (u == v) continue;
                const int dur = travel_time_min[u][v];
                for (int s = now; s + dur <= DAY_END; s += 5) {
                    const int arr = s + dur;
                    long long gain = 0;
                    if (valid_pair[u][v]) {
                        for (int tid = 0; tid < TARGET_CNT; tid++) {
                            if (arr <= target_times[tid] && s_sq_latest[u][v][tid] < s && !won[u][v][tid]) {
                                gain += pair_score[u][v];
                            }
                        }
                    }
                    const int consumed = s - now + dur;
                    const double eval = static_cast<double>(gain) / static_cast<double>(consumed);
                    if (eval > best_eval || (eval == best_eval && gain > best_gain)) {
                        best_eval = eval;
                        best_gain = gain;
                        best_u = u;
                        best_v = v;
                        best_s = s;
                        best_arr = arr;
                    }
                }
            }
        }

        if (best_u == -1 || best_gain <= 0 || plane_cnt[p] >= MAX_C) {
            plane_now_time[p] = DAY_END;
            continue;
        }

        if (valid_pair[best_u][best_v]) {
            for (int tid = 0; tid < TARGET_CNT; tid++) {
                if (best_arr <= target_times[tid] && s_sq_latest[best_u][best_v][tid] < best_s) {
                    won[best_u][best_v][tid] = true;
                }
            }
        }

        const int idx = plane_cnt[p]++;
        out_a[p][idx] = best_u;
        out_s[p][idx] = best_s;
        out_b[p][idx] = best_v;
        out_t[p][idx] = best_arr;
        plane_now_city[p] = best_v;
        plane_now_time[p] = best_arr;
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    timer = Timer(); // タイマー初期化

    cin >> N >> R;
    cerr << N << " " << R << "\n";

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

    cin >> M;
    cerr << M << "\n";
    for (int i = 0; i < M; i++) {
        string s, t;
        cin >> square_flights[i].a >> s >> square_flights[i].b >> t;
        square_flights[i].s = parse_time(s);
        square_flights[i].t = parse_time(t);
    }

    cin >> K;

    precompute_city_info();
    precompute_square_latest_departure();
    build_greedy_schedule();
    for (int p = 0; p < K; p++) {
        cout << plane_cnt[p] << '\n';
        for (int i = 0; i < plane_cnt[p]; i++) {
            cout << out_a[p][i] << ' ' << format_time(out_s[p][i]) << ' '
                 << out_b[p][i] << ' ' << format_time(out_t[p][i]) << '\n';
        }
    }

}