結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 mogura3.0
|
| 提出日時 | 2026-02-25 23:40:35 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 884 ms / 1,000 ms |
| コード長 | 22,671 bytes |
| 記録 | |
| コンパイル時間 | 4,838 ms |
| コンパイル使用メモリ | 289,088 KB |
| 実行使用メモリ | 7,848 KB |
| スコア | 43,729,406 |
| 最終ジャッジ日時 | 2026-02-25 23:42:15 |
| 合計ジャッジ時間 | 98,520 ms |
|
ジャッジサーバーID （参考情報） |
judge7 / judge6 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#include <algorithm>
#include <array>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using namespace std;
struct City {
int x, y;
long long w;
};
struct Flight {
int u, v; // 0-indexed city
int s, t; // minutes from 00:00
};
struct PlanePlan {
int group; // 0 or 1
int spoke; // 0-indexed city, must be != hubs[group]
int phaseSlot; // 0..11 => 0..55 min from 06:00
bool startHub;
};
static constexpr int DAY_START = 6 * 60; // 06:00
static constexpr int DAY_END = 21 * 60; // 21:00
static constexpr int Q = 21; // 11:00..21:00 every 30 min
static constexpr int INF_NEG = -1'000'000'000;
int parse_time_token(const string& tok) {
auto pos = tok.find(':');
if (pos == string::npos) return stoi(tok);
int hh = stoi(tok.substr(0, pos));
int mm = stoi(tok.substr(pos + 1));
return hh * 60 + mm;
}
void print_time(int minute) {
int hh = minute / 60;
int mm = minute % 60;
cout << setw(2) << setfill('0') << hh << ':'
<< setw(2) << setfill('0') << mm;
cout << setfill(' ');
}
int calc_duration_minutes(const City& c1, const City& c2) {
// Exact 5-minute ceil of 40 + 3*sqrt(d2)/40 using integer comparisons.
long long dx = (long long)c1.x - (long long)c2.x;
long long dy = (long long)c1.y - (long long)c2.y;
long long d2 = dx * dx + dy * dy;
for (int dur = 40; dur <= 300; dur += 5) {
long long lhs = 40LL * dur - 1600LL;
if (lhs * lhs >= 9LL * d2) return dur;
}
return 300;
}
struct Solver {
int N = 0, R = 0, M = 0, K = 0;
vector<City> cities;
vector<Flight> squareFlights;
vector<vector<int>> dur;
vector<vector<unsigned char>> eligible;
vector<vector<unsigned long long>> pairW;
array<int, Q> targetTimes{};
vector<int> sqLatest; // [q][dst][src]
vector<int> hubOrder;
vector<vector<int>> spokeOrder;
chrono::steady_clock::time_point t0;
double internalTimeLimitSec = 0.88;
int idx3(int q, int dst, int src) const {
return (q * N + dst) * N + src;
}
bool time_over() const {
double elapsed = chrono::duration<double>(chrono::steady_clock::now() - t0).count();
return elapsed >= internalTimeLimitSec;
}
void read_input() {
cin >> N >> R;
cities.resize(N);
for (int i = 0; i < N; ++i) {
cin >> cities[i].x >> cities[i].y >> cities[i].w;
}
cin >> M;
squareFlights.reserve(M);
for (int i = 0; i < M; ++i) {
int a, b;
string sTok, tTok;
cin >> a >> sTok >> b >> tTok;
squareFlights.push_back(Flight{a - 1, b - 1, parse_time_token(sTok), parse_time_token(tTok)});
}
cin >> K;
for (int q = 0; q < Q; ++q) targetTimes[q] = 11 * 60 + 30 * q;
}
void precompute_geometry() {
dur.assign(N, vector<int>(N, 0));
eligible.assign(N, vector<unsigned char>(N, 0));
pairW.assign(N, vector<unsigned long long>(N, 0));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (i != j) dur[i][j] = calc_duration_minutes(cities[i], cities[j]);
long long dx = (long long)cities[i].x - (long long)cities[j].x;
long long dy = (long long)cities[i].y - (long long)cities[j].y;
long long d2 = dx * dx + dy * dy;
if (16LL * d2 >= 1LL * R * R) {
eligible[i][j] = 1;
pairW[i][j] = (unsigned long long)cities[i].w * (unsigned long long)cities[j].w;
}
}
}
}
void precompute_orders() {
spokeOrder.assign(N, {});
vector<pair<long double, int>> hubs;
hubs.reserve(N);
for (int h = 0; h < N; ++h) {
long double acc = 0.0L;
vector<pair<long double, int>> cand;
cand.reserve(max(0, N - 1));
for (int v = 0; v < N; ++v) {
if (v == h) continue;
long double sc = (long double)cities[v].w / (long double)dur[h][v];
cand.push_back({sc, v});
acc += sc;
}
sort(cand.begin(), cand.end(), [&](const auto& a, const auto& b) {
if (a.first != b.first) return a.first > b.first;
return a.second < b.second;
});
spokeOrder[h].reserve(cand.size());
for (auto& p : cand) spokeOrder[h].push_back(p.second);
long double hubScore = acc * (long double)cities[h].w;
hubs.push_back({hubScore, h});
}
sort(hubs.begin(), hubs.end(), [&](const auto& a, const auto& b) {
if (a.first != b.first) return a.first > b.first;
return a.second < b.second;
});
hubOrder.clear();
hubOrder.reserve(N);
for (auto& p : hubs) hubOrder.push_back(p.second);
}
void precompute_square_latest() {
vector<Flight> fs = squareFlights;
sort(fs.begin(), fs.end(), [&](const Flight& a, const Flight& b) {
if (a.s != b.s) return a.s > b.s;
if (a.t != b.t) return a.t > b.t;
if (a.u != b.u) return a.u < b.u;
return a.v < b.v;
});
sqLatest.assign(Q * N * N, INF_NEG);
vector<int> best(N);
for (int q = 0; q < Q; ++q) {
int T = targetTimes[q];
for (int dst = 0; dst < N; ++dst) {
fill(best.begin(), best.end(), INF_NEG);
best[dst] = T;
for (const auto& f : fs) {
if (best[f.v] >= f.t && best[f.u] < f.s) best[f.u] = f.s;
}
for (int src = 0; src < N; ++src) sqLatest[idx3(q, dst, src)] = best[src];
}
}
}
vector<Flight> build_circle_flights(const array<int, 2>& hubs, const vector<PlanePlan>& plans) const {
vector<Flight> flights;
flights.reserve(K * 16);
for (int p = 0; p < K; ++p) {
const auto& pl = plans[p];
int hub = hubs[pl.group];
int spoke = pl.spoke;
if (spoke == hub) continue;
int cur = pl.startHub ? hub : spoke;
int tm = DAY_START + 5 * pl.phaseSlot;
while (true) {
int nxt = (cur == hub ? spoke : hub);
int arr = tm + dur[cur][nxt];
if (arr > DAY_END) break;
flights.push_back(Flight{cur, nxt, tm, arr});
cur = nxt;
tm = arr;
}
}
sort(flights.begin(), flights.end(), [&](const Flight& a, const Flight& b) {
if (a.s != b.s) return a.s > b.s;
if (a.t != b.t) return a.t > b.t;
if (a.u != b.u) return a.u < b.u;
return a.v < b.v;
});
return flights;
}
unsigned __int128 evaluate_vci(const array<int, 2>& hubs, const vector<PlanePlan>& plans) const {
vector<Flight> flights = build_circle_flights(hubs, plans);
vector<int> best(N);
unsigned __int128 vci = 0;
for (int q = 0; q < Q; ++q) {
int T = targetTimes[q];
for (int dst = 0; dst < N; ++dst) {
fill(best.begin(), best.end(), INF_NEG);
best[dst] = T;
for (const auto& f : flights) {
if (best[f.v] >= f.t && best[f.u] < f.s) best[f.u] = f.s;
}
int base = (q * N + dst) * N;
for (int src = 0; src < N; ++src) {
if (!eligible[src][dst]) continue;
if (sqLatest[base + src] < best[src]) {
vci += (unsigned __int128)pairW[src][dst];
}
}
}
}
return vci;
}
int first_valid_spoke_for_hub(int hub) const {
for (int v : spokeOrder[hub]) {
if (v != hub) return v;
}
return (hub + 1) % N;
}
vector<PlanePlan> initial_plans_for_hubs(const array<int, 2>& hubs) const {
vector<PlanePlan> plans(K);
array<int, 2> usedCnt{0, 0};
array<int, 2> pickIdx{0, 0};
for (int p = 0; p < K; ++p) {
int g = (p % 2); // balanced 13/12 split
int hub = hubs[g];
int otherHub = hubs[1 - g];
int spoke;
if (usedCnt[g] == 0) {
// Seed an inter-hub shuttle for each group.
spoke = otherHub;
} else {
const auto& ord = spokeOrder[hub];
while (pickIdx[g] < (int)ord.size() && ord[pickIdx[g]] == hub) ++pickIdx[g];
if (pickIdx[g] < (int)ord.size()) {
spoke = ord[pickIdx[g]++];
} else {
spoke = first_valid_spoke_for_hub(hub);
}
}
if (spoke == hub) spoke = first_valid_spoke_for_hub(hub);
plans[p] = PlanePlan{g, spoke, p % 12, (p % 2 == 0)};
++usedCnt[g];
}
return plans;
}
vector<PlanePlan> initial_plans_for_one_hub(int hub) const {
vector<PlanePlan> plans(K);
const auto& ord = spokeOrder[hub];
int m = max(1, (int)ord.size());
for (int p = 0; p < K; ++p) {
int spoke = ord.empty() ? ((hub + 1) % N) : ord[p % m];
if (spoke == hub) spoke = first_valid_spoke_for_hub(hub);
plans[p] = PlanePlan{0, spoke, p % 12, (p % 2 == 0)};
}
return plans;
}
struct SearchResult {
array<int, 2> hubs{0, 1};
vector<PlanePlan> plans;
unsigned __int128 vci = 0;
};
SearchResult optimize_one_hub(int hub) {
static constexpr int MAX_PASSES = 1;
static constexpr int SPOKE_CAND_LIMIT = 12;
SearchResult res;
res.hubs = {hub, hub};
res.plans = initial_plans_for_one_hub(hub);
res.vci = evaluate_vci(res.hubs, res.plans);
bool any = true;
for (int pass = 0; pass < MAX_PASSES && any && !time_over(); ++pass) {
any = false;
for (int p = 0; p < K; ++p) {
if (time_over()) break;
// 1) spoke
{
int curSpoke = res.plans[p].spoke;
int bestSpoke = curSpoke;
unsigned __int128 bestVal = res.vci;
int tried = 0;
for (int cand : spokeOrder[hub]) {
if (cand == hub || cand == curSpoke) continue;
res.plans[p].spoke = cand;
unsigned __int128 val = evaluate_vci(res.hubs, res.plans);
if (val > bestVal) {
bestVal = val;
bestSpoke = cand;
}
++tried;
if (tried >= SPOKE_CAND_LIMIT) break;
if ((tried & 3) == 0 && time_over()) break;
}
res.plans[p].spoke = bestSpoke;
if (bestVal > res.vci) {
res.vci = bestVal;
any = true;
}
}
if (time_over()) break;
// 2) phase
{
int curPhase = res.plans[p].phaseSlot;
int bestPhase = curPhase;
unsigned __int128 bestVal = res.vci;
for (int ph = 0; ph < 12; ++ph) {
if (ph == curPhase) continue;
res.plans[p].phaseSlot = ph;
unsigned __int128 val = evaluate_vci(res.hubs, res.plans);
if (val > bestVal) {
bestVal = val;
bestPhase = ph;
}
if ((ph & 3) == 3 && time_over()) break;
}
res.plans[p].phaseSlot = bestPhase;
if (bestVal > res.vci) {
res.vci = bestVal;
any = true;
}
}
if (time_over()) break;
// 3) start direction
{
bool curDir = res.plans[p].startHub;
res.plans[p].startHub = !curDir;
unsigned __int128 val = evaluate_vci(res.hubs, res.plans);
if (val > res.vci) {
res.vci = val;
any = true;
} else {
res.plans[p].startHub = curDir;
}
}
}
}
return res;
}
SearchResult optimize_hub_pair(const array<int, 2>& hubs) {
static constexpr int MAX_PASSES = 1;
static constexpr int SPOKE_CAND_LIMIT = 10;
static constexpr int MIN_GROUP_SIZE = 1;
SearchResult res;
res.hubs = hubs;
res.plans = initial_plans_for_hubs(hubs);
res.vci = evaluate_vci(hubs, res.plans);
array<int, 2> groupCnt{0, 0};
for (const auto& pl : res.plans) ++groupCnt[pl.group];
bool any = true;
for (int pass = 0; pass < MAX_PASSES && any && !time_over(); ++pass) {
any = false;
for (int p = 0; p < K; ++p) {
if (time_over()) break;
// 1) Group toggle (single try)
{
int curG = res.plans[p].group;
int nxtG = 1 - curG;
if (groupCnt[curG] > MIN_GROUP_SIZE) {
PlanePlan backup = res.plans[p];
int nxtHub = hubs[nxtG];
res.plans[p].group = nxtG;
if (res.plans[p].spoke == nxtHub) {
res.plans[p].spoke = first_valid_spoke_for_hub(nxtHub);
}
unsigned __int128 val = evaluate_vci(hubs, res.plans);
if (val > res.vci) {
--groupCnt[curG];
++groupCnt[nxtG];
res.vci = val;
any = true;
} else {
res.plans[p] = backup;
}
}
}
if (time_over()) break;
// 2) Spoke coordinate for current group
{
int g = res.plans[p].group;
int hub = hubs[g];
int curSpoke = res.plans[p].spoke;
int bestSpoke = curSpoke;
unsigned __int128 bestVal = res.vci;
int tried = 0;
bool testedOtherHub = false;
int otherHub = hubs[1 - g];
for (int cand : spokeOrder[hub]) {
if (cand == hub || cand == curSpoke) continue;
if (cand == otherHub) testedOtherHub = true;
res.plans[p].spoke = cand;
unsigned __int128 val = evaluate_vci(hubs, res.plans);
if (val > bestVal) {
bestVal = val;
bestSpoke = cand;
}
++tried;
if (tried >= SPOKE_CAND_LIMIT) break;
if ((tried & 3) == 0 && time_over()) break;
}
// Explicitly test the other hub as spoke (bridge shuttle) even if rank is low.
if (!time_over() && otherHub != hub && otherHub != curSpoke && !testedOtherHub) {
res.plans[p].spoke = otherHub;
unsigned __int128 val = evaluate_vci(hubs, res.plans);
if (val > bestVal) {
bestVal = val;
bestSpoke = otherHub;
}
}
res.plans[p].spoke = bestSpoke;
if (bestVal > res.vci) {
res.vci = bestVal;
any = true;
}
}
if (time_over()) break;
// 3) Phase coordinate
{
int curPhase = res.plans[p].phaseSlot;
int bestPhase = curPhase;
unsigned __int128 bestVal = res.vci;
for (int ph = 0; ph < 12; ++ph) {
if (ph == curPhase) continue;
res.plans[p].phaseSlot = ph;
unsigned __int128 val = evaluate_vci(hubs, res.plans);
if (val > bestVal) {
bestVal = val;
bestPhase = ph;
}
if ((ph & 3) == 3 && time_over()) break;
}
res.plans[p].phaseSlot = bestPhase;
if (bestVal > res.vci) {
res.vci = bestVal;
any = true;
}
}
if (time_over()) break;
// 4) Start direction toggle
{
bool curDir = res.plans[p].startHub;
res.plans[p].startHub = !curDir;
unsigned __int128 val = evaluate_vci(hubs, res.plans);
if (val > res.vci) {
res.vci = val;
any = true;
} else {
res.plans[p].startHub = curDir;
}
}
}
}
return res;
}
SearchResult solve() {
t0 = chrono::steady_clock::now();
read_input();
precompute_geometry();
precompute_orders();
precompute_square_latest();
SearchResult bestAll;
bool initialized = false;
// 1-hub branch
{
struct OneSeed {
int hub;
unsigned __int128 vci;
};
vector<OneSeed> oneSeeds;
int oneHubCand = min(N, 5);
for (int i = 0; i < oneHubCand; ++i) {
if (time_over()) break;
int hub = hubOrder[i];
auto initPlans = initial_plans_for_one_hub(hub);
unsigned __int128 v = evaluate_vci({hub, hub}, initPlans);
oneSeeds.push_back(OneSeed{hub, v});
}
if (!oneSeeds.empty()) {
sort(oneSeeds.begin(), oneSeeds.end(), [&](const OneSeed& a, const OneSeed& b) {
return a.vci > b.vci;
});
int oneTrials = min<int>(oneSeeds.size(), 2);
for (int i = 0; i < oneTrials; ++i) {
if (time_over()) break;
SearchResult cand = optimize_one_hub(oneSeeds[i].hub);
if (!initialized || cand.vci > bestAll.vci) {
bestAll = std::move(cand);
initialized = true;
}
}
}
}
if (time_over()) {
if (!initialized) {
int hub = hubOrder.empty() ? 0 : hubOrder[0];
return optimize_one_hub(hub);
}
return bestAll;
}
// 2-hub branch
vector<array<int, 2>> pairs;
int hubCand = min(N, 6);
for (int i = 0; i < hubCand; ++i) {
for (int j = i + 1; j < hubCand; ++j) {
pairs.push_back({hubOrder[i], hubOrder[j]});
}
}
if (pairs.empty()) {
if (N >= 2) pairs.push_back({0, 1});
else pairs.push_back({0, 0});
}
struct SeedCand {
array<int, 2> hubs;
unsigned __int128 vci;
};
vector<SeedCand> seeds;
seeds.reserve(pairs.size());
for (const auto& hubs : pairs) {
if (time_over()) break;
auto initPlans = initial_plans_for_hubs(hubs);
unsigned __int128 v = evaluate_vci(hubs, initPlans);
seeds.push_back(SeedCand{hubs, v});
}
if (seeds.empty()) {
auto hubs = pairs.front();
auto initPlans = initial_plans_for_hubs(hubs);
seeds.push_back(SeedCand{hubs, evaluate_vci(hubs, initPlans)});
}
sort(seeds.begin(), seeds.end(), [&](const SeedCand& a, const SeedCand& b) {
return a.vci > b.vci;
});
int pairTrials = min<int>(seeds.size(), 4);
for (int i = 0; i < pairTrials; ++i) {
if (time_over()) break;
SearchResult cand = optimize_hub_pair(seeds[i].hubs);
if (!initialized || cand.vci > bestAll.vci) {
bestAll = std::move(cand);
initialized = true;
}
}
if (!initialized) {
bestAll = optimize_hub_pair(seeds[0].hubs);
}
return bestAll;
}
void output_answer(const SearchResult& ans) const {
vector<vector<Flight>> perPlane(K);
for (int p = 0; p < K; ++p) {
const auto& pl = ans.plans[p];
int hub = ans.hubs[pl.group];
int spoke = pl.spoke;
if (spoke == hub) continue;
int cur = pl.startHub ? hub : spoke;
int tm = DAY_START + 5 * pl.phaseSlot;
while (true) {
int nxt = (cur == hub ? spoke : hub);
int arr = tm + dur[cur][nxt];
if (arr > DAY_END) break;
perPlane[p].push_back(Flight{cur, nxt, tm, arr});
cur = nxt;
tm = arr;
}
}
for (int p = 0; p < K; ++p) {
cout << perPlane[p].size() << '\n';
for (const auto& f : perPlane[p]) {
cout << (f.u + 1) << ' ';
print_time(f.s);
cout << ' ' << (f.v + 1) << ' ';
print_time(f.t);
cout << '\n';
}
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
Solver solver;
auto ans = solver.solve();
solver.output_answer(ans);
return 0;
}