結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 てんぷら
|
| 提出日時 | 2026-02-25 22:17:17 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 18,130 bytes |
| 記録 | |
| コンパイル時間 | 5,904 ms |
| コンパイル使用メモリ | 302,960 KB |
| 実行使用メモリ | 7,976 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2026-02-25 22:20:10 |
| 合計ジャッジ時間 | 168,282 ms |
|
ジャッジサーバーID （参考情報） |
judge6 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | TLE * 100 |
ソースコード
#include <algorithm>
#include <array>
#include <cmath>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <string>
#include <tuple>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;
struct City {
int x, y;
ll w;
};
struct Flight {
int a, b;
int s, t;
};
struct PlanePlan {
vector<int> route;
int offset = 0;
int duration = 0;
};
struct DemandTerm {
int src, dst;
long double w;
array<int, 21> sq;
};
constexpr int START_HOUR = 6;
constexpr int END_HOUR = 21;
constexpr int SLOT_MIN = 5;
constexpr int MAX_SLOT = (END_HOUR - START_HOUR) * 60 / SLOT_MIN; // 180
constexpr int TARGET_CNT = 21;
constexpr int TARGET_START = (11 - START_HOUR) * 60 / SLOT_MIN; // 60
constexpr int TARGET_STEP = 30 / SLOT_MIN; // 6
constexpr int NEG_INF = -1e9;
int parseTimeToSlot(const string& s) {
auto pos = s.find(':');
int hh = stoi(s.substr(0, pos));
int mm = stoi(s.substr(pos + 1));
return (hh * 60 + mm - START_HOUR * 60) / SLOT_MIN;
}
string slotToTime(int slot) {
int total = START_HOUR * 60 + slot * SLOT_MIN;
int hh = total / 60;
int mm = total % 60;
char buf[16];
snprintf(buf, sizeof(buf), "%02d:%02d", hh, mm);
return string(buf);
}
int calcDurationSlot(const City& c1, const City& c2) {
double dx = double(c1.x) - double(c2.x);
double dy = double(c1.y) - double(c2.y);
double d = sqrt(dx * dx + dy * dy);
double minutes = 60.0 * d / 800.0 + 40.0;
return (int)ceil(minutes / 5.0 - 1e-12);
}
int routeDuration(const vector<int>& route, const vector<vector<int>>& dur) {
int total = 0;
for (int i = 1; i < (int)route.size(); ++i) {
if (route[i - 1] == route[i]) return MAX_SLOT + 1;
total += dur[route[i - 1]][route[i]];
if (total > MAX_SLOT) return total;
}
return total;
}
void normalizePlane(PlanePlan& p, const vector<vector<int>>& dur) {
if (p.route.empty()) p.route.push_back(0);
vector<int> fixed;
fixed.reserve(p.route.size());
fixed.push_back(p.route[0]);
for (int i = 1; i < (int)p.route.size(); ++i) {
if (p.route[i] != p.route[i - 1]) fixed.push_back(p.route[i]);
}
p.route.swap(fixed);
if (p.route.empty()) p.route.push_back(0);
p.duration = routeDuration(p.route, dur);
while (p.duration > MAX_SLOT && (int)p.route.size() > 1) {
p.route.pop_back();
p.duration = routeDuration(p.route, dur);
}
int lim = max(0, MAX_SLOT - p.duration);
p.offset = min(max(0, p.offset), lim);
}
void appendPlaneFlights(const PlanePlan& p, const vector<vector<int>>& dur, vector<Flight>& out) {
int tm = p.offset;
for (int i = 1; i < (int)p.route.size(); ++i) {
int a = p.route[i - 1];
int b = p.route[i];
int nt = tm + dur[a][b];
out.push_back({a, b, tm, nt});
tm = nt;
}
}
vector<Flight> flattenPlans(const vector<PlanePlan>& plans, const vector<vector<int>>& dur) {
vector<Flight> flights;
for (const auto& p : plans) appendPlaneFlights(p, dur, flights);
return flights;
}
struct ScoreEvaluator {
int N;
uint64_t allMask;
explicit ScoreEvaluator(int n) : N(n) {
allMask = (N == 64 ? ~0ULL : ((1ULL << N) - 1));
}
vector<vector<Flight>> buildByStart(const vector<Flight>& flights, int target) const {
vector<vector<Flight>> byStart(target + 1);
for (const auto& f : flights) {
if (f.s < 0 || f.s > target || f.t < 0 || f.t > target) continue;
byStart[f.s].push_back(f);
}
return byStart;
}
vector<vector<int>> latestMatrixForTarget(const vector<vector<Flight>>& byStart, int target) const {
vector<vector<uint64_t>> reach(target + 1, vector<uint64_t>(N, 0ULL));
for (int c = 0; c < N; ++c) reach[target][c] = (1ULL << c);
for (int tm = target - 1; tm >= 0; --tm) {
for (int c = 0; c < N; ++c) reach[tm][c] = reach[tm + 1][c];
for (const auto& f : byStart[tm]) {
reach[tm][f.a] |= reach[f.t][f.b];
}
}
vector<vector<int>> latest(N, vector<int>(N, NEG_INF));
for (int src = 0; src < N; ++src) {
uint64_t rem = allMask;
for (int tm = target; tm >= 0 && rem; --tm) {
uint64_t m = reach[tm][src] & rem;
while (m) {
int dst = __builtin_ctzll(m);
latest[src][dst] = tm;
rem &= ~(1ULL << dst);
m &= (m - 1);
}
}
}
return latest;
}
vector<vector<vector<int>>> precomputeSqBest(const vector<Flight>& sqFlights) const {
vector<vector<vector<int>>> sqBest(TARGET_CNT, vector<vector<int>>(N, vector<int>(N, NEG_INF)));
for (int k = 0; k < TARGET_CNT; ++k) {
int target = TARGET_START + TARGET_STEP * k;
auto byStart = buildByStart(sqFlights, target);
sqBest[k] = latestMatrixForTarget(byStart, target);
}
return sqBest;
}
double score(
const vector<Flight>& ciFlights,
const vector<DemandTerm>& demands
) const {
long double vSq = 0.0L, vCi = 0.0L;
for (int k = 0; k < TARGET_CNT; ++k) {
int target = TARGET_START + TARGET_STEP * k;
auto byStart = buildByStart(ciFlights, target);
auto latest = latestMatrixForTarget(byStart, target);
for (const auto& d : demands) {
if (d.sq[k] < latest[d.src][d.dst]) vCi += d.w;
else vSq += d.w;
}
}
long double den = vSq + vCi;
if (den <= 0.0L) return 0.0;
return (double)(vCi / den);
}
};
PlanePlan buildCyclicPlan(
const vector<int>& cycle,
int offset,
const vector<vector<int>>& dur
) {
PlanePlan p;
if (cycle.empty()) return p;
p.route.push_back(cycle[0]);
p.offset = offset;
int tm = offset;
int cur = cycle[0];
int idx = 1 % (int)cycle.size();
while (true) {
int nxt = cycle[idx];
if (nxt == cur) break;
int nt = tm + dur[cur][nxt];
if (nt > MAX_SLOT) break;
p.route.push_back(nxt);
tm = nt;
cur = nxt;
idx = (idx + 1) % (int)cycle.size();
}
p.duration = tm - offset;
normalizePlane(p, dur);
return p;
}
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> sqFlights(M);
for (int i = 0; i < M; ++i) {
int a, b;
string ss, tt;
cin >> a >> ss >> b >> tt;
--a;
--b;
sqFlights[i] = {a, b, parseTimeToSlot(ss), parseTimeToSlot(tt)};
}
int K;
cin >> K;
vector<vector<int>> dur(N, vector<int>(N, 0));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) if (i != j) dur[i][j] = calcDurationSlot(cities[i], cities[j]);
}
vector<vector<long double>> pairWeight(N, vector<long double>(N, 0.0L));
double threshold = 0.25 * R;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
double dx = double(cities[i].x) - double(cities[j].x);
double dy = double(cities[i].y) - double(cities[j].y);
double d = sqrt(dx * dx + dy * dy);
if (d + 1e-12 >= threshold) {
pairWeight[i][j] = (long double)cities[i].w * (long double)cities[j].w;
}
}
}
ScoreEvaluator evaluator(N);
auto sqBest = evaluator.precomputeSqBest(sqFlights); // [k][src][dst]
vector<DemandTerm> demands;
demands.reserve(N * N);
for (int src = 0; src < N; ++src) {
for (int dst = 0; dst < N; ++dst) {
if (pairWeight[src][dst] == 0.0L) continue;
DemandTerm d;
d.src = src;
d.dst = dst;
d.w = pairWeight[src][dst];
for (int k = 0; k < TARGET_CNT; ++k) d.sq[k] = sqBest[k][src][dst];
demands.push_back(d);
}
}
vector<long double> cityScore(N, 0.0L);
for (int i = 0; i < N; ++i) {
long double s = (long double)cities[i].w * 1e6L;
for (int j = 0; j < N; ++j) s += pairWeight[i][j] + pairWeight[j][i];
cityScore[i] = max((long double)1.0, s);
}
vector<int> cityOrd(N);
iota(cityOrd.begin(), cityOrd.end(), 0);
sort(cityOrd.begin(), cityOrd.end(), [&](int a, int b) {
return cityScore[a] > cityScore[b];
});
vector<tuple<long double, int, int>> pairOrd;
pairOrd.reserve(N * (N - 1) / 2);
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
long double v = pairWeight[i][j] + pairWeight[j][i];
pairOrd.emplace_back(v, i, j);
}
}
sort(pairOrd.begin(), pairOrd.end(), [&](const auto& a, const auto& b) {
return get<0>(a) > get<0>(b);
});
vector<PlanePlan> candidates;
vector<vector<Flight>> candidateFlights;
vector<long double> staticPotential;
vector<uint64_t> candidateCityMask;
unordered_set<string> seenPlan;
auto addCandidate = [&](const PlanePlan& p) {
if ((int)p.route.size() <= 1) return;
string key;
key.reserve(16 + p.route.size() * 4);
key += to_string(p.offset);
key.push_back('|');
for (int c : p.route) {
key += to_string(c);
key.push_back(',');
}
if (seenPlan.find(key) != seenPlan.end()) return;
vector<Flight> fl;
appendPlaneFlights(p, dur, fl);
if (fl.empty()) return;
long double pot = 0.0L;
for (const auto& f : fl) {
long double base = pairWeight[f.a][f.b];
if (base <= 0.0L) continue;
for (int k = 0; k < TARGET_CNT; ++k) {
int target = TARGET_START + TARGET_STEP * k;
if (f.t <= target && f.s > sqBest[k][f.a][f.b]) pot += base;
}
}
candidates.push_back(p);
candidateFlights.push_back(std::move(fl));
staticPotential.push_back(pot);
uint64_t mask = 0ULL;
for (int c : p.route) mask |= (1ULL << c);
candidateCityMask.push_back(mask);
seenPlan.insert(std::move(key));
};
vector<int> offsets = {0, 12, 24, 36, 48, 60};
int topPairs = min((int)pairOrd.size(), 220);
for (int id = 0; id < topPairs; ++id) {
auto [v, a, b] = pairOrd[id];
if (v <= 0.0L) break;
for (int off : offsets) {
addCandidate(buildCyclicPlan({a, b}, off, dur));
addCandidate(buildCyclicPlan({b, a}, off, dur));
}
}
int hubCnt = min(6, N);
int spokeCnt = min(14, N);
vector<int> hubs(cityOrd.begin(), cityOrd.begin() + hubCnt);
vector<int> spokes(cityOrd.begin(), cityOrd.begin() + spokeCnt);
for (int h : hubs) {
for (int a : spokes) {
if (a == h) continue;
for (int b : spokes) {
if (b == h || b == a) continue;
for (int off : vector<int>{6, 30, 54}) {
addCandidate(buildCyclicPlan({h, a, h, b}, off, dur));
}
}
}
}
// Cover all cities: for each city, add shuttle plans to several strong partners.
for (int c = 0; c < N; ++c) {
vector<pair<long double, int>> partner;
partner.reserve(N - 1);
for (int o = 0; o < N; ++o) {
if (o == c) continue;
long double v = pairWeight[c][o] + pairWeight[o][c];
v += 0.05L * (cityScore[c] + cityScore[o]);
partner.push_back({v, o});
}
sort(partner.begin(), partner.end(), [&](const auto& a, const auto& b) {
return a.first > b.first;
});
int take = min(5, (int)partner.size());
for (int i = 0; i < take; ++i) {
int p = partner[i].second;
for (int off : vector<int>{0, 18, 36, 54}) {
addCandidate(buildCyclicPlan({c, p}, off, dur));
addCandidate(buildCyclicPlan({p, c}, off, dur));
}
}
}
// Multiple rings over different city-score bands.
int ringLen = min(8, N);
if (ringLen >= 4) {
for (int st = 0; st < N; st += 6) {
vector<int> ring;
for (int i = st; i < min(N, st + ringLen); ++i) ring.push_back(cityOrd[i]);
if ((int)ring.size() < 4) continue;
for (int off : vector<int>{0, 24, 48}) {
addCandidate(buildCyclicPlan(ring, off, dur));
vector<int> rev = ring;
reverse(rev.begin(), rev.end());
addCandidate(buildCyclicPlan(rev, off, dur));
}
}
}
vector<int> candOrd((int)candidates.size());
iota(candOrd.begin(), candOrd.end(), 0);
sort(candOrd.begin(), candOrd.end(), [&](int a, int b) {
return staticPotential[a] > staticPotential[b];
});
vector<PlanePlan> plans;
plans.reserve(K);
vector<Flight> currentFlights;
vector<char> used(candidates.size(), 0);
vector<int> cityUse(N, 0);
uint64_t coveredMask = 0ULL;
int uniqueCities = 0;
int targetUnique = min(N, 16);
long double maxCityScore = 1.0L;
for (int i = 0; i < N; ++i) maxCityScore = max(maxCityScore, cityScore[i]);
long double avgPotential = 1.0L;
if (!staticPotential.empty()) {
long double sum = 0.0L;
for (long double p : staticPotential) sum += p;
avgPotential = max((long double)1.0, sum / (long double)staticPotential.size());
}
for (int step = 0; step < K; ++step) {
vector<pair<long double, int>> dyn;
vector<pair<int, int>> dynUncovered;
dyn.reserve(candidates.size());
dynUncovered.reserve(candidates.size());
for (int id : candOrd) {
if (used[id]) continue;
uint64_t m = candidateCityMask[id];
long double novelty = 0.0L;
while (m) {
int c = __builtin_ctzll(m);
novelty += (cityScore[c] / maxCityScore) / (1.0L + (long double)cityUse[c]);
m &= (m - 1);
}
uint64_t uncovered = candidateCityMask[id] & (~coveredMask);
int uncoveredCnt = __builtin_popcountll(uncovered);
long double potNorm = staticPotential[id] / avgPotential;
long double rank = potNorm + 0.60L * novelty + 0.90L * (long double)uncoveredCnt;
dyn.push_back({rank, id});
dynUncovered.push_back({uncoveredCnt, id});
}
sort(dyn.begin(), dyn.end(), [&](const auto& a, const auto& b) {
return a.first > b.first;
});
sort(dynUncovered.begin(), dynUncovered.end(), [&](const auto& a, const auto& b) {
if (a.first != b.first) return a.first > b.first;
return staticPotential[a.second] > staticPotential[b.second];
});
vector<int> shortlist;
int shortlistSize = 70;
shortlist.reserve(shortlistSize);
for (int i = 0; i < min(shortlistSize, (int)dyn.size()); ++i) shortlist.push_back(dyn[i].second);
if (uniqueCities < targetUnique) {
for (int i = 0; i < min(40, (int)dynUncovered.size()); ++i) {
int id = dynUncovered[i].second;
bool dup = false;
for (int x : shortlist) {
if (x == id) {
dup = true;
break;
}
}
if (!dup) shortlist.push_back(id);
}
}
if (shortlist.empty()) break;
int bestId = shortlist[0];
double bestScore = -1.0;
double bestObjective = -1.0;
double exploreCoef = 0.0;
if (uniqueCities < targetUnique) {
exploreCoef = 0.010 * (double)(targetUnique - uniqueCities) / (double)targetUnique;
}
for (int id : shortlist) {
vector<Flight> testFlights = currentFlights;
testFlights.insert(testFlights.end(), candidateFlights[id].begin(), candidateFlights[id].end());
double s = evaluator.score(testFlights, demands);
int uncoveredCnt = __builtin_popcountll(candidateCityMask[id] & (~coveredMask));
double objective = s + exploreCoef * (double)uncoveredCnt;
if (objective > bestObjective || (objective == bestObjective && s > bestScore)) {
bestObjective = objective;
bestScore = s;
bestId = id;
}
}
used[bestId] = 1;
plans.push_back(candidates[bestId]);
currentFlights.insert(currentFlights.end(), candidateFlights[bestId].begin(), candidateFlights[bestId].end());
uint64_t m = candidateCityMask[bestId];
while (m) {
int c = __builtin_ctzll(m);
if (cityUse[c] == 0) uniqueCities++;
cityUse[c]++;
m &= (m - 1);
}
coveredMask |= candidateCityMask[bestId];
}
while ((int)plans.size() < K) plans.push_back(PlanePlan{{0}, 0, 0});
vector<Flight> finalFlights = flattenPlans(plans, dur);
double finalScore = evaluator.score(finalFlights, demands);
for (int i = 0; i < K; ++i) {
const auto& p = plans[i];
cout << max(0, (int)p.route.size() - 1) << '\n';
int tm = p.offset;
for (int j = 1; j < (int)p.route.size(); ++j) {
int a = p.route[j - 1], b = p.route[j];
int nt = tm + dur[a][b];
cout << (a + 1) << ' ' << slotToTime(tm) << ' ' << (b + 1) << ' ' << slotToTime(nt) << '\n';
tm = nt;
}
}
cerr << fixed << setprecision(12)
<< "score=" << finalScore
<< " candidates=" << candidates.size()
<< " flights=" << finalFlights.size() << '\n';
return 0;
}