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

• 問題: No.5023 Airlines Optimization
• ユーザー: tetra4
• 提出日時: 2026-02-25 23:28:47
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 591 ms / 1,000 ms
• コード長: 9,245 bytes
• コンパイル時間: 3,724 ms
• コンパイル使用メモリ: 353,156 KB
• 実行使用メモリ: 7,848 KB
• スコア: 60,608,384
• 最終ジャッジ日時: 2026-02-25 23:30:13
• 合計ジャッジ時間: 64,608 ms
• ジャッジサーバーID （参考情報）: judge4 / judge7

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

ソースコード

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

constexpr int N = 47, R = 1000, M = 400, K = 25;
constexpr int INF = 1e9;
constexpr int MAX_TIME_SLOTS = 182;
constexpr int MAX_FLIGHTS = 2000;

struct Flight {
    int u, s, v, t;
};

// スロット(0~180)を "HH:MM" 形式の文字列に変換
string to_time_str(int t) {
    int h = 6 + t / 12;
    int m = (t % 12) * 5;
    char buf[6];
    snprintf(buf, sizeof(buf), "%02d:%02d", h, m);
    return string(buf);
}

struct Input {
    array<int, N> x, y, w;
    array<int, M> a, s, b, t;
    array<array<bool, N>, N> valid_dist{};
    array<array<long long, N>, N> weight{};
    long long total_W = 0;

    Input() {
        int _;
        cin >> _ >> _;
        for (int i = 0; i < N; ++i) cin >> x[i] >> y[i] >> w[i];
        cin >> _;
        string s_str, t_str;
        for (int i = 0; i < M; ++i) {
            cin >> a[i] >> s_str >> b[i] >> t_str;
            --a[i], --b[i];
            s[i] = (stoi(s_str.substr(0, 2)) - 6) * 12 + stoi(s_str.substr(3, 2)) / 5;
            t[i] = (stoi(t_str.substr(0, 2)) - 6) * 12 + stoi(t_str.substr(3, 2)) / 5;
        }

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (i == j) continue;
                long long dx = x[i] - x[j];
                long long dy = y[i] - y[j];
                if (dx * dx + dy * dy >= (R * R) / 16) {
                    valid_dist[i][j] = true;
                    weight[i][j] = (long long)w[i] * w[j];
                    total_W += weight[i][j] * 21;
                }
            }
        }
    }

    int get_duration(int u, int v) const {
        double dx = x[u] - x[v];
        double dy = y[u] - y[v];
        double d = sqrt(dx * dx + dy * dy);
        double minutes = 60.0 * d / 800.0 + 40.0;
        return (int)ceil(minutes / 5.0 - 1e-9);
    }
};

// 計算用のワークスペース
struct ComputeSciWorkspace {
    array<array<int, MAX_TIME_SLOTS>, N> head;
    array<int, MAX_FLIGHTS> nxt;
    array<array<bool, MAX_TIME_SLOTS>, N> reach;
};

// 限界利益探索用の巨大配列を保持するワークスペース
struct MarginalGainWorkspace {
    array<array<array<int, 21>, N>, N> current_s_ci;
    array<array<array<long long, MAX_TIME_SLOTS>, N>, N> edge_gain;
    array<array<long long, MAX_TIME_SLOTS>, N> dp;
    array<array<int, MAX_TIME_SLOTS>, N> nxt_v;
    array<array<int, N>, N> dur;
};

// 共通関数：フライト集合に対する限界出発時刻 (s_ci) を計算する
void compute_s_ci(const Input& in, const vector<Flight>& flights,
                  array<array<array<int, 21>, N>, N>& s_ci, ComputeSciWorkspace& ws) {
    for (int u = 0; u < N; ++u) {
        for (int dst = 0; dst < N; ++dst) {
            s_ci[u][dst].fill(-INF);
        }
    }

    for (int u = 0; u < N; ++u) ws.head[u].fill(-1);
    ws.nxt.fill(-1);

    for (int i = 0; i < (int)flights.size(); ++i) {
        int u = flights[i].u;
        int s = flights[i].s;
        ws.nxt[i] = ws.head[u][s];
        ws.head[u][s] = i;
    }

    for (int dst = 0; dst < N; ++dst) {
        for (int T_idx = 0; T_idx < 21; ++T_idx) {
            int T_target = 60 + T_idx * 6;
            for (int u = 0; u < N; ++u) ws.reach[u].fill(false);
            for (int t = 0; t <= T_target; ++t) ws.reach[dst][t] = true;

            for (int t = T_target; t >= 0; --t) {
                for (int u = 0; u < N; ++u) {
                    if (t + 1 <= 180 && ws.reach[u][t + 1]) ws.reach[u][t] = true;
                    for (int e = ws.head[u][t]; e != -1; e = ws.nxt[e]) {
                        int v = flights[e].v;
                        int arr_time = flights[e].t;
                        if (arr_time <= T_target && ws.reach[v][arr_time]) {
                            ws.reach[u][t] = true;
                        }
                    }
                }
            }
            for (int u = 0; u < N; ++u) {
                if (u == dst || !in.valid_dist[u][dst]) continue;
                for (int t = T_target; t >= 0; --t) {
                    if (ws.reach[u][t]) {
                        s_ci[u][dst][T_idx] = t;
                        break;
                    }
                }
            }
        }
    }
}

struct RivalSchedule {
    array<array<array<int, 21>, N>, N> s_sq;
    RivalSchedule(const Input& in, ComputeSciWorkspace& ws) {
        vector<Flight> r_flights;
        r_flights.reserve(M);
        for (int i = 0; i < M; ++i) r_flights.push_back({in.a[i], in.s[i], in.b[i], in.t[i]});
        compute_s_ci(in, r_flights, s_sq, ws);
    }
};

// 限界利益(Marginal Gain)に基づく逐次最長路アルゴリズム
array<vector<Flight>, K> solve_marginal_gain(const Input& in, const RivalSchedule& rival,
                                             ComputeSciWorkspace& c_ws,
                                             MarginalGainWorkspace& mg_ws) {
    array<vector<Flight>, K> circle_flights;
    vector<Flight> all_my_flights;
    all_my_flights.reserve(MAX_FLIGHTS);

    for (int u = 0; u < N; ++u) {
        for (int v = 0; v < N; ++v) {
            mg_ws.dur[u][v] = (u != v) ? in.get_duration(u, v) : 0;
        }
    }

    for (int k = 0; k < K; ++k) {
        compute_s_ci(in, all_my_flights, mg_ws.current_s_ci, c_ws);

        for (int u = 0; u < N; ++u) {
            for (int v = 0; v < N; ++v) mg_ws.edge_gain[u][v].fill(0);
        }

        for (int u = 0; u < N; ++u) {
            for (int dst = 0; dst < N; ++dst) {
                if (!in.valid_dist[u][dst]) continue;
                for (int T_idx = 0; T_idx < 21; ++T_idx) {
                    int s_sq_val = rival.s_sq[u][dst][T_idx];
                    int s_ci_val = mg_ws.current_s_ci[u][dst][T_idx];
                    if (s_ci_val > s_sq_val) continue;

                    int min_s = max(0, s_sq_val + 1);
                    int T_target = 60 + T_idx * 6;

                    for (int v = 0; v < N; ++v) {
                        if (u == v) continue;
                        int max_t = (v == dst) ? T_target : mg_ws.current_s_ci[v][dst][T_idx];
                        if (max_t < 0) continue;
                        int max_s = min(180 - mg_ws.dur[u][v], max_t - mg_ws.dur[u][v]);

                        if (min_s <= max_s) {
                            mg_ws.edge_gain[u][v][min_s] += in.weight[u][dst];
                            if (max_s + 1 <= 180)
                                mg_ws.edge_gain[u][v][max_s + 1] -= in.weight[u][dst];
                        }
                    }
                }
            }
        }

        for (int u = 0; u < N; ++u) {
            for (int v = 0; v < N; ++v) {
                if (u == v) continue;
                long long current_val = 0;
                for (int s = 0; s <= 180; ++s) {
                    current_val += mg_ws.edge_gain[u][v][s];
                    mg_ws.edge_gain[u][v][s] = current_val;
                }
            }
        }

        for (int u = 0; u < N; ++u) {
            mg_ws.dp[u].fill(0);
            mg_ws.nxt_v[u].fill(-1);
        }

        for (int t = 180; t >= 0; --t) {
            for (int u = 0; u < N; ++u) {
                if (t + 1 <= 180) {
                    mg_ws.dp[u][t] = mg_ws.dp[u][t + 1];
                    mg_ws.nxt_v[u][t] = -1;
                }
                for (int v = 0; v < N; ++v) {
                    if (u == v) continue;
                    int t_next = t + mg_ws.dur[u][v];
                    if (t_next <= 180) {
                        long long gain = mg_ws.edge_gain[u][v][t];
                        if (gain + mg_ws.dp[v][t_next] > mg_ws.dp[u][t]) {
                            mg_ws.dp[u][t] = gain + mg_ws.dp[v][t_next];
                            mg_ws.nxt_v[u][t] = v;
                        }
                    }
                }
            }
        }

        long long best_start_val = -1;
        int start_u = 0;
        for (int u = 0; u < N; ++u) {
            if (mg_ws.dp[u][0] > best_start_val) {
                best_start_val = mg_ws.dp[u][0];
                start_u = u;
            }
        }

        int curr_u = start_u, curr_t = 0;
        while (curr_t <= 180) {
            int next_city = mg_ws.nxt_v[curr_u][curr_t];
            if (next_city != -1) {
                int d = mg_ws.dur[curr_u][next_city];
                Flight f = {curr_u, curr_t, next_city, curr_t + d};
                circle_flights[k].push_back(f);
                all_my_flights.push_back(f);
                curr_u = next_city;
                curr_t += d;
            } else {
                curr_t += 1;
            }
        }
    }
    return circle_flights;
}

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

    Input in;
    auto c_ws = make_unique<ComputeSciWorkspace>();
    auto mg_ws = make_unique<MarginalGainWorkspace>();

    RivalSchedule rival(in, *c_ws);
    auto circle_flights = solve_marginal_gain(in, rival, *c_ws, *mg_ws);

    for (int k = 0; k < K; ++k) {
        cout << circle_flights[k].size() << "\n";
        for (const auto& f : circle_flights[k]) {
            cout << f.u + 1 << " " << to_time_str(f.s) << " " << f.v + 1 << " " << to_time_str(f.t)
                 << "\n";
        }
    }
    return 0;
}