結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 Shun_PI
|
| 提出日時 | 2026-02-25 22:47:32 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,576 bytes |
| 記録 | |
| コンパイル時間 | 4,460 ms |
| コンパイル使用メモリ | 364,116 KB |
| 実行使用メモリ | 7,848 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2026-02-25 22:50:46 |
| 合計ジャッジ時間 | 192,355 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge7 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | TLE * 100 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
// ========== Constants ==========
const int T_START = 360; // 06:00 in minutes from 00:00
const int T_END = 1260; // 21:00
const int T_STEP = 5;
const int NUM_TARGETS = 21; // 11:00, 11:30, ..., 21:00
const int NEG_INF = -999999;
// ========== Data Structures ==========
int N, R, M, K;
double px[50], py[50]; // 1-indexed
int pw[50]; // population
struct Flight {
int a, b; // cities (1-indexed)
int s, t; // departure, arrival (minutes)
};
vector<Flight> sq_flights;
double dist_tab[50][50];
int ftime_tab[50][50]; // minimum flight time
vector<int> vsrc[50]; // vsrc[j] = valid sources for destination j
int target_t[NUM_TARGETS];
// Square Airlines: precomputed latest departure
// sq_lat[j][k][i] = latest dep from city i to reach j by target_t[k]
int sq_lat[50][NUM_TARGETS][50];
// Circle Airlines state
int plane_start[26]; // 1-indexed
vector<int> route[26]; // city sequence per plane
mt19937 rng;
// ========== Time Utilities ==========
int parse_time(const char* s) {
int h, m;
sscanf(s, "%d:%d", &h, &m);
return h * 60 + m;
}
// ========== Precomputation ==========
void precompute() {
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++) {
double dx = px[i] - px[j], dy = py[i] - py[j];
dist_tab[i][j] = sqrt(dx * dx + dy * dy);
}
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++) {
if (i == j) { ftime_tab[i][j] = 0; continue; }
double raw = 60.0 * dist_tab[i][j] / 800.0 + 40.0;
ftime_tab[i][j] = (int)ceil(raw / 5.0) * 5;
}
for (int j = 1; j <= N; j++)
for (int i = 1; i <= N; i++)
if (i != j && dist_tab[i][j] >= 0.25 * R)
vsrc[j].push_back(i);
for (int k = 0; k < NUM_TARGETS; k++)
target_t[k] = 660 + 30 * k; // 11:00 to 21:00
}
// ========== Latest Departure Computation ==========
// sorted_flights must be sorted by arrival time DESCENDING.
// Computes lat[c] = latest departure time from city c to reach dest by deadline.
// lat[c] = NEG_INF means unreachable.
void compute_latest(const vector<Flight>& sorted_flights, int dest, int deadline, int lat[]) {
for (int c = 1; c <= N; c++) lat[c] = NEG_INF;
lat[dest] = deadline;
for (const auto& f : sorted_flights) {
if (lat[f.b] != NEG_INF && f.t <= lat[f.b]) {
if (f.s > lat[f.a]) lat[f.a] = f.s;
}
}
}
// ========== Precompute Square Airlines ==========
void precompute_sq() {
vector<Flight> sorted = sq_flights;
sort(sorted.begin(), sorted.end(), [](const Flight& a, const Flight& b) {
return a.t > b.t;
});
for (int j = 1; j <= N; j++)
for (int k = 0; k < NUM_TARGETS; k++)
compute_latest(sorted, j, target_t[k], sq_lat[j][k]);
}
// ========== Flight Generation from Routes ==========
// Generate flights for one plane (ASAP scheduling from plane_start)
vector<Flight> gen_plane_flights(int p) {
vector<Flight> res;
const auto& rt = route[p];
if ((int)rt.size() < 2) return res;
int cur = plane_start[p];
for (int i = 0; i + 1 < (int)rt.size(); i++) {
int a = rt[i], b = rt[i + 1];
int ft = ftime_tab[a][b];
int arr = cur + ft;
if (arr > T_END) break;
res.push_back({a, b, cur, arr});
cur = arr;
}
return res;
}
// Generate all Circle Airlines flights, sorted by arrival descending
vector<Flight> gen_all_ci_sorted() {
vector<Flight> all;
for (int p = 1; p <= K; p++) {
auto fl = gen_plane_flights(p);
for (auto& f : fl) all.push_back(f);
}
sort(all.begin(), all.end(), [](const Flight& a, const Flight& b) {
return a.t > b.t;
});
return all;
}
// ========== Score Computation ==========
// Returns v_ci (sum of w_i*w_j for triples where Circle beats Square)
long long eval_score(const vector<Flight>& ci_sorted) {
long long v_ci = 0;
int lat[50];
for (int j = 1; j <= N; j++) {
for (int k = 0; k < NUM_TARGETS; k++) {
compute_latest(ci_sorted, j, target_t[k], lat);
for (int i : vsrc[j]) {
// s_sq < s_ci => Circle wins
if (sq_lat[j][k][i] < lat[i])
v_ci += (long long)pw[i] * pw[j];
}
}
}
return v_ci;
}
int main() {
rng.seed(chrono::steady_clock::now().time_since_epoch().count());
// ---- Input ----
scanf("%d %d", &N, &R);
for (int i = 1; i <= N; i++)
scanf("%lf %lf %d", &px[i], &py[i], &pw[i]);
scanf("%d", &M);
sq_flights.resize(M);
for (int i = 0; i < M; i++) {
char ss[10], tt[10];
scanf("%d %s %d %s", &sq_flights[i].a, ss, &sq_flights[i].b, tt);
sq_flights[i].s = parse_time(ss);
sq_flights[i].t = parse_time(tt);
}
scanf("%d", &K);
precompute();
precompute_sq();
// ---- Initial Solution ----
// Each plane: start at random city, greedily add reachable cities
for (int p = 1; p <= K; p++) {
plane_start[p] = T_START;
route[p].clear();
int city = rng() % N + 1;
route[p].push_back(city);
int cur = T_START;
while (true) {
int last = route[p].back();
vector<int> cands;
for (int c = 1; c <= N; c++) {
if (c == last) continue;
if (cur + ftime_tab[last][c] <= T_END)
cands.push_back(c);
}
if (cands.empty()) break;
int next = cands[rng() % cands.size()];
route[p].push_back(next);
cur += ftime_tab[last][next];
}
}
// ---- Simulated Annealing ----
auto ci_sorted = gen_all_ci_sorted();
long long cur_score = eval_score(ci_sorted);
long long best_score = cur_score;
vector<int> best_route[26];
int best_start[26];
for (int p = 1; p <= K; p++) {
best_route[p] = route[p];
best_start[p] = plane_start[p];
}
auto t0 = chrono::steady_clock::now();
double time_limit = 1.8;
int iter = 0;
while (true) {
auto now = chrono::steady_clock::now();
double elapsed = chrono::duration<double>(now - t0).count();
if (elapsed >= time_limit) break;
double progress = elapsed / time_limit;
// Exponential temperature schedule
double temp = 1e13 * pow(1e-4, progress); // 1e13 -> 1e9
// Pick a random plane
int p = rng() % K + 1;
auto old_route = route[p];
int old_start = plane_start[p];
// Choose mutation type
int mut = rng() % 6;
if (mut == 0 && (int)route[p].size() >= 2) {
// Change a random city in the route
int pos = rng() % (int)route[p].size();
int new_city = rng() % N + 1;
route[p][pos] = new_city;
} else if (mut == 1) {
// Insert a random city
int pos = rng() % ((int)route[p].size() + 1);
int new_city = rng() % N + 1;
route[p].insert(route[p].begin() + pos, new_city);
} else if (mut == 2 && (int)route[p].size() >= 2) {
// Remove a random city
int pos = rng() % (int)route[p].size();
route[p].erase(route[p].begin() + pos);
} else if (mut == 3 && (int)route[p].size() >= 3) {
// Swap two random positions
int a = rng() % (int)route[p].size();
int b = rng() % (int)route[p].size();
swap(route[p][a], route[p][b]);
} else if (mut == 4) {
// Change start time
int delta = ((int)(rng() % 13) - 6) * T_STEP; // -30 to +30 min
int ns = plane_start[p] + delta;
ns = max(T_START, min(T_END, ns));
plane_start[p] = ns;
} else {
// Reinitialize this plane's route
route[p].clear();
int city = rng() % N + 1;
route[p].push_back(city);
int cur = plane_start[p];
while (true) {
int last = route[p].back();
vector<int> cands;
for (int c = 1; c <= N; c++) {
if (c == last) continue;
if (cur + ftime_tab[last][c] <= T_END)
cands.push_back(c);
}
if (cands.empty()) break;
int next = cands[rng() % cands.size()];
route[p].push_back(next);
cur += ftime_tab[last][next];
}
}
// Validate: no consecutive duplicates, cities in range
bool valid = true;
for (int c : route[p])
if (c < 1 || c > N) { valid = false; break; }
if (valid) {
for (int i = 0; i + 1 < (int)route[p].size(); i++)
if (route[p][i] == route[p][i + 1]) { valid = false; break; }
}
if (!valid || route[p].empty()) {
route[p] = old_route;
plane_start[p] = old_start;
continue;
}
// Evaluate
auto new_ci = gen_all_ci_sorted();
long long new_score = eval_score(new_ci);
long long d = new_score - cur_score;
bool accept = false;
if (d >= 0) {
accept = true;
} else if (temp > 0) {
double prob = exp((double)d / temp);
if ((double)(rng() % 1000000) / 1000000.0 < prob)
accept = true;
}
if (accept) {
cur_score = new_score;
ci_sorted = new_ci;
if (new_score > best_score) {
best_score = new_score;
for (int q = 1; q <= K; q++) {
best_route[q] = route[q];
best_start[q] = plane_start[q];
}
}
} else {
route[p] = old_route;
plane_start[p] = old_start;
}
iter++;
}
// Restore best solution
for (int p = 1; p <= K; p++) {
route[p] = best_route[p];
plane_start[p] = best_start[p];
}
fprintf(stderr, "SA: %d iters, best_score=%lld\n", iter, best_score);
// ---- Output ----
for (int p = 1; p <= K; p++) {
auto flights = gen_plane_flights(p);
printf("%d\n", (int)flights.size());
for (auto& f : flights) {
printf("%d %02d:%02d %d %02d:%02d\n",
f.a, f.s / 60, f.s % 60,
f.b, f.t / 60, f.t % 60);
}
}
return 0;
}