結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 prussian_coder
|
| 提出日時 | 2026-02-25 21:25:30 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 907 ms / 1,000 ms |
| コード長 | 33,047 bytes |
| 記録 | |
| コンパイル時間 | 7,367 ms |
| コンパイル使用メモリ | 381,140 KB |
| 実行使用メモリ | 7,848 KB |
| スコア | 38,055,177 |
| 最終ジャッジ日時 | 2026-02-25 21:27:14 |
| 合計ジャッジ時間 | 104,141 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
// Constants
const int N = 47;
const int R = 1000;
const int M_FLIGHTS = 400;
const int K = 25;
const int TIME_MIN = 360; // 06:00 in minutes
const int TIME_MAX = 1260; // 21:00 in minutes
const int TIME_SLOTS = 181; // (1260-360)/5 + 1
const int NUM_TARGETS = 21; // 11:00, 11:30, ..., 21:00
const int NEG_INF = -1000000;
// Globals
int cx[N], cy[N], cw[N]; // city coords and population
int sq_a[M_FLIGHTS], sq_b[M_FLIGHTS], sq_s[M_FLIGHTS], sq_t[M_FLIGHTS]; // square flights
double dist_table[N][N];
int flight_time[N][N]; // in minutes, 0 if same city
bool valid_pair[N][N]; // distance >= 250
// target arrival times: 11:00=660, 11:30=690, ..., 21:00=1260
int target_times[NUM_TARGETS];
// s_sq[i][j][t] = latest departure from i to reach j by target_times[t] using Square only
int s_sq[N][N][NUM_TARGETS];
// Random
mt19937 rng(42);
int parse_time(const string& s) {
int h = stoi(s.substr(0, 2));
int m = stoi(s.substr(3, 2));
return h * 60 + m;
}
string format_time(int t) {
char buf[6];
sprintf(buf, "%02d:%02d", t / 60, t % 60);
return string(buf);
}
int calc_flight_time(double d) {
double raw = 60.0 * d / 800.0 + 40.0;
int rounded = (int)ceil(raw / 5.0) * 5;
return rounded;
}
// Compute s_sq for all (i, j, t_idx) using reverse Dijkstra from j at time target_times[t_idx]
void compute_square_dijkstra() {
// Build adjacency: for each flight, it goes from sq_a to sq_b, depart sq_s, arrive sq_t
// Reverse: from sq_b at time sq_t, we can reach sq_a at time sq_s (latest departure = sq_s)
// We want: for each destination j and target time T, find latest departure from each city i
// For each (j, t_idx):
// Initialize best[j] = target_times[t_idx]
// Use max-heap (latest departure first)
// For each city reached at time arr_time, look at all flights arriving at that city
// with arrival time <= arr_time. The departure time of that flight is a candidate.
// Build reverse adjacency: for each city b, list of (a, depart_time, arrive_time)
vector<vector<tuple<int,int,int>>> rev_adj(N);
for (int f = 0; f < M_FLIGHTS; f++) {
rev_adj[sq_b[f]].emplace_back(sq_a[f], sq_s[f], sq_t[f]);
}
// Sort by arrival time for each destination
for (int b = 0; b < N; b++) {
sort(rev_adj[b].begin(), rev_adj[b].end(), [](auto& a, auto& b) {
return get<2>(a) > get<2>(b); // sort by arrive_time descending
});
}
for (int t_idx = 0; t_idx < NUM_TARGETS; t_idx++) {
int T = target_times[t_idx];
for (int j = 0; j < N; j++) {
// best[i] = latest time you can depart from i to reach j by time T
int best[N];
fill(best, best + N, NEG_INF);
best[j] = T;
// Max-heap: (available_time_at_city, city)
priority_queue<pair<int,int>> pq;
pq.push({T, j});
while (!pq.empty()) {
auto [arr_time, city] = pq.top();
pq.pop();
if (arr_time < best[city]) continue;
// Look at all flights arriving at 'city' with arrive_time <= arr_time
for (auto& [from, dep, arr] : rev_adj[city]) {
if (arr > arr_time) continue;
if (arr < TIME_MIN) break; // sorted descending, so no more valid
// We can take this flight: depart from 'from' at time 'dep'
if (dep > best[from]) {
best[from] = dep;
pq.push({dep, from});
}
}
}
for (int i = 0; i < N; i++) {
s_sq[i][j][t_idx] = best[i];
}
}
}
}
// Circle Airlines schedule
struct Flight {
int from, to, depart, arrive; // 0-indexed cities, times in minutes
};
struct Airplane {
vector<Flight> flights;
};
// Compute s_ci[i][j][t_idx] given Circle Airlines schedule
// Returns total score
long long evaluate(const vector<Airplane>& planes, bool compute_s_ci = false,
vector<vector<vector<int>>>* out_s_ci = nullptr) {
// Build Circle adjacency
vector<vector<tuple<int,int,int>>> ci_rev_adj(N);
for (auto& plane : planes) {
for (auto& f : plane.flights) {
ci_rev_adj[f.to].emplace_back(f.from, f.depart, f.arrive);
}
}
for (int b = 0; b < N; b++) {
sort(ci_rev_adj[b].begin(), ci_rev_adj[b].end(), [](auto& a, auto& b) {
return get<2>(a) > get<2>(b);
});
}
long long v_ci = 0, v_sq = 0;
for (int t_idx = 0; t_idx < NUM_TARGETS; t_idx++) {
int T = target_times[t_idx];
for (int j = 0; j < N; j++) {
int best[N];
fill(best, best + N, NEG_INF);
best[j] = T;
priority_queue<pair<int,int>> pq;
pq.push({T, j});
while (!pq.empty()) {
auto [arr_time, city] = pq.top();
pq.pop();
if (arr_time < best[city]) continue;
for (auto& [from, dep, arr] : ci_rev_adj[city]) {
if (arr > arr_time) continue;
if (dep > best[from]) {
best[from] = dep;
pq.push({dep, from});
}
}
}
for (int i = 0; i < N; i++) {
if (!valid_pair[i][j]) continue;
int sci = best[i];
int ssq = s_sq[i][j][t_idx];
long long w = (long long)cw[i] * cw[j];
if (sci > ssq) {
v_ci += w;
} else {
v_sq += w;
}
}
if (compute_s_ci && out_s_ci) {
for (int i = 0; i < N; i++) {
(*out_s_ci)[i][j][t_idx] = best[i];
}
}
}
}
return v_ci; // return v_ci; total = v_ci + v_sq, share = v_ci / total
}
// Quick incremental evaluation: only recompute affected destinations
// For efficiency during SA, we do full evaluation but optimize later if needed
bool is_valid_schedule(const Airplane& plane) {
for (int j = 0; j < (int)plane.flights.size(); j++) {
auto& f = plane.flights[j];
if (f.from < 0 || f.from >= N || f.to < 0 || f.to >= N) return false;
if (f.from == f.to) return false;
if (f.depart < TIME_MIN || f.arrive > TIME_MAX) return false;
if (f.depart % 5 != 0 || f.arrive % 5 != 0) return false;
if (f.arrive - f.depart != flight_time[f.from][f.to]) return false;
if (j > 0) {
if (plane.flights[j-1].to != f.from) return false;
if (plane.flights[j-1].arrive > f.depart) return false;
}
}
return true;
}
// Build a route for one airplane: visit a sequence of cities with given start time
vector<Flight> build_route(const vector<int>& cities, int start_time) {
vector<Flight> flights;
int cur_time = start_time;
for (int i = 0; i + 1 < (int)cities.size(); i++) {
int from = cities[i], to = cities[i+1];
if (from == to) continue;
int ft = flight_time[from][to];
// Round cur_time up to next 5-minute slot
int dep = ((cur_time + 4) / 5) * 5;
int arr = dep + ft;
if (arr > TIME_MAX) break;
if (dep < TIME_MIN) dep = TIME_MIN;
arr = dep + ft;
if (arr > TIME_MAX) break;
flights.push_back({from, to, dep, arr});
cur_time = arr;
}
return flights;
}
// Initial solution: hub-and-spoke from top cities
vector<Airplane> build_initial_solution() {
vector<Airplane> planes(K);
// Sort cities by population (already sorted in input, city 0 is largest)
// Pick top cities as important destinations
// Strategy: each plane does shuttle routes between city pairs
// covering as many high-weight pairs as possible
// Get top ~15 cities by population
vector<int> top_cities;
for (int i = 0; i < min(N, 20); i++) top_cities.push_back(i);
// Hub city = city 0 (highest population)
int hub = 1; // 0-indexed city 1 (second highest pop) - actually let's use 0
// Try: each plane shuttles between hub and a spoke city
// Important pairs by weight
vector<tuple<long long, int, int>> pairs;
for (int i = 0; i < N; i++) {
for (int j = i+1; j < N; j++) {
if (valid_pair[i][j]) {
long long w = (long long)cw[i] * cw[j];
pairs.push_back({w, i, j});
}
}
}
sort(pairs.rbegin(), pairs.rend());
// Strategy: for each plane, create a route that visits many cities
// covering high-weight pairs efficiently
// Simple approach: each plane does a chain of flights visiting different cities
// starting from different times to cover the time range
// Better strategy: hub-and-spoke
// Plane k: hub -> spoke_k -> hub -> spoke_k -> hub -> ...
// This creates many connections through the hub
// Select spoke cities: top cities excluding hub
vector<int> spokes;
for (int i = 0; i < N && (int)spokes.size() < K; i++) {
if (i != 0) spokes.push_back(i); // 0-indexed, so city 0 = hub
}
// Each plane assigned to one spoke
for (int k = 0; k < K; k++) {
int spoke = spokes[k % spokes.size()];
vector<int> route;
// Start time staggered
int base_start = TIME_MIN + (k * 30) % 180; // stagger by 30min, wrap at 3hr
int cur_time = base_start;
int cur_city = 0; // start from hub
bool at_hub = true;
route.push_back(cur_city);
while (cur_time + flight_time[cur_city][at_hub ? spoke : 0] <= TIME_MAX) {
int next = at_hub ? spoke : 0;
route.push_back(next);
cur_time += flight_time[cur_city][next];
cur_city = next;
at_hub = !at_hub;
}
planes[k].flights = build_route(route, base_start);
}
return planes;
}
// Build initial solution v2: greedily assign planes to cover high-weight pairs
vector<Airplane> build_initial_solution_v2() {
vector<Airplane> planes(K);
// Important pairs by weight
vector<tuple<long long, int, int>> pairs;
for (int i = 0; i < N; i++) {
for (int j = i+1; j < N; j++) {
if (valid_pair[i][j]) {
long long w = 2LL * cw[i] * cw[j]; // both directions
pairs.push_back({w, i, j});
}
}
}
sort(pairs.rbegin(), pairs.rend());
// For each plane, create a tour visiting several top cities
// Different starting cities and times for diversity
// Create city visit sequences
// Top 10 cities: 0,1,2,3,4,5,6,7,8,9
// Each plane gets a circular tour through a subset
// Strategy: divide day into time bands, assign planes to cover different bands
// Each plane: chain of flights visiting top cities
for (int k = 0; k < K; k++) {
// Pick a starting city and a set of cities to visit
int start_city;
vector<int> visit_order;
if (k < 15) {
// Hub-spoke: shuttle between city 0 and a spoke
int spoke = (k % 15) + 1; // cities 1-15
start_city = 0;
int base_start = TIME_MIN + ((k / 15) * 150 + (k % 15) * 10);
if (base_start > TIME_MAX - 200) base_start = TIME_MIN + (k * 7) % 120;
vector<int> route;
int cur = start_city;
int ct = base_start;
route.push_back(cur);
while (true) {
int next = (cur == 0) ? spoke : 0;
int ft = flight_time[cur][next];
if (ct + ft > TIME_MAX) break;
route.push_back(next);
ct += ft;
cur = next;
}
planes[k].flights = build_route(route, base_start);
} else {
// Chain tour through top cities
int group = k - 15;
int base_start = TIME_MIN + group * 60;
if (base_start > TIME_MAX - 300) base_start = TIME_MIN;
// Visit sequence: cycle through some cities
vector<int> cities_to_visit;
for (int i = 0; i < 8; i++) {
cities_to_visit.push_back((group * 3 + i * 2) % 20);
}
vector<int> route;
route.push_back(cities_to_visit[0]);
for (int i = 1; i < (int)cities_to_visit.size(); i++) {
if (cities_to_visit[i] != route.back()) {
route.push_back(cities_to_visit[i]);
}
}
planes[k].flights = build_route(route, base_start);
}
}
return planes;
}
// Improved initial solution: multi-hub approach
vector<Airplane> build_initial_solution_v3() {
vector<Airplane> planes(K);
// Hub-spoke with multiple hubs for better coverage
// Hub 0 (city 0): planes 0-7 (8 planes)
// Hub 1 (city 1): planes 8-14 (7 planes)
// Hub 2 (city 2): planes 15-19 (5 planes)
// Touring: planes 20-24 (5 planes)
// For hub planes, shuttle to different spoke cities at staggered times
auto make_hub_shuttle = [&](int hub, int spoke, int start_time) -> vector<Flight> {
vector<int> route;
int cur = hub;
int ct = start_time;
route.push_back(cur);
while (true) {
int next = (cur == hub) ? spoke : hub;
int ft = flight_time[cur][next];
int dep = ((ct + 4) / 5) * 5;
if (dep + ft > TIME_MAX) break;
route.push_back(next);
ct = dep + ft;
cur = next;
}
return build_route(route, start_time);
};
// Hub 0 spokes: top importance cities
vector<int> hub0_spokes = {1, 2, 3, 4, 5, 6, 7, 8};
for (int k = 0; k < 8; k++) {
int spoke = hub0_spokes[k];
int start = TIME_MIN + k * 20;
planes[k].flights = make_hub_shuttle(0, spoke, start);
}
// Hub 1 spokes
vector<int> hub1_spokes = {0, 2, 3, 4, 5, 6, 7};
for (int k = 8; k < 15; k++) {
int spoke = hub1_spokes[k - 8];
int start = TIME_MIN + (k - 8) * 25;
planes[k].flights = make_hub_shuttle(1, spoke, start);
}
// Hub 2 spokes
vector<int> hub2_spokes = {0, 1, 3, 4, 5};
for (int k = 15; k < 20; k++) {
int spoke = hub2_spokes[k - 15];
int start = TIME_MIN + (k - 15) * 30;
planes[k].flights = make_hub_shuttle(2, spoke, start);
}
// Touring planes: visit sequences of cities
for (int k = 20; k < K; k++) {
int group = k - 20;
vector<int> tour;
// Create different tours for each plane
int offset = group * 5;
for (int i = 0; i < 10; i++) {
tour.push_back((offset + i * 3) % N);
}
// Remove consecutive duplicates
vector<int> route;
route.push_back(tour[0]);
for (int i = 1; i < (int)tour.size(); i++) {
if (tour[i] != route.back()) route.push_back(tour[i]);
}
planes[k].flights = build_route(route, TIME_MIN + group * 40);
}
return planes;
}
// Simulated annealing
void simulated_annealing(vector<Airplane>& planes, double time_limit_sec) {
auto start = chrono::steady_clock::now();
long long cur_score = evaluate(planes);
long long best_score = cur_score;
vector<Airplane> best_planes = planes;
int iter = 0;
int accept_count = 0;
auto elapsed = [&]() -> double {
auto now = chrono::steady_clock::now();
return chrono::duration<double>(now - start).count();
};
double T_start = 1e14;
double T_end = 1e10;
while (true) {
double t = elapsed();
if (t >= time_limit_sec) break;
double progress = t / time_limit_sec;
double T = T_start * pow(T_end / T_start, progress);
iter++;
// Choose operation
int op = rng() % 100;
int plane_idx = rng() % K;
Airplane old_plane = planes[plane_idx];
if (op < 40) {
// Operation 1: Change a spoke city in a hub-spoke route
auto& flights = planes[plane_idx].flights;
if (flights.empty()) continue;
// Pick a random flight and change destination
int fi = rng() % flights.size();
int new_city = rng() % N;
if (new_city == flights[fi].from) continue;
// Rebuild the rest of the route from this flight
vector<int> route;
for (int i = 0; i <= fi; i++) {
if (i == 0) route.push_back(flights[i].from);
if (i < fi) route.push_back(flights[i].to);
}
route.push_back(new_city);
// Continue with alternating pattern or random cities
int cur = new_city;
int ct = route.size() > 1 ? flights[fi].depart : TIME_MIN;
// Estimate arrival at new_city
int ft_to_new = flight_time[flights[fi].from][new_city];
int dep_new = flights[fi].depart;
int arr_new = dep_new + ft_to_new;
if (arr_new > TIME_MAX) {
planes[plane_idx] = old_plane;
continue;
}
// Add more flights after new_city
ct = arr_new;
// Try to go back to a hub (city 0 or 1 or 2)
for (int tries = 0; tries < 10; tries++) {
int next = rng() % min(N, 20);
if (next == cur) continue;
int ft = flight_time[cur][next];
int dep = ((ct + 4) / 5) * 5;
if (dep + ft > TIME_MAX) break;
route.push_back(next);
ct = dep + ft;
cur = next;
}
int start_time = flights.empty() ? TIME_MIN : flights[0].depart;
if (fi == 0) {
start_time = flights[0].depart;
}
planes[plane_idx].flights = build_route(route, start_time);
} else if (op < 60) {
// Operation 2: Shift entire schedule by +-5 to +-15 minutes
int shift = ((int)(rng() % 7) - 3) * 5; // -15 to +15
if (shift == 0) continue;
bool ok = true;
for (auto& f : planes[plane_idx].flights) {
f.depart += shift;
f.arrive += shift;
if (f.depart < TIME_MIN || f.arrive > TIME_MAX) {
ok = false;
break;
}
}
if (!ok) {
planes[plane_idx] = old_plane;
continue;
}
} else if (op < 80) {
// Operation 3: Completely rebuild one plane's route
auto& flights = planes[plane_idx].flights;
// Pick random start city and time
int start_city = rng() % min(N, 25);
int start_time = TIME_MIN + (rng() % 36) * 5; // random 5-min slot in first 3 hours
vector<int> route;
route.push_back(start_city);
int cur = start_city;
int ct = start_time;
// Greedily add cities
for (int tries = 0; tries < 15; tries++) {
// Pick a random city from top 25 or all
int next;
if (rng() % 3 == 0) {
next = rng() % N; // any city
} else {
next = rng() % min(N, 20); // top cities
}
if (next == cur) continue;
int ft = flight_time[cur][next];
int dep = ((ct + 4) / 5) * 5;
if (dep + ft > TIME_MAX) continue;
route.push_back(next);
ct = dep + ft;
cur = next;
}
planes[plane_idx].flights = build_route(route, start_time);
} else {
// Operation 4: Swap two planes' routes or swap a segment
int other = rng() % K;
if (other == plane_idx) continue;
swap(planes[plane_idx], planes[other]);
// This doesn't change score, skip evaluation
continue;
}
// Evaluate
long long new_score = evaluate(planes);
long long delta = new_score - cur_score;
if (delta > 0 || (T > 0 && exp((double)delta / T) > (double)(rng() % 1000000) / 1000000.0)) {
cur_score = new_score;
accept_count++;
if (cur_score > best_score) {
best_score = cur_score;
best_planes = planes;
}
} else {
planes[plane_idx] = old_plane;
}
}
planes = best_planes;
fprintf(stderr, "SA: iter=%d, accept=%d, best_score=%lld\n", iter, accept_count, best_score);
}
// Fast evaluation: only compute a partial score for a single plane change
// This caches Circle Airlines adjacency and only updates for the changed plane
struct FastEvaluator {
vector<Airplane>* planes;
// All circle flights combined
vector<tuple<int,int,int>> ci_rev_adj[N]; // (from, depart, arrive)
long long total_v_ci, total_v_sq;
void init(vector<Airplane>* p) {
planes = p;
rebuild_all();
}
void rebuild_all() {
for (int i = 0; i < N; i++) ci_rev_adj[i].clear();
for (auto& plane : *planes) {
for (auto& f : plane.flights) {
ci_rev_adj[f.to].emplace_back(f.from, f.depart, f.arrive);
}
}
for (int i = 0; i < N; i++) {
sort(ci_rev_adj[i].begin(), ci_rev_adj[i].end(), [](auto& a, auto& b) {
return get<2>(a) > get<2>(b);
});
}
}
long long compute_score() {
long long v_ci = 0, v_sq = 0;
for (int t_idx = 0; t_idx < NUM_TARGETS; t_idx++) {
int T = target_times[t_idx];
for (int j = 0; j < N; j++) {
int best[N];
fill(best, best + N, NEG_INF);
best[j] = T;
priority_queue<pair<int,int>> pq;
pq.push({T, j});
while (!pq.empty()) {
auto [arr_time, city] = pq.top();
pq.pop();
if (arr_time < best[city]) continue;
for (auto& [from, dep, arr] : ci_rev_adj[city]) {
if (arr > arr_time) continue;
if (dep > best[from]) {
best[from] = dep;
pq.push({dep, from});
}
}
}
for (int i = 0; i < N; i++) {
if (!valid_pair[i][j]) continue;
int sci = best[i];
int ssq = s_sq[i][j][t_idx];
long long w = (long long)cw[i] * cw[j];
if (sci > ssq) {
v_ci += w;
} else {
v_sq += w;
}
}
}
}
total_v_ci = v_ci;
total_v_sq = v_sq;
return v_ci;
}
};
// Improved SA with fast evaluator
void simulated_annealing_v2(vector<Airplane>& planes, double time_limit_sec) {
auto start = chrono::steady_clock::now();
FastEvaluator eval;
eval.init(&planes);
long long cur_score = eval.compute_score();
long long best_score = cur_score;
vector<Airplane> best_planes = planes;
int iter = 0;
int accept_count = 0;
auto elapsed = [&]() -> double {
auto now = chrono::steady_clock::now();
return chrono::duration<double>(now - start).count();
};
double T_start = 5e13;
double T_end = 1e10;
while (true) {
double t = elapsed();
if (t >= time_limit_sec) break;
double progress = t / time_limit_sec;
double T = T_start * pow(T_end / T_start, progress);
iter++;
int plane_idx = rng() % K;
Airplane old_plane = planes[plane_idx];
int op = rng() % 100;
if (op < 35) {
// Rebuild route: random chain through important cities
int start_city;
if (rng() % 2 == 0) {
start_city = rng() % 3; // top 3 cities
} else {
start_city = rng() % min(N, 15);
}
int start_time = TIME_MIN + (rng() % 60) * 5;
vector<int> route;
route.push_back(start_city);
int cur = start_city;
int ct = start_time;
for (int tries = 0; tries < 20; tries++) {
int next;
int r = rng() % 10;
if (r < 4) next = rng() % 3; // top 3
else if (r < 7) next = rng() % 10; // top 10
else if (r < 9) next = rng() % 20; // top 20
else next = rng() % N; // any
if (next == cur) continue;
int ft = flight_time[cur][next];
int dep = ((ct + 4) / 5) * 5;
if (dep + ft > TIME_MAX) continue;
route.push_back(next);
ct = dep + ft;
cur = next;
}
planes[plane_idx].flights = build_route(route, start_time);
} else if (op < 55) {
// Shift time +-5 to +-20 minutes
int shift = ((int)(rng() % 9) - 4) * 5;
if (shift == 0) shift = 5;
bool ok = true;
for (auto& f : planes[plane_idx].flights) {
f.depart += shift;
f.arrive += shift;
if (f.depart < TIME_MIN || f.arrive > TIME_MAX) { ok = false; break; }
}
if (!ok) {
planes[plane_idx] = old_plane;
continue;
}
} else if (op < 75) {
// Modify one flight's destination
auto& flights = planes[plane_idx].flights;
if (flights.size() < 2) {
// Rebuild instead
int start_city = rng() % 10;
int start_time = TIME_MIN + (rng() % 60) * 5;
vector<int> route = {start_city};
int cur = start_city;
int ct = start_time;
for (int tries = 0; tries < 15; tries++) {
int next = rng() % min(N, 20);
if (next == cur) continue;
int ft = flight_time[cur][next];
int dep = ((ct + 4) / 5) * 5;
if (dep + ft > TIME_MAX) continue;
route.push_back(next);
ct = dep + ft;
cur = next;
}
planes[plane_idx].flights = build_route(route, start_time);
} else {
// Pick a random split point and rebuild from there
int split = 1 + rng() % ((int)flights.size() - 1);
int cur = flights[split - 1].to;
int ct = flights[split - 1].arrive;
// Keep flights before split
vector<Flight> new_flights(flights.begin(), flights.begin() + split);
// Rebuild from split point
for (int tries = 0; tries < 15; tries++) {
int next;
int r = rng() % 10;
if (r < 4) next = rng() % 3;
else if (r < 7) next = rng() % 10;
else next = rng() % N;
if (next == cur) continue;
int ft = flight_time[cur][next];
int dep = ((ct + 4) / 5) * 5;
if (dep + ft > TIME_MAX) break;
new_flights.push_back({cur, next, dep, dep + ft});
ct = dep + ft;
cur = next;
}
planes[plane_idx].flights = new_flights;
}
} else {
// Hub-spoke shuttle rebuild
int hub, spoke;
if (rng() % 2 == 0) {
hub = 0;
spoke = 1 + rng() % (N - 1);
} else {
hub = rng() % 3;
spoke = rng() % N;
if (spoke == hub) continue;
}
int start_time = TIME_MIN + (rng() % 72) * 5; // 0 to 6 hours offset
vector<int> route;
int cur = hub;
int ct = start_time;
route.push_back(cur);
while (true) {
int next = (cur == hub) ? spoke : hub;
int ft = flight_time[cur][next];
int dep = ((ct + 4) / 5) * 5;
if (dep + ft > TIME_MAX) break;
route.push_back(next);
ct = dep + ft;
cur = next;
}
planes[plane_idx].flights = build_route(route, start_time);
}
// Validate
if (!is_valid_schedule(planes[plane_idx])) {
planes[plane_idx] = old_plane;
continue;
}
// Evaluate
eval.rebuild_all();
long long new_score = eval.compute_score();
long long delta = new_score - cur_score;
if (delta > 0 || (T > 0 && exp((double)delta / T) > (double)(rng() % 1000000) / 1000000.0)) {
cur_score = new_score;
accept_count++;
if (cur_score > best_score) {
best_score = cur_score;
best_planes = planes;
}
} else {
planes[plane_idx] = old_plane;
}
}
planes = best_planes;
fprintf(stderr, "SA v2: iter=%d, accept=%d, best_v_ci=%lld\n", iter, accept_count, best_score);
}
int main() {
auto global_start = chrono::steady_clock::now();
int n, r;
scanf("%d %d", &n, &r);
for (int i = 0; i < N; i++) {
scanf("%d %d %d", &cx[i], &cy[i], &cw[i]);
}
// Compute distance and flight time tables
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i == j) {
dist_table[i][j] = 0;
flight_time[i][j] = 0;
valid_pair[i][j] = false;
} else {
double dx = cx[i] - cx[j], dy = cy[i] - cy[j];
dist_table[i][j] = sqrt(dx*dx + dy*dy);
flight_time[i][j] = calc_flight_time(dist_table[i][j]);
valid_pair[i][j] = (dist_table[i][j] >= 250.0);
}
}
}
// Read Square flights
int m;
scanf("%d", &m);
for (int i = 0; i < m; i++) {
char s_time[6], t_time[6];
scanf("%d %5s %d %5s", &sq_a[i], s_time, &sq_b[i], t_time);
sq_a[i]--; sq_b[i]--; // 0-indexed
sq_s[i] = parse_time(s_time);
sq_t[i] = parse_time(t_time);
}
int k;
scanf("%d", &k);
// Target arrival times
for (int i = 0; i < NUM_TARGETS; i++) {
target_times[i] = 660 + i * 30; // 11:00, 11:30, ..., 21:00
}
// Compute Square Airlines Dijkstra
compute_square_dijkstra();
auto after_precomp = chrono::steady_clock::now();
double precomp_time = chrono::duration<double>(after_precomp - global_start).count();
fprintf(stderr, "Precomputation done in %.3fs\n", precomp_time);
// Build initial solution
vector<Airplane> planes = build_initial_solution_v3();
long long init_score = evaluate(planes);
fprintf(stderr, "Initial score (v_ci): %lld\n", init_score);
// Run SA with remaining time
double total_time_limit = 0.90; // leave margin for output
double sa_time = total_time_limit - precomp_time;
if (sa_time > 0.05) {
simulated_annealing_v2(planes, sa_time);
}
// Compute final score
long long final_vci = evaluate(planes);
// Count total weight for share calculation
long long total_weight = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (valid_pair[i][j]) {
total_weight += (long long)cw[i] * cw[j];
}
}
}
// total_weight counted per target time
total_weight *= NUM_TARGETS;
fprintf(stderr, "Final v_ci: %lld, total_weight: %lld\n", final_vci, total_weight);
if (total_weight > 0) {
fprintf(stderr, "Share: %.6f, Score: %lld\n",
(double)final_vci / total_weight,
(long long)((double)final_vci / total_weight * 1000000));
}
// Output
for (int p = 0; p < K; p++) {
printf("%d\n", (int)planes[p].flights.size());
for (auto& f : planes[p].flights) {
printf("%d %s %d %s\n",
f.from + 1, format_time(f.depart).c_str(),
f.to + 1, format_time(f.arrive).c_str());
}
}
auto total_elapsed = chrono::duration<double>(chrono::steady_clock::now() - global_start).count();
fprintf(stderr, "Total time: %.3fs\n", total_elapsed);
return 0;
}