#1149303 (C++17) No.5023 Airlines Optimization

• 問題: No.5023 Airlines Optimization
• ユーザー: mtmr_s1
• 提出日時: 2026-02-25 21:56:03
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 11 ms / 1,000 ms
• コード長: 8,589 bytes
• コンパイル時間: 3,150 ms
• コンパイル使用メモリ: 252,792 KB
• 実行使用メモリ: 7,848 KB
• スコア: 29,649,106
• 最終ジャッジ日時: 2026-02-25 21:56:13
• 合計ジャッジ時間: 8,935 ms
• ジャッジサーバーID （参考情報）: judge2 / judge6

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

ソースコード

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

// ------------------------------------------------------------
// Baseline: population-heavy direct round-trip shuttles (no transfers)
// - Precompute Square (given) latest-departure times via backward DP
// - For top-P cities, evaluate each pair (u,v) with a 1-plane shuttle u<->v
//   trying a few start offsets; keep only if it beats Square for some deadlines
// - Pick best K pairs and output their shuttle schedules; others c_i = 0
// ------------------------------------------------------------

static constexpr int N_FIXED = 47;
static constexpr int M_FIXED = 400;
static constexpr int R_FIXED = 1000;

// time grid: 06:00..21:00, step 5 min
static constexpr int START_MIN = 6 * 60;
static constexpr int END_MIN   = 21 * 60;
static constexpr int STEP_MIN  = 5;
static constexpr int TICKS = (END_MIN - START_MIN) / STEP_MIN; // 180
static constexpr int TICK_MAX = TICKS; // inclusive index 0..180
static constexpr int INF_NEG = -1;

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

struct Flight {
    int a;   // 0-based city
    int b;   // 0-based city
    int s;   // time idx 0..180
    int t;   // time idx 0..180
};

static int time_to_idx(const string& hhmm) {
    int hh = stoi(hhmm.substr(0, 2));
    int mm = stoi(hhmm.substr(3, 2));
    int mins = hh * 60 + mm;
    return (mins - START_MIN) / STEP_MIN;
}

static string idx_to_time(int idx) {
    int mins = START_MIN + idx * STEP_MIN;
    int hh = mins / 60;
    int mm = mins % 60;
    ostringstream oss;
    oss << setw(2) << setfill('0') << hh << ":" << setw(2) << setfill('0') << mm;
    return oss.str();
}

// duration formula: ceil_to_5( 60*d/800 + 40 ) minutes
static int dur_idx(const City& A, const City& B) {
    double dx = double(A.x - B.x);
    double dy = double(A.y - B.y);
    double d = sqrt(dx*dx + dy*dy);
    double raw = 60.0 * d / 800.0 + 40.0; // minutes
    int raw_int = (int)ceil(raw - 1e-12);
    int rounded = ((raw_int + 4) / 5) * 5;
    return rounded / 5;
}

static double euclid(const City& A, const City& B) {
    double dx = double(A.x - B.x);
    double dy = double(A.y - B.y);
    return sqrt(dx*dx + dy*dy);
}

struct Leg {
    int a, b;
    int s, t; // idx
};

struct Candidate {
    long long gain;
    int u, v;
    int start_idx;
    vector<Leg> legs; // full schedule for one plane
};

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;
    vector<Flight> sq(M);
    for (int i = 0; i < M; i++) {
        int a, b;
        string s_str, t_str;
        cin >> a >> s_str >> b >> t_str;
        --a; --b;
        sq[i].a = a;
        sq[i].b = b;
        sq[i].s = time_to_idx(s_str);
        sq[i].t = time_to_idx(t_str);
    }

    int K;
    cin >> K;

    // deadlines: 11:00, 11:30, ..., 21:00  (21 values)
    vector<int> deadlines;
    {
        int idx_1100 = (11*60 - START_MIN) / STEP_MIN; // 300/5=60
        for (int k = 0; k < 21; k++) deadlines.push_back(idx_1100 + 6*k);
    }

    // Precompute Square latest departure: sq_latest[dest][dk][src] = idx or -1
    // Backward DP relaxation for each (dest, deadline)
    vector<vector<vector<int>>> sq_latest(N, vector<vector<int>>(deadlines.size(), vector<int>(N, INF_NEG)));

    for (int dest = 0; dest < N; dest++) {
        for (int dk = 0; dk < (int)deadlines.size(); dk++) {
            int T = deadlines[dk];
            vector<int> L(N, INF_NEG);
            L[dest] = T;
            bool changed = true;
            // With time-monotone edges, relaxation converges fast; cap iterations for safety
            for (int it = 0; it < 500 && changed; it++) {
                changed = false;
                for (const auto& e : sq) {
                    if (L[e.b] != INF_NEG && e.t <= L[e.b]) {
                        if (e.s > L[e.a]) {
                            L[e.a] = e.s;
                            changed = true;
                        }
                    }
                }
            }
            for (int src = 0; src < N; src++) sq_latest[dest][dk][src] = L[src];
        }
    }

    // Choose top-P cities by population (they should already be sorted, but keep robust)
    vector<int> order(N);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b){
        return cities[a].w > cities[b].w;
    });
    int P = 15;
    if (P > N) P = N;
    vector<int> top(order.begin(), order.begin() + P);

    // Helper to build a 1-plane shuttle schedule u<->v starting at u at start_idx
    auto build_shuttle = [&](int u, int v, int start_idx) -> vector<Leg> {
        vector<Leg> legs;
        int duv = dur_idx(cities[u], cities[v]); // in ticks
        int dvui = dur_idx(cities[v], cities[u]); // same as duv but compute anyway
        // they should be identical; keep both for clarity
        (void)dvui;

        int cur_city = u;
        int other = v;
        int cur_t = start_idx;

        while (true) {
            int d = dur_idx(cities[cur_city], cities[other]);
            int arr = cur_t + d;
            if (arr > TICK_MAX) break;
            legs.push_back(Leg{cur_city, other, cur_t, arr});
            cur_t = arr;
            swap(cur_city, other);
        }
        return legs;
    };

    // For given legs, compute latest direct departure for direction src->dst for each deadline
    // If no flight arrives by deadline, return -1.
    auto direct_latest = [&](const vector<Leg>& legs, int src, int dst) -> vector<int> {
        vector<int> best(deadlines.size(), INF_NEG);
        for (const auto& L : legs) {
            if (L.a != src || L.b != dst) continue;
            for (int k = 0; k < (int)deadlines.size(); k++) {
                if (L.t <= deadlines[k]) best[k] = max(best[k], L.s);
            }
        }
        return best;
    };

    // Evaluate candidate pairs among top cities
    vector<Candidate> cands;
    cands.reserve(P * (P-1) / 2);

    for (int ii = 0; ii < P; ii++) {
        for (int jj = ii + 1; jj < P; jj++) {
            int u = top[ii], v = top[jj];
            // scoring only considers pairs with distance >= 0.25R (=250)
            if (euclid(cities[u], cities[v]) < 250.0) continue;

            long long wprod = cities[u].w * cities[v].w;
            long long best_gain = 0;
            int best_start = 0;
            vector<Leg> best_legs;

            // Try a few start offsets (06:00..06:55)
            for (int off = 0; off < 12; off++) {
                int start_idx = off; // 06:00 + 5*off
                auto legs = build_shuttle(u, v, start_idx);
                if (legs.empty()) continue;

                auto dir_uv = direct_latest(legs, u, v);
                auto dir_vu = direct_latest(legs, v, u);

                long long gain = 0;
                for (int k = 0; k < (int)deadlines.size(); k++) {
                    int sq_uv = sq_latest[v][k][u]; // src u -> dest v
                    int sq_vu = sq_latest[u][k][v]; // src v -> dest u
                    int ci_uv = dir_uv[k];
                    int ci_vu = dir_vu[k];

                    if (ci_uv != INF_NEG && sq_uv < ci_uv) gain += wprod;
                    if (ci_vu != INF_NEG && sq_vu < ci_vu) gain += wprod;
                }

                if (gain > best_gain) {
                    best_gain = gain;
                    best_start = start_idx;
                    best_legs = std::move(legs);
                }
            }

            if (best_gain > 0) {
                cands.push_back(Candidate{best_gain, u, v, best_start, best_legs});
            }
        }
    }

    sort(cands.begin(), cands.end(), [&](const Candidate& A, const Candidate& B){
        if (A.gain != B.gain) return A.gain > B.gain;
        if (A.u != B.u) return A.u < B.u;
        return A.v < B.v;
    });

    // Assign up to K planes to best candidates (1 plane per pair)
    vector<vector<Leg>> plane_legs(K);
    int used = 0;
    for (const auto& cand : cands) {
        if (used >= K) break;
        plane_legs[used] = cand.legs;
        used++;
    }
    // remaining planes left empty -> 0

    // Output
    // Each plane: c_i then lines "a s b t" (1-based city, HH:MM)
    for (int i = 0; i < K; i++) {
        cout << (int)plane_legs[i].size() << "\n";
        for (auto &L : plane_legs[i]) {
            cout << (L.a + 1) << " " << idx_to_time(L.s) << " "
                 << (L.b + 1) << " " << idx_to_time(L.t) << "\n";
        }
    }

    return 0;
}