結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 mtmr_s1
|
| 提出日時 | 2026-02-25 22:06:24 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 12,081 bytes |
| 記録 | |
| コンパイル時間 | 3,701 ms |
| コンパイル使用メモリ | 255,912 KB |
| 実行使用メモリ | 7,848 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2026-02-25 22:10:18 |
| 合計ジャッジ時間 | 196,040 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | TLE * 100 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
/*
Simulated Annealing Solver (C++20) - "Important cities / latest-departure wins"
- We maximize v_ci (weighted wins), since denominator is constant.
- Compare, for each (src i, dest j, deadline T):
s_sq(i->j,T) < s_ci(i->j,T) => Circle wins, add w_i*w_j to v_ci.
where s_* is the latest departure time (5-min ticks) that can still arrive by T.
- We compute latest departure via backward reachability DP on time-expanded DAG-ish flights:
L[dest]=T, others=-INF
if there is flight u(s->t)->v and t<=L[v], then L[u]=max(L[u], s)
Representation (Circle):
- Each plane is a simple shuttle between two cities u<->v
- Start offset in [0..11] meaning 06:00 + 5*offset
- Plane runs greedily back and forth until 21:00.
SA moves:
- Toggle plane enabled
- Change plane pair among top-P important cities
- Change plane start offset
- Swap two planes
NOTE: This is a "working baseline SA". It is not fast-optimal.
*/
static constexpr int START_MIN = 6 * 60;
static constexpr int END_MIN = 21 * 60;
static constexpr int STEP_MIN = 5;
// 06:00..21:00 inclusive => indices 0..180 (181 values)
static constexpr int TICK_MAX = (END_MIN - START_MIN) / STEP_MIN; // 180
static constexpr int NEG_INF = -1;
struct City {
int x, y;
long long w;
};
struct Flight {
int a, b; // 0-based city
int s, t; // 0..180
};
struct IncomingEdge {
int a; // from
int s; // depart
int t; // arrive
};
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();
}
static double dist_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);
}
// duration: ceil_to_5(60*d/800 + 40) minutes => ticks
static int dur_ticks(const City& A, const City& B) {
double d = dist_euclid(A,B);
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;
}
// ------------------------------------------------------------
// Latest departure DP (single dest & deadline) with incremental processing
// incoming_sorted_by_t[v] must be sorted by t ascending.
// We maintain a pointer ptr[v] meaning "processed all incoming with t <= current L[v] up to ptr[v]".
// When L[v] increases, newly eligible flights are processed once.
// ------------------------------------------------------------
static vector<int> compute_latest_departure_single_dest_deadline(
int N,
const vector<vector<IncomingEdge>>& incoming_sorted_by_t,
int dest,
int deadline_T
) {
vector<int> L(N, NEG_INF);
vector<int> ptr(N, 0);
deque<int> q;
L[dest] = deadline_T;
q.push_back(dest);
while(!q.empty()) {
int v = q.front(); q.pop_front();
int Lv = L[v];
if (Lv == NEG_INF) continue;
const auto& inc = incoming_sorted_by_t[v];
int &p = ptr[v];
while (p < (int)inc.size() && inc[p].t <= Lv) {
const auto &e = inc[p];
p++;
if (e.s > L[e.a]) {
L[e.a] = e.s;
q.push_back(e.a);
}
}
}
return L;
}
static vector<vector<vector<int>>> precompute_latest_all(
int N,
const vector<Flight>& flights,
const vector<int>& deadlines
) {
// incoming[v] = list of flights that arrive at v
vector<vector<IncomingEdge>> incoming(N);
for (const auto& f : flights) {
incoming[f.b].push_back(IncomingEdge{f.a, f.s, f.t});
}
for (int v = 0; v < N; v++) {
auto &inc = incoming[v];
sort(inc.begin(), inc.end(), [](const IncomingEdge& p, const IncomingEdge& q){
if (p.t != q.t) return p.t < q.t;
return p.s < q.s;
});
}
vector<vector<vector<int>>> latest(N, vector<vector<int>>(deadlines.size(), vector<int>(N, NEG_INF)));
for (int dest = 0; dest < N; dest++) {
for (int dk = 0; dk < (int)deadlines.size(); dk++) {
int T = deadlines[dk];
auto L = compute_latest_departure_single_dest_deadline(N, incoming, dest, T);
latest[dest][dk] = std::move(L);
}
}
return latest;
}
// ------------------------------------------------------------
// Circle schedule model: each plane is a shuttle u<->v with a start offset.
// ------------------------------------------------------------
struct Plane {
int u = -1;
int v = -1;
int start = 0; // 0..11 => 06:00 + 5*start
bool enabled = false;
};
static vector<Flight> build_circle_flights_from_planes(
const vector<City>& cities,
const vector<Plane>& planes
) {
vector<Flight> out;
out.reserve(800);
for (const auto& pl : planes) {
if (!pl.enabled) continue;
int u = pl.u, v = pl.v;
if (u < 0 || v < 0 || u == v) continue;
int cur_city = u;
int other = v;
int cur_t = pl.start;
while (true) {
int d = dur_ticks(cities[cur_city], cities[other]);
int arr = cur_t + d;
if (arr > TICK_MAX) break;
out.push_back(Flight{cur_city, other, cur_t, arr});
cur_t = arr;
swap(cur_city, other);
}
}
return out;
}
// ------------------------------------------------------------
// Scoring (objective): v_ci maximize
// ------------------------------------------------------------
struct PairSample {
int i, j; // src, dest
long long wprod; // w_i * w_j
};
static long long evaluate_v_ci(
const vector<vector<vector<int>>>& sq_latest,
const vector<vector<vector<int>>>& ci_latest,
const vector<PairSample>& samples,
int num_deadlines
) {
long long vci = 0;
for (const auto& ps : samples) {
int i = ps.i, j = ps.j;
long long wprod = ps.wprod;
for (int dk = 0; dk < num_deadlines; dk++) {
int ssq = sq_latest[j][dk][i];
int sci = ci_latest[j][dk][i];
if (ssq < sci) vci += wprod;
}
}
return vci;
}
// RNG
struct XorShift {
uint64_t x=88172645463325252ULL;
uint64_t next_u64() {
x ^= x<<7;
x ^= x>>9;
return x;
}
int next_int(int lo, int hi) { // inclusive
return lo + (int)(next_u64() % (uint64_t)(hi - lo + 1));
}
double next_double() {
return (next_u64() >> 11) * (1.0/9007199254740992.0); // [0,1)
}
};
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> square(M);
for (int k = 0; k < M; k++) {
int a, b;
string s_str, t_str;
cin >> a >> s_str >> b >> t_str;
--a; --b;
square[k] = Flight{a, b, time_to_idx(s_str), 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; // 60
for (int k = 0; k < 21; k++) deadlines.push_back(idx_1100 + 6*k);
}
// Precompute square latest table once
auto sq_latest = precompute_latest_all(N, square, deadlines);
// Important city set: top-P by population
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;
P = min(P, N);
vector<int> top(order.begin(), order.begin()+P);
// Samples: all directed pairs (i,j) with dist>=0.25R, i!=j
vector<PairSample> samples;
samples.reserve(N*N);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) if (i != j) {
if (dist_euclid(cities[i], cities[j]) >= 0.25 * (double)R) {
long long wprod = cities[i].w * cities[j].w;
samples.push_back(PairSample{i, j, wprod});
}
}
}
// Initial state: fill planes with distinct pairs among top cities
vector<Plane> cur(K), best_state(K);
{
for (int pi = 0; pi < K; pi++) {
cur[pi].enabled = false;
cur[pi].u = top[0];
cur[pi].v = top[min(1, P-1)];
cur[pi].start = 0;
}
int idx = 0;
for (int ii = 0; ii < P && idx < K; ii++) {
for (int jj = ii+1; jj < P && idx < K; jj++) {
int u = top[ii], v = top[jj];
if (dist_euclid(cities[u], cities[v]) < 0.25 * (double)R) continue;
cur[idx].enabled = true;
cur[idx].u = u;
cur[idx].v = v;
cur[idx].start = (idx % 12);
idx++;
}
}
}
// Evaluate initial
{
auto cur_flights = build_circle_flights_from_planes(cities, cur);
auto cur_latest = precompute_latest_all(N, cur_flights, deadlines);
long long cur_vci = evaluate_v_ci(sq_latest, cur_latest, samples, (int)deadlines.size());
long long best_vci = cur_vci;
best_state = cur;
XorShift rng;
auto start_clock = chrono::high_resolution_clock::now();
// SA params
const double TIME_LIMIT_SEC = 1.85;
const double T0 = 2.0e12; // scale large
const double T1 = 1.0e9;
auto elapsed_sec = [&](){
auto now = chrono::high_resolution_clock::now();
return chrono::duration<double>(now - start_clock).count();
};
auto temperature = [&](double t){
double x = min(1.0, t / TIME_LIMIT_SEC);
double logT = log(T0) * (1.0 - x) + log(T1) * x;
return exp(logT);
};
auto apply_random_move = [&](vector<Plane>& st){
int p = rng.next_int(0, K-1);
int typ = rng.next_int(0, 99);
if (typ < 20) {
// toggle enabled
st[p].enabled = !st[p].enabled;
if (st[p].enabled && (st[p].u < 0 || st[p].v < 0 || st[p].u == st[p].v)) {
st[p].u = top[0];
st[p].v = top[min(1, P-1)];
st[p].start = rng.next_int(0, 11);
}
} else if (typ < 55) {
// change pair among top cities
int u = top[rng.next_int(0, P-1)];
int v = top[rng.next_int(0, P-1)];
while (v == u) v = top[rng.next_int(0, P-1)];
st[p].u = u;
st[p].v = v;
st[p].enabled = true;
} else if (typ < 80) {
// change start offset
st[p].start = rng.next_int(0, 11);
st[p].enabled = true;
} else {
// swap two planes
int q = rng.next_int(0, K-1);
swap(st[p], st[q]);
}
};
while (true) {
double t = elapsed_sec();
if (t >= TIME_LIMIT_SEC) break;
double Temp = temperature(t);
vector<Plane> nxt = cur;
apply_random_move(nxt);
auto nxt_flights = build_circle_flights_from_planes(cities, nxt);
auto nxt_latest = precompute_latest_all(N, nxt_flights, deadlines);
long long nxt_vci = evaluate_v_ci(sq_latest, nxt_latest, samples, (int)deadlines.size());
long long delta = nxt_vci - cur_vci;
bool accept = false;
if (delta >= 0) {
accept = true;
} else {
double prob = exp((double)delta / Temp);
if (rng.next_double() < prob) accept = true;
}
if (accept) {
cur = std::move(nxt);
cur_vci = nxt_vci;
if (cur_vci > best_vci) {
best_vci = cur_vci;
best_state = cur;
}
}
}
}
// Output best schedule
for (int pi = 0; pi < K; pi++) {
const auto& pl = best_state[pi];
if (!pl.enabled || pl.u < 0 || pl.v < 0 || pl.u == pl.v) {
cout << 0 << "\n";
continue;
}
vector<Flight> legs;
int cur_city = pl.u;
int other = pl.v;
int cur_t = pl.start;
while (true) {
int d = dur_ticks(cities[cur_city], cities[other]);
int arr = cur_t + d;
if (arr > TICK_MAX) break;
legs.push_back(Flight{cur_city, other, cur_t, arr});
cur_t = arr;
swap(cur_city, other);
}
cout << legs.size() << "\n";
for (const auto& f : legs) {
cout << (f.a + 1) << " " << idx_to_time(f.s) << " "
<< (f.b + 1) << " " << idx_to_time(f.t) << "\n";
}
}
return 0;
}