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

• 問題: No.5023 Airlines Optimization
• ユーザー: Shymohn _
• 提出日時: 2026-02-25 22:25:46
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 996 ms / 1,000 ms
• コード長: 15,043 bytes
• コンパイル時間: 6,282 ms
• コンパイル使用メモリ: 371,656 KB
• 実行使用メモリ: 7,844 KB
• スコア: 36,463,857
• 最終ジャッジ日時: 2026-02-25 22:28:57
• 合計ジャッジ時間: 111,859 ms
• ジャッジサーバーID （参考情報）: judge6 / judge4

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")


struct City { double x, y; long long w; };
struct Flight { int a; int dep; int b; int arr; }; // dep/arr in minutes from midnight

int travel_time_minutes(double x1, double y1, double x2, double y2) {
    double d = hypot(x1 - x2, y1 - y2);
    double raw = 60.0 * d / 800.0 + 40.0;
    int tt = (int)ceil(raw / 5.0) * 5;
    return tt;
}

string fmt_time(int t){
    int hh = t / 60;
    int mm = t % 60;
    char buf[6];
    sprintf(buf, "%02d:%02d", hh, mm);
    return string(buf);
}

const int START = 6*60;   // 360
const int END   = 21*60;  // 1260
const int INF_NEG = -1000000000;

// Convert "HH:MM" to minutes
int parse_time(const string &s){
    int hh = stoi(s.substr(0,2));
    int mm = stoi(s.substr(3,2));
    return hh*60 + mm;
}

using Schedule = vector<vector<Flight>>;

// Build list of target arrival times: 11:00..21:00 step 30
vector<int> build_target_times() {
    vector<int> T;
    for (int t = 11*60; t <= 21*60; t += 30) T.push_back(t);
    return T;
}

// Flatten schedules into flight vector
vector<Flight> flatten_schedule(const Schedule &schedules) {
    vector<Flight> flights;
    for (const auto &sch : schedules) {
        for (const auto &f : sch) flights.push_back(f);
    }
    return flights;
}

// compute flights_by_arrival mapping for given flights
vector<vector<int>> build_flights_by_arrival(const vector<Flight> &flights, int N) {
    vector<vector<int>> fba(N);
    for (int i = 0; i < (int)flights.size(); ++i) {
        int arr_city = flights[i].b;
        fba[arr_city].push_back(i);
    }
    return fba;
}

// Given flights (list) and flights_by_arrival, compute for all dest and all target times T the latest departure times
// returns res[dest][t_idx][city] = latest departure time from city to reach dest by T (or INF_NEG)
vector<vector<vector<int>>> compute_latest_deps_all(int N, const vector<Flight> &flights, const vector<vector<int>> &fba, const vector<int> &Tlist) {
    int D = N;
    int TT = (int)Tlist.size();
    vector<vector<vector<int>>> res(D, vector<vector<int>>(TT, vector<int>(N, INF_NEG)));
    for (int dest = 0; dest < D; ++dest) {
        for (int ti = 0; ti < TT; ++ti) {
            int T = Tlist[ti];
            vector<int> L(N, INF_NEG);
            deque<int> dq;
            L[dest] = T;
            dq.push_back(dest);
            while (!dq.empty()) {
                int v = dq.front(); dq.pop_front();
                for (int fi : fba[v]) {
                    const Flight &f = flights[fi];
                    if (f.arr <= L[v]) {
                        int u = f.a;
                        if (L[u] < f.dep) {
                            L[u] = f.dep;
                            dq.push_back(u);
                        }
                    }
                }
            }
            res[dest][ti] = std::move(L);
        }
    }
    return res;
}

// compute latest_deps for circle (s_ci) given current schedules: returns res[dest][ti][city]
vector<vector<vector<int>>> compute_s_ci_all(const Schedule &schedules, const vector<City> &cities, const vector<int> &Tlist) {
    vector<Flight> flights = flatten_schedule(schedules);
    int N = (int)cities.size();
    vector<vector<int>> fba = build_flights_by_arrival(flights, N);
    return compute_latest_deps_all(N, flights, fba, Tlist);
}

// Evaluate share-rate S given precomputed s_sq for Square and computed s_ci for Circle
long double compute_share_rate(const vector<vector<vector<int>>> &s_sq_all, const vector<vector<vector<int>>> &s_ci_all,
                               const vector<pair<int,int>> &ODlist, const vector<int> &Tlist,
                               const vector<City> &cities) {
    long double v_ci = 0.0L, v_sq = 0.0L;
    int TT = (int)Tlist.size();
    for (auto &od : ODlist) {
        int u = od.first;
        int v = od.second;
        long long weight = cities[u].w * cities[v].w;
        for (int ti = 0; ti < TT; ++ti) {
            int s_sq = s_sq_all[v][ti][u];
            int s_ci = s_ci_all[v][ti][u];
            if (s_sq < s_ci) v_ci += (long double)weight;
            else v_sq += (long double)weight;
        }
    }
    if (v_ci + v_sq <= 0.0L) return 0.0L;
    return v_ci / (v_ci + v_sq);
}

// Build initial schedule as hub <-> top25 (or up to available) round-robin
Schedule build_initial(const vector<City> &cities, int K) {
    int N = (int)cities.size();
    int hub = 0;
    for (int i = 1; i < N; ++i) if (cities[i].w > cities[hub].w) hub = i;
    vector<pair<long long,int>> vec;
    for (int i = 0; i < N; ++i) if (i != hub) vec.emplace_back(cities[i].w, i);
    sort(vec.begin(), vec.end(), [](const auto &A, const auto &B){
        if (A.first != B.first) return A.first > B.first;
        return A.second < B.second;
    });
    int needSpokes = 25;
    int topCount = min((int)vec.size(), needSpokes);
    vector<int> targets;
    for (int i = 0; i < topCount; ++i) targets.push_back(vec[i].second);

    Schedule schedules(K);
    if (topCount == 0) return schedules;

    for (int k = 0; k < K; ++k) {
        int target = targets[k % topCount];
        int cur = hub;
        int time = START;
        while (true) {
            int next = (cur == hub) ? target : hub;
            int tt = travel_time_minutes(cities[cur].x, cities[cur].y, cities[next].x, cities[next].y);
            int dep = time;
            int arr = dep + tt;
            if (arr > END) break;
            schedules[k].push_back({cur, dep, next, arr});
            cur = next;
            time = arr;
        }
    }
    return schedules;
}

// Greedy extend from (cur, time) for a single plane
vector<Flight> greedy_extend_from(const vector<City> &cities, int cur, int time) {
    vector<Flight> res;
    int N = (int)cities.size();
    while (true) {
        int best = -1, best_tt = INT_MAX;
        for (int j = 0; j < N; ++j) {
            if (j == cur) continue;
            int tt = travel_time_minutes(cities[cur].x, cities[cur].y, cities[j].x, cities[j].y);
            if (time + tt > END) continue;
            if (tt < best_tt || (tt == best_tt && j < best)) {
                best_tt = tt; best = j;
            }
        }
        if (best == -1) break;
        int dep = time;
        int arr = dep + best_tt;
        res.push_back({cur, dep, best, arr});
        cur = best;
        time = arr;
    }
    return res;
}

// Attempt neighbor operations on schedules (modify only one plane's schedule minimally).
// Returns pair<bool,int> : whether changed, and index of plane changed
pair<bool,int> apply_random_neighbor(Schedule &schedules, const vector<City> &cities, mt19937_64 &rng) {
    int K = schedules.size();
    uniform_int_distribution<int> pick_plane(0, max(0, K-1));
    int k = pick_plane(rng);
    vector<Flight> &sch = schedules[k];
    int n = (int)sch.size();
    uniform_int_distribution<int> opdist(0,1);
    int op = opdist(rng);
    if (n == 0) {
        int hub = 0;
        for (int i = 1; i < (int)cities.size(); ++i) if (cities[i].w > cities[hub].w) hub = i;
        vector<Flight> newsch = greedy_extend_from(cities, hub, START);
        if (!newsch.empty()) {
            sch = std::move(newsch);
            return {true, k};
        } else return {false, -1};
    }
    vector<Flight> backup = sch;
    if (op == 0) {
        uniform_int_distribution<int> pick_pos(0, n-1);
        int p = pick_pos(rng);
        int cur; int time;
        if (p == 0) { cur = sch[0].a; time = sch[0].dep; }
        else { cur = sch[p-1].b; time = sch[p-1].arr; }
        vector<int> cand;
        int N = (int)cities.size();
        for (int j = 0; j < N; ++j) {
            if (j == cur) continue;
            int tt = travel_time_minutes(cities[cur].x, cities[cur].y, cities[j].x, cities[j].y);
            if (time + tt <= END) cand.push_back(j);
        }
        if (cand.empty()) return {false, -1};
        int cur_b = sch[p].b;
        vector<int> cand2;
        for (int v : cand) if (v != cur_b) cand2.push_back(v);
        if (cand2.empty()) return {false, -1};
        uniform_int_distribution<int> pick_cand(0, (int)cand2.size()-1);
        int newdest = cand2[pick_cand(rng)];
        sch.erase(sch.begin() + p, sch.end());
        int tt = travel_time_minutes(cities[cur].x, cities[cur].y, cities[newdest].x, cities[newdest].y);
        int dep = time;
        int arr = dep + tt;
        sch.push_back({cur, dep, newdest, arr});
        int cur_city = newdest;
        int cur_time = arr;
        for (int j = p+1; j < (int)backup.size(); ++j) {
            const Flight &orig = backup[j];
            int required_tt = travel_time_minutes(cities[orig.a].x, cities[orig.a].y, cities[orig.b].x, cities[orig.b].y);
            if (orig.a == cur_city && orig.dep >= cur_time && orig.arr - orig.dep == required_tt) {
                sch.push_back(orig);
                cur_city = orig.b;
                cur_time = orig.arr;
            } else {
                vector<Flight> tail = greedy_extend_from(cities, cur_city, cur_time);
                sch.insert(sch.end(), tail.begin(), tail.end());
                break;
            }
        }
        return {true, k};
    } else {
        uniform_int_distribution<int> pick_pos(0, n-1);
        int p = pick_pos(rng);
        int prev_arr = (p==0) ? START : sch[p-1].arr;
        int dep = sch[p].dep;
        int tt = sch[p].arr - sch[p].dep;
        vector<int> cand_dep;
        if (dep - 5 >= prev_arr) cand_dep.push_back(dep - 5);
        if (dep + 5 + tt <= END) cand_dep.push_back(dep + 5);
        if (cand_dep.empty()) return {false, -1};
        uniform_int_distribution<int> pickd(0, (int)cand_dep.size()-1);
        int new_dep = cand_dep[pickd(rng)];
        int new_arr = new_dep + tt;
        int a_orig = sch[p].a;
        int b_orig = sch[p].b;
        sch.erase(sch.begin() + p, sch.end());
        sch.push_back({a_orig, new_dep, b_orig, new_arr});
        int cur_city = b_orig;
        int cur_time = new_arr;
        for (int j = p+1; j < (int)backup.size(); ++j) {
            const Flight &orig = backup[j];
            int required_tt = travel_time_minutes(cities[orig.a].x, cities[orig.a].y, cities[orig.b].x, cities[orig.b].y);
            if (orig.a == cur_city && orig.dep >= cur_time && orig.arr - orig.dep == required_tt) {
                sch.push_back(orig);
                cur_city = orig.b;
                cur_time = orig.arr;
            } else {
                vector<Flight> tail = greedy_extend_from(cities, cur_city, cur_time);
                sch.insert(sch.end(), tail.begin(), tail.end());
                break;
            }
        }
        return {true, k};
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; int R;
    if (!(cin >> N >> R)) return 0;
    vector<City> cities(N);
    for (int i = 0; i < N; ++i) {
        long long xi, yi, wi;
        cin >> xi >> yi >> wi;
        cities[i].x = (double)xi;
        cities[i].y = (double)yi;
        cities[i].w = wi;
    }
    int M; cin >> M;
    vector<Flight> square_flights;
    square_flights.reserve(M);
    for (int i = 0; i < M; ++i) {
        int a, b; string s_str, t_str;
        cin >> a >> s_str >> b >> t_str;
        int smin = parse_time(s_str);
        int tmin = parse_time(t_str);
        square_flights.push_back({a-1, smin, b-1, tmin});
    }
    int K; cin >> K;

    // Precompute Tlist and ODlist (pairs with distance >= 0.25R)
    vector<int> Tlist = build_target_times();
    vector<pair<int,int>> ODlist;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (i == j) continue;
            double d = hypot(cities[i].x - cities[j].x, cities[i].y - cities[j].y);
            if (d + 1e-9 >= 0.25 * (double)R) ODlist.emplace_back(i,j);
        }
    }

    // Precompute s_sq_all using square_flights
    vector<vector<int>> fba_sq = build_flights_by_arrival(square_flights, N);
    vector<vector<vector<int>>> s_sq_all = compute_latest_deps_all(N, square_flights, fba_sq, Tlist);

    // Build initial schedules
    Schedule schedules = build_initial(cities, K);

    // Evaluate initial s_ci and share-rate
    vector<vector<vector<int>>> s_ci_all = compute_s_ci_all(schedules, cities, Tlist);
    long double best_score = compute_share_rate(s_sq_all, s_ci_all, ODlist, Tlist, cities);
    Schedule best_sched = schedules;

    // Random
    mt19937_64 rng((unsigned)chrono::high_resolution_clock::now().time_since_epoch().count());

    // Time limit set to nearly 2 seconds
    const double TIME_LIMIT = 0.99; // seconds (use full 2s budget)
    const long double T0 = 1.0L;
    const long double Tmin = 1e-6L;

    auto time_start = chrono::high_resolution_clock::now();
    long long iter = 0;
    while (true) {
        auto now = chrono::high_resolution_clock::now();
        double elapsed = chrono::duration_cast<chrono::duration<double>>(now - time_start).count();
        if (elapsed > TIME_LIMIT) break;
        long double frac = elapsed / TIME_LIMIT;
        if (frac > 1.0) frac = 1.0;
        long double T = T0 * (1.0L - frac) + Tmin * frac;

        ++iter;
        Schedule old_sched = schedules;
        auto res = apply_random_neighbor(schedules, cities, rng);
        if (!res.first) {
            schedules = old_sched;
            continue;
        }

        // compute s_ci_all for new schedules (full recompute)
        vector<vector<vector<int>>> new_s_ci_all = compute_s_ci_all(schedules, cities, Tlist);
        long double new_score = compute_share_rate(s_sq_all, new_s_ci_all, ODlist, Tlist, cities);

        bool accept = false;
        if (new_score > best_score) {
            accept = true;
            best_score = new_score;
            best_sched = schedules;
        } else {
            long double diff = new_score - best_score; // <= 0
            long double prob = expl(diff / max((long double)1e-18, T));
            uniform_real_distribution<long double> ud(0.0L, 1.0L);
            if (ud(rng) < prob) accept = true;
            else accept = false;
        }
        if (!accept) {
            schedules = old_sched; // revert
        }
    }

    // Output best solution in required format
    for (int k = 0; k < K; ++k) {
        if (k < (int)best_sched.size()) {
            const auto &sch = best_sched[k];
            cout << sch.size() << '\n';
            for (const auto &f : sch) {
                cout << (f.a + 1) << " " << fmt_time(f.dep) << " " << (f.b + 1) << " " << fmt_time(f.arr) << '\n';
            }
        } else {
            cout << 0 << '\n';
        }
    }

    // Print diagnostics to stderr: elapsed time and iterations
    auto time_end = chrono::high_resolution_clock::now();
    double total_elapsed = chrono::duration_cast<chrono::duration<double>>(time_end - time_start).count();
    cerr.setf(std::ios::fixed); cerr<<setprecision(6);
    cerr << "elapsed_seconds: " << total_elapsed << " iterations: " << iter << '\n';

    return 0;
}