結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 Shymohn _
|
| 提出日時 | 2026-02-25 22:34:53 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 957 ms / 1,000 ms |
| コード長 | 19,522 bytes |
| 記録 | |
| コンパイル時間 | 8,272 ms |
| コンパイル使用メモリ | 401,460 KB |
| 実行使用メモリ | 7,848 KB |
| スコア | 36,468,480 |
| 最終ジャッジ日時 | 2026-02-25 22:41:40 |
| 合計ジャッジ時間 | 109,816 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
struct City { double x, y; long long w; };
struct Flight { int a; int dep; int b; int arr; }; // dep/arr in minutes from midnight
struct InFlight { int a; int dep; int arr; }; // used in flights-by-arrival lists
inline 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);
}
inline int parse_time(const string &s){
int hh = (s[0]-'0')*10 + (s[1]-'0');
int mm = (s[3]-'0')*10 + (s[4]-'0');
return hh*60 + mm;
}
const int START = 6*60; // 360
const int END = 21*60; // 1260
const int INF_NEG = -1000000000;
using Schedule = vector<vector<Flight>>;
// Build list of target arrival times: 11:00..21:00 step 30
static inline vector<int> build_target_times() {
vector<int> T;
for (int t = 11*60; t <= 21*60; t += 30) T.push_back(t);
return T;
}
// Precompute travel time matrix (5-minute-ceiled formula)
static vector<vector<int>> build_travel_matrix(const vector<City> &cities) {
int N = (int)cities.size();
vector<vector<int>> travel(N, vector<int>(N));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (i == j) { travel[i][j] = 0; continue; }
double dx = cities[i].x - cities[j].x;
double dy = cities[i].y - cities[j].y;
double d = hypot(dx, dy);
double raw = 60.0 * d / 800.0 + 40.0;
int tt = (int)ceil(raw / 5.0) * 5;
travel[i][j] = tt;
}
}
return travel;
}
// Greedy extend from (cur, time) for a single plane using travel matrix
static vector<Flight> greedy_extend_from(const vector<City> &cities, const vector<vector<int>> &travel, 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[cur][j];
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;
}
// Build initial schedule as hub <-> top25 (or up to available) round-robin
static Schedule build_initial(const vector<City> &cities, int K, const vector<vector<int>> &travel) {
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;
vec.reserve(N);
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; targets.reserve(topCount);
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;
auto &sch = schedules[k];
while (true) {
int next = (cur == hub) ? target : hub;
int tt = travel[cur][next];
int dep = time;
int arr = dep + tt;
if (arr > END) break;
sch.push_back({cur, dep, next, arr});
cur = next;
time = arr;
}
}
return schedules;
}
// Build flights-by-arrival (fba) from schedules
static vector<vector<InFlight>> build_fba_from_schedules(const Schedule &schedules, int N) {
vector<vector<InFlight>> fba(N);
for (const auto &sch : schedules) {
for (const auto &f : sch) {
fba[f.b].push_back({f.a, f.dep, f.arr});
}
}
return fba;
}
// Build fba from generic flights vector
static vector<vector<InFlight>> build_fba_from_flights(const vector<Flight> &flights, int N) {
vector<vector<InFlight>> fba(N);
for (const auto &f : flights) fba[f.b].push_back({f.a, f.dep, f.arr});
return fba;
}
// Compute latest deps for a single (dest, target T) using current fba (reverse BFS)
static vector<int> compute_latest_dep_one(int N, int dest, int T, const vector<vector<InFlight>> &fba) {
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();
const auto &vec = fba[v];
for (int i = 0; i < (int)vec.size(); ++i) {
const InFlight &inf = vec[i];
if (inf.arr <= L[v]) {
int u = inf.a;
if (L[u] < inf.dep) {
L[u] = inf.dep;
dq.push_back(u);
}
}
}
}
return L;
}
// Compute latest deps for all (dest,ti) — used initially for s_ci and s_sq
static vector<vector<vector<int>>> compute_latest_deps_all_from_fba(int N, const vector<vector<InFlight>> &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) {
res[dest][ti] = compute_latest_dep_one(N, dest, Tlist[ti], fba);
}
}
return res;
}
// Compute share-rate S given s_sq and s_ci
static 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 (const 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);
}
// Apply neighbor change to schedules: modify schedules in-place for one plane.
// Returns tuple: (changed?, plane_index, oldFlights, newFlights)
static tuple<bool,int,vector<Flight>,vector<Flight>> apply_random_neighbor_return_changes(Schedule &schedules, const vector<City> &cities, const vector<vector<int>> &travel, 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);
vector<Flight> oldFlights = sch; // backup of old flights for this plane
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, travel, hub, START);
if (!newsch.empty()) {
sch = std::move(newsch);
return {true, k, oldFlights, sch};
} else return {false, -1, oldFlights, vector<Flight>()};
}
if (op == 0) {
// change destination of random flight p (minimal change)
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; cand.reserve(cities.size());
int N = (int)cities.size();
for (int j = 0; j < N; ++j) {
if (j == cur) continue;
int tt = travel[cur][j];
if (time + tt <= END) cand.push_back(j);
}
if (cand.empty()) return {false, -1, oldFlights, vector<Flight>()};
int cur_b = sch[p].b;
vector<int> cand2; cand2.reserve(cand.size());
for (int v : cand) if (v != cur_b) cand2.push_back(v);
if (cand2.empty()) return {false, -1, oldFlights, vector<Flight>()};
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[cur][newdest];
int dep = time;
int arr = dep + tt;
sch.push_back({cur, dep, newdest, arr});
int cur_city = newdest;
int cur_time = arr;
// try to preserve suffix where possible
for (int j = p+1; j < (int)oldFlights.size(); ++j) {
const Flight &orig = oldFlights[j];
int required_tt = travel[orig.a][orig.b];
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, travel, cur_city, cur_time);
sch.insert(sch.end(), tail.begin(), tail.end());
break;
}
}
return {true, k, oldFlights, sch};
} else {
// shift departure of random flight p by +/-5
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, oldFlights, vector<Flight>()};
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)oldFlights.size(); ++j) {
const Flight &orig = oldFlights[j];
int required_tt = travel[orig.a][orig.b];
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, travel, cur_city, cur_time);
sch.insert(sch.end(), tail.begin(), tail.end());
break;
}
}
return {true, k, oldFlights, sch};
}
}
// helper: remove a single inflight entry matching (a,dep,arr) from fba[b]; returns true if removed
static bool remove_inflight_from_fba(vector<vector<InFlight>> &fba, const InFlight &inf, int b) {
auto &vec = fba[b];
for (auto it = vec.begin(); it != vec.end(); ++it) {
if (it->a == inf.a && it->dep == inf.dep && it->arr == inf.arr) {
*it = vec.back();
vec.pop_back();
return true;
}
}
return false;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, 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;
// prepare
vector<int> Tlist = build_target_times();
int TT = (int)Tlist.size();
vector<vector<int>> travel = build_travel_matrix(cities);
// OD list (distance >= 0.25R)
vector<pair<int,int>> ODlist; ODlist.reserve(N*N/2);
for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) if (i!=j) {
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);
}
// build s_sq_all from square_flights: use fba of square flights
vector<vector<InFlight>> fba_sq = build_fba_from_flights(square_flights, max(1,N));
vector<vector<vector<int>>> s_sq_all = compute_latest_deps_all_from_fba(N, fba_sq, Tlist);
// initial schedules
Schedule schedules = build_initial(cities, K, travel);
// build fba_current from schedules
vector<vector<InFlight>> fba_cur = build_fba_from_schedules(schedules, max(1,N));
// compute initial s_ci_all
vector<vector<vector<int>>> s_ci_all = compute_latest_deps_all_from_fba(N, fba_cur, 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
const double TIME_LIMIT = 0.95; // seconds
const long double T0 = 1.0L, Tmin = 1e-3L;
auto tstart = 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 - tstart).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;
// propose neighbor, get changed plane and old/new flights
auto tup = apply_random_neighbor_return_changes(schedules, cities, travel, rng);
bool changed = get<0>(tup);
int plane = get<1>(tup);
vector<Flight> oldFlights = get<2>(tup);
vector<Flight> newFlights = get<3>(tup);
if (!changed) continue;
// BEFORE updating fba_cur, decide affected (dest,ti) candidates using old s_ci_all
int changed_count = (int)oldFlights.size() + (int)newFlights.size();
vector<vector<char>> affected(N, vector<char>(TT, 0));
// use old s_ci_all
for (const Flight &f : oldFlights) {
int b = f.b;
int arr_old = f.arr;
for (int dest = 0; dest < N; ++dest) {
for (int ti = 0; ti < TT; ++ti) {
if (!affected[dest][ti] && s_ci_all[dest][ti][b] >= arr_old) affected[dest][ti] = 1;
}
}
}
for (const Flight &f : newFlights) {
int b = f.b;
int arr_new = f.arr;
for (int dest = 0; dest < N; ++dest) {
for (int ti = 0; ti < TT; ++ti) {
if (!affected[dest][ti] && s_ci_all[dest][ti][b] >= arr_new) affected[dest][ti] = 1;
}
}
}
// Now update fba_cur: remove oldFlights, add newFlights
bool remove_ok = true;
for (const Flight &f : oldFlights) {
InFlight inf{f.a, f.dep, f.arr};
bool r = remove_inflight_from_fba(fba_cur, inf, f.b);
if (!r) {
// shouldn't happen; but we'll continue
remove_ok = false;
}
}
for (const Flight &f : newFlights) {
fba_cur[f.b].push_back({f.a, f.dep, f.arr});
}
// For all affected (dest,ti), recompute L_new and update s_ci_all[dest][ti] if changed
for (int dest = 0; dest < N; ++dest) {
for (int ti = 0; ti < TT; ++ti) {
if (!affected[dest][ti]) continue;
vector<int> Lnew = compute_latest_dep_one(N, dest, Tlist[ti], fba_cur);
// compare Lnew with s_ci_all[dest][ti]
bool diff = false;
for (int c = 0; c < N; ++c) {
if (Lnew[c] != s_ci_all[dest][ti][c]) { diff = true; break; }
}
if (diff) {
s_ci_all[dest][ti].swap(Lnew); // update
}
}
}
// Evaluate new score
long double new_score = compute_share_rate(s_sq_all, 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) {
// revert schedules and fba_cur and s_ci_all (we need to undo fba changes and s_ci changes)
// revert schedules
schedules[plane] = oldFlights;
// revert fba_cur: remove newFlights additions, re-add oldFlights
for (const Flight &f : newFlights) {
// remove one matching inflight from fba_cur[f.b]
InFlight inf{f.a, f.dep, f.arr};
bool r = remove_inflight_from_fba(fba_cur, inf, f.b);
(void)r;
}
for (const Flight &f : oldFlights) {
fba_cur[f.b].push_back({f.a, f.dep, f.arr});
}
// recompute s_ci_all for affected (dest,ti) back to previous values:
// Easiest correct way: recompute L_old for affected (dest,ti) using fba constructed from reverting; this restores s_ci_all
for (int dest = 0; dest < N; ++dest) {
for (int ti = 0; ti < TT; ++ti) {
if (!affected[dest][ti]) continue;
vector<int> Lold = compute_latest_dep_one(N, dest, Tlist[ti], fba_cur);
s_ci_all[dest][ti].swap(Lold);
}
}
}
// otherwise accept: s_ci_all is already updated and fba_cur already reflects new flights
}
// 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';
}
}
// diagnostics
auto tend = chrono::high_resolution_clock::now();
double total_elapsed = chrono::duration_cast<chrono::duration<double>>(tend - tstart).count();
cerr.setf(std::ios::fixed); cerr<<setprecision(6);
cerr << "elapsed_seconds: " << total_elapsed << " iterations: " << iter << '\n';
return 0;
}