結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 Piiiii
|
| 提出日時 | 2026-03-04 20:11:30 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 27,183 bytes |
| 記録 | |
| コンパイル時間 | 7,354 ms |
| コンパイル使用メモリ | 427,760 KB |
| 実行使用メモリ | 42,996 KB |
| スコア | 25,376,511 |
| 最終ジャッジ日時 | 2026-03-04 22:11:00 |
| 合計ジャッジ時間 | 121,263 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 40 TLE * 60 |
ソースコード
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
static constexpr int MAXN = 47;
static constexpr int SLOT_MIN = 5;
static constexpr int DAY_START_MIN = 6 * 60; // 06:00
static constexpr int DAY_END_MIN = 21 * 60; // 21:00
static constexpr int TS = (DAY_END_MIN - DAY_START_MIN) / SLOT_MIN + 1; // 181
static constexpr int V = MAXN * TS;
// ===== Fixed hyperparameters =====
static constexpr int ORIGIN_USE = 47;
static constexpr int START_USE = 47;
static constexpr int NEAR_CAND = 18;
static constexpr int POP_CAND = 26;
static constexpr int K_FIXED = 25;
static constexpr int M_FIXED = 400;
static constexpr int BEAM_WIDTH_DEFAULT = 3;
static constexpr int BRANCHES_DEFAULT = 2;
static int gBeamWidth = BEAM_WIDTH_DEFAULT;
static int gBranches = BRANCHES_DEFAULT;
// Tunable parameters for tie-breaking / branch scoring.
static int gTieMove = 0;
static int gTiePopDiv = 0;
static int gTieArr = 1;
static int gBranchMode = 0; // 0: default, 1: spatial-diverse, 2: time-diverse
static int gBranchDivW = 0;
static int gScoreMode = 1; // 0: cumulative dp, 1: parent true + dp
static long long gBeamGap = 100; // keep states with score >= best - gap
static int gVerboseStep = 0;
static long long gEvalFlightW = 0;
static long long gEvalPopDivW = 1;
static long long gEvalLateArrW = 0;
// Targets: 11:00, 11:30, ..., 21:00 (21 values)
static constexpr int TGT = 21;
struct FlightOut {
int a, b;
int dep_t, arr_t; // time index
};
struct RouteCandidate {
vector<FlightOut> flights;
__int128 value;
};
static inline int timeToIdx(int minute) { return (minute - DAY_START_MIN) / SLOT_MIN; }
static inline int idxToTime(int idx) { return DAY_START_MIN + idx * SLOT_MIN; }
static inline string fmtTimeIdx(int idx) {
int m = idxToTime(idx);
int hh = m / 60, mm = m % 60;
char buf[6];
snprintf(buf, sizeof(buf), "%02d:%02d", hh, mm);
return string(buf);
}
static inline int parseTimeStr(const string& s) {
int hh = (s[0]-'0')*10 + (s[1]-'0');
int mm = (s[3]-'0')*10 + (s[4]-'0');
return hh*60 + mm;
}
static inline bool parseEnvInt(const char* name, int& out) {
const char* s = getenv(name);
if (!s) return false;
out = atoi(s);
return true;
}
// ===== globals =====
static uint32_t popW[MAXN];
static int N, R;
static int durSlot[MAXN][MAXN];
static double distMat[MAXN][MAXN];
static bool validPair[MAXN][MAXN];
// earliest[d][t][c] (time-major for cache)
static uint16_t earliestSq[MAXN][TS][MAXN];
static uint16_t earliestCi[MAXN][TS][MAXN];
static constexpr uint16_t INF16 = 65535;
// latest[o][d][deadline] (same as before)
static int16_t latestSq[MAXN][MAXN][TS];
static int16_t latestCi[MAXN][MAXN][TS];
static int16_t s_sq[MAXN][MAXN][TGT];
static int16_t s_ci[MAXN][MAXN][TGT];
// reachMask[vtx][ti] : destinations reachable by target ti from vtx
static uint64_t reachMask[V][TGT];
// flipMask[oi][s][ti] (IMPORTANT: ti contiguous now)
static uint64_t flipMask[ORIGIN_USE][TS][TGT];
static int tgtIdx[TGT];
static int firstTiTime[TS]; // first target index whose deadline >= timeIdx (or TGT)
// Precomputed feasible flight transitions from each vertex (c,t).
static uint8_t dpMoveCnt[V];
static uint16_t dpMoveV[V][MAXN];
static uint8_t dpMoveStartTi[V][MAXN];
static inline long long routeEvalBonus(const vector<FlightOut>& flights) {
long long bonus = 0;
bonus += gEvalFlightW * (long long)flights.size();
if (!flights.empty()) {
long long popDiv = 0;
int lastArr = flights.back().arr_t;
bool seen[MAXN];
memset(seen, 0, sizeof(seen));
for (const auto& f : flights) {
if (!seen[f.b]) {
seen[f.b] = true;
popDiv += popW[f.b] / 1000;
}
}
bonus += gEvalPopDivW * popDiv;
bonus += gEvalLateArrW * (long long)lastArr;
}
return bonus;
}
// ===== sumW(mask) tables =====
static uint32_t T0[1<<16];
static uint32_t T1[1<<16];
static uint32_t T2[1<<15];
static inline void buildWeightTables(const uint32_t* w) {
T0[0]=0;
for (uint32_t m=1; m<(1u<<16); m++) {
uint32_t b = __builtin_ctz(m);
T0[m] = T0[m & (m-1)] + w[b];
}
T1[0]=0;
for (uint32_t m=1; m<(1u<<16); m++) {
uint32_t b = __builtin_ctz(m);
T1[m] = T1[m & (m-1)] + w[16 + b];
}
T2[0]=0;
for (uint32_t m=1; m<(1u<<15); m++) {
uint32_t b = __builtin_ctz(m);
T2[m] = T2[m & (m-1)] + w[32 + b];
}
}
static inline uint64_t sumW_mask(uint64_t mask) {
uint32_t a = (uint32_t)(mask & 0xFFFFull);
uint32_t b = (uint32_t)((mask >> 16) & 0xFFFFull);
uint32_t c = (uint32_t)((mask >> 32) & 0x7FFFull);
return T0[a] + T1[b] + T2[c];
}
// ===== CSR adjacency (contiguous edges per u) =====
template<int MAXE>
struct CSRAdj {
int E = 0;
int u[MAXE];
uint8_t toCity[MAXE];
uint8_t arrT[MAXE];
int start[V+1]; // size V+1
uint8_t bTo[MAXE];
uint8_t bArr[MAXE];
void init() { E = 0; }
inline void addEdge(int uV, int vCity, int at) {
u[E] = uV;
toCity[E] = (uint8_t)vCity;
arrT[E] = (uint8_t)at;
++E;
}
void build() {
static int cnt[V];
static int cur[V];
memset(cnt, 0, sizeof(cnt));
for (int i=0;i<E;i++) cnt[u[i]]++;
start[0] = 0;
for (int i=0;i<V;i++) start[i+1] = start[i] + cnt[i];
memcpy(cur, start, sizeof(int)*V);
for (int i=0;i<E;i++) {
int pos = cur[u[i]]++;
bTo[pos] = toCity[i];
bArr[pos] = arrT[i];
}
}
};
static CSRAdj<M_FIXED + 8> sqAdj;
static CSRAdj<20000> ciAdj;
// ===== build earliest + latest =====
template<int MAXE>
static inline void buildEarliestTable(const CSRAdj<MAXE>& adj,
uint16_t earliest[MAXN][TS][MAXN]) {
// earliest[d][t][c] = min arrival time at d starting from (c,t)
for (int d=0; d<N; d++) {
for (int t=TS-1; t>=0; --t) {
uint16_t* row = earliest[d][t];
uint16_t* rowWait = (t+1 < TS) ? earliest[d][t+1] : nullptr;
for (int c=0; c<N; c++) {
uint16_t best = INF16;
if (c == d) best = (uint16_t)t;
if (rowWait) best = min(best, rowWait[c]); // wait
int uV = c*TS + t;
for (int ei = adj.start[uV]; ei < adj.start[uV+1]; ++ei) {
best = min(best, earliest[d][adj.bArr[ei]][adj.bTo[ei]]);
}
row[c] = best;
}
}
}
}
static inline void buildLatestTable(const uint16_t earliest[MAXN][TS][MAXN],
int16_t latest[MAXN][MAXN][TS]) {
// latest[o][d][deadline] from earliest
static int16_t bucket[TS];
for (int o=0; o<N; o++) {
for (int d=0; d<N; d++) {
for (int i=0;i<TS;i++) bucket[i] = -1;
for (int s=0; s<TS; s++) {
uint16_t arr = earliest[d][s][o];
if (arr != INF16) bucket[arr] = max(bucket[arr], (int16_t)s);
}
int16_t best = -1;
for (int dead=0; dead<TS; dead++) {
best = max(best, bucket[dead]);
latest[o][d][dead] = best;
}
}
}
}
template<int MAXE>
static inline void buildEarliestAndLatest(const CSRAdj<MAXE>& adj,
uint16_t earliest[MAXN][TS][MAXN],
int16_t latest[MAXN][MAXN][TS]) {
buildEarliestTable(adj, earliest);
buildLatestTable(earliest, latest);
}
static void buildTargetsFromLatest(const int16_t latest[MAXN][MAXN][TS],
int16_t out[MAXN][MAXN][TGT]) {
for (int o=0; o<N; o++)
for (int d=0; d<N; d++)
for (int ti=0; ti<TGT; ti++)
out[o][d][ti] = latest[o][d][tgtIdx[ti]];
}
// ===== reachMask: O(V*(N+TGT)) =====
static void buildReachMaskFromEarliestFast(const uint16_t earliest[MAXN][TS][MAXN]) {
uint64_t tmp[TGT];
for (int vtx=0; vtx<N*TS; vtx++) {
int c = vtx / TS;
int t = vtx % TS;
for (int i=0;i<TGT;i++) tmp[i]=0;
for (int d=0; d<N; d++) {
uint16_t arr = earliest[d][t][c];
if (arr == INF16) continue;
int k = firstTiTime[(int)arr];
if (k < TGT) tmp[k] |= (1ull << d);
}
uint64_t cur=0;
for (int ti=0; ti<TGT; ti++) {
cur |= tmp[ti];
reachMask[vtx][ti] = cur;
}
}
}
// build flipMask[oi][s][ti]
static void buildFlipMaskForOrigins(const int originsUsed[ORIGIN_USE], int originsCount) {
for (int oi=0; oi<originsCount; oi++) {
int o = originsUsed[oi];
for (int ti=0; ti<TGT; ti++) {
uint64_t addAt[TS];
memset(addAt, 0, sizeof(addAt));
for (int d=0; d<N; d++) {
if (!validPair[o][d]) continue;
if (s_ci[o][d][ti] > s_sq[o][d][ti]) continue;
int16_t sq = s_sq[o][d][ti];
int thr = (sq < 0 ? 0 : (int)sq + 1);
if (thr <= TS-1) addAt[thr] |= (1ull << d);
}
uint64_t cur=0;
for (int s=0; s<TS; s++) {
cur |= addAt[s];
flipMask[oi][s][ti] = cur;
}
}
}
}
// ===== active origins per vertex (cache fp pointer) =====
struct ActOrigins {
uint8_t cnt;
uint64_t wo[ORIGIN_USE];
const uint64_t* fp0[ORIGIN_USE]; // points to flipMask[oi][sidx][0]
};
static ActOrigins act[V];
static void buildActOrigins(const int16_t (*originLatest[ORIGIN_USE])[TS],
const uint64_t originW[ORIGIN_USE],
int originsCount) {
for (int u=0; u<N*TS; u++) {
int c = u/TS;
int t = u%TS;
uint8_t cnt=0;
for (int oi=0; oi<originsCount; oi++) {
int16_t s = originLatest[oi][c][t];
if (s < 0) continue;
act[u].wo[cnt] = originW[oi];
act[u].fp0[cnt] = &flipMask[oi][(int)s][0];
cnt++;
}
act[u].cnt = cnt;
}
}
// ===== edgeGain (faster due to flipMask layout) =====
static inline uint64_t edgeGainUV(int u, int vtx, int startTi) {
uint64_t gain = 0;
const ActOrigins& A = act[u];
const uint64_t* rm = reachMask[vtx];
uint64_t lastMask = ~0ull;
uint64_t lastSum = 0;
for (int k=0; k<(int)A.cnt; k++) {
uint64_t wo = A.wo[k];
const uint64_t* fp = A.fp0[k]; // fp[ti] is flipMask for this origin and sidx
for (int ti=startTi; ti<TGT; ti++) {
uint64_t m = fp[ti] & rm[ti];
if (!m) continue;
uint64_t sw;
if (m == lastMask) sw = lastSum;
else {
sw = sumW_mask(m);
lastMask = m;
lastSum = sw;
}
gain += wo * sw;
}
}
return gain;
}
static vector<FlightOut> restoreFlightsFromEnd(int endVtx, const int prevv[V]) {
vector<FlightOut> revFlights;
int cur = endVtx;
while (cur != -1) {
int p = prevv[cur];
if (p == -1) break;
int pc = p / TS, pt = p % TS;
int cc = cur / TS, ct = cur % TS;
if (pc != cc) revFlights.push_back(FlightOut{pc, cc, pt, ct});
cur = p;
}
reverse(revFlights.begin(), revFlights.end());
return revFlights;
}
// ===== top-2 DP routes for one plane (different end cities) =====
static vector<RouteCandidate> solveOnePlaneDPTopK(const vector<int>& startCities) {
static __int128 dp[V];
static int prevv[V];
static long long dpSec[V];
static int16_t dpMove[V];
static int32_t dpPopDiv[V];
const __int128 NEG = -((__int128)1 << 120);
const long long NEG_SEC = numeric_limits<long long>::min() / 4;
for (int i = 0; i < V; i++) {
dp[i] = NEG;
prevv[i] = -1;
dpSec[i] = NEG_SEC;
dpMove[i] = -1;
dpPopDiv[i] = -1;
}
for (int c : startCities) {
dp[c * TS] = 0;
dpSec[c * TS] = 0;
dpMove[c * TS] = 0;
dpPopDiv[c * TS] = 0;
}
auto betterState = [&](int v, __int128 nv, long long ns, int16_t nm, int32_t np, int p) {
if (nv != dp[v]) return nv > dp[v];
if (ns != dpSec[v]) return ns > dpSec[v];
if (nm != dpMove[v]) return nm > dpMove[v];
if (np != dpPopDiv[v]) return np > dpPopDiv[v];
return (prevv[v] < 0 || p < prevv[v]);
};
for (int t = 0; t < TS; t++) {
for (int c = 0; c < N; c++) {
int u = c * TS + t;
__int128 cur = dp[u];
if (cur == NEG) continue;
// wait
if (t + 1 < TS) {
int v = u + 1;
if (betterState(v, cur, dpSec[u], dpMove[u], dpPopDiv[u], u)) {
dp[v] = cur;
dpSec[v] = dpSec[u];
dpMove[v] = dpMove[u];
dpPopDiv[v] = dpPopDiv[u];
prevv[v] = u;
}
}
// moves
int mcnt = (int)dpMoveCnt[u];
const uint16_t* mv = dpMoveV[u];
const uint8_t* ms = dpMoveStartTi[u];
for (int mi = 0; mi < mcnt; mi++) {
int v = (int)mv[mi];
int st = (int)ms[mi];
uint64_t g = edgeGainUV(u, v, st);
__int128 nv = cur + (__int128)g;
int toCity = v / TS;
int at = v % TS;
int popDiv = (int)(popW[toCity] / 1000);
long long stepSec = (long long)gTieMove
+ 1LL * gTiePopDiv * popDiv
+ 1LL * gTieArr * at;
long long ns = dpSec[u] + stepSec;
int16_t nm = (int16_t)(dpMove[u] + 1);
int32_t np = dpPopDiv[u] + popDiv;
if (betterState(v, nv, ns, nm, np, u)) {
dp[v] = nv;
dpSec[v] = ns;
dpMove[v] = nm;
dpPopDiv[v] = np;
prevv[v] = u;
}
}
}
}
vector<RouteCandidate> out;
out.reserve(gBranches);
static __int128 cityBestVal[MAXN];
static int cityBestVtx[MAXN];
static long long cityBestSec[MAXN];
static int16_t cityBestMove[MAXN];
static int32_t cityBestPopDiv[MAXN];
for (int city = 0; city < N; city++) {
cityBestVal[city] = NEG;
cityBestVtx[city] = -1;
cityBestSec[city] = NEG_SEC;
cityBestMove[city] = -1;
cityBestPopDiv[city] = -1;
}
for (int v = 0; v < V; v++) {
if (dp[v] == NEG) continue;
int city = v / TS;
if (dp[v] > cityBestVal[city] ||
(dp[v] == cityBestVal[city] && (
dpSec[v] > cityBestSec[city] ||
(dpSec[v] == cityBestSec[city] && (
dpMove[v] > cityBestMove[city] ||
(dpMove[v] == cityBestMove[city] && (
dpPopDiv[v] > cityBestPopDiv[city] ||
(dpPopDiv[v] == cityBestPopDiv[city] &&
(cityBestVtx[city] < 0 || v < cityBestVtx[city]))
))
))
))) {
cityBestVal[city] = dp[v];
cityBestVtx[city] = v;
cityBestSec[city] = dpSec[v];
cityBestMove[city] = dpMove[v];
cityBestPopDiv[city] = dpPopDiv[v];
}
}
bool usedEndCity[MAXN];
memset(usedEndCity, 0, sizeof(usedEndCity));
int selectedCities[MAXN];
int selectedArr[MAXN];
int selectedCnt = 0;
for (int k = 0; k < gBranches; k++) {
__int128 bestVal = NEG;
int bestCity = -1;
int bestVtx = -1;
long long bestSec = NEG_SEC;
int16_t bestMove = -1;
int32_t bestPopDiv = -1;
for (int city = 0; city < N; city++) {
if (usedEndCity[city]) continue;
int v = cityBestVtx[city];
if (v < 0) continue;
__int128 val = cityBestVal[city];
long long sec = cityBestSec[city];
if (gBranchMode == 1 && selectedCnt > 0) {
double minD = 1e100;
for (int i = 0; i < selectedCnt; i++) minD = min(minD, distMat[city][selectedCities[i]]);
sec += (long long)llround(minD * gBranchDivW);
} else if (gBranchMode == 2 && selectedCnt > 0) {
int arr = v % TS;
int minDt = TS;
for (int i = 0; i < selectedCnt; i++) minDt = min(minDt, abs(arr - selectedArr[i]));
sec += 1LL * gBranchDivW * minDt;
}
if (val > bestVal ||
(val == bestVal && (sec > bestSec ||
(sec == bestSec && (cityBestMove[city] > bestMove ||
(cityBestMove[city] == bestMove && (cityBestPopDiv[city] > bestPopDiv ||
(cityBestPopDiv[city] == bestPopDiv &&
(bestVtx < 0 || v < bestVtx))))))))) {
bestVal = val;
bestCity = city;
bestVtx = v;
bestSec = sec;
bestMove = cityBestMove[city];
bestPopDiv = cityBestPopDiv[city];
}
}
if (bestCity < 0) break;
usedEndCity[bestCity] = true;
selectedCities[selectedCnt] = bestCity;
selectedArr[selectedCnt] = bestVtx % TS;
selectedCnt++;
out.push_back(RouteCandidate{restoreFlightsFromEnd(bestVtx, prevv), bestVal});
}
return out;
}
static vector<vector<int>> buildCandidateDestinations(const vector<int>& popOrder) {
// nearest + popular candidates, then deduplicated in ascending city index
vector<vector<int>> candDest(N);
for (int i=0;i<N;i++){
vector<pair<double,int>> near;
near.reserve(N-1);
for (int j=0;j<N;j++){
if (i==j) continue;
near.push_back({distMat[i][j], j});
}
sort(near.begin(), near.end());
vector<int> cand;
cand.reserve(min(NEAR_CAND, N-1) + min(POP_CAND, N-1) + 4);
int takeNear = min(NEAR_CAND, N-1);
for (int k=0; k<(int)near.size() && (int)cand.size()<takeNear; k++){
cand.push_back(near[k].second);
}
int takePop = min(POP_CAND, N-1);
int addedPop = 0;
for (int k=0; k<N && addedPop<takePop; k++){
int j = popOrder[k];
if (j==i) continue;
cand.push_back(j);
addedPop++;
}
sort(cand.begin(), cand.end());
cand.erase(unique(cand.begin(), cand.end()), cand.end());
candDest[i]=cand;
}
return candDest;
}
static vector<int> buildStartCities(const vector<int>& popOrder) {
vector<int> startCities;
for (int i=0;i<min(START_USE, N); i++) {
startCities.push_back(popOrder[i]);
}
return startCities;
}
static void buildDpTransitions(const vector<vector<int>>& candDest) {
// Keep candidate order to preserve exact DP tie behavior.
for (int c=0; c<N; c++) {
const auto& cd = candDest[c];
for (int t=0; t<TS; t++) {
int u = c*TS + t;
uint8_t cnt = 0;
for (int j: cd) {
int at = t + durSlot[c][j];
if (at >= TS) continue;
dpMoveV[u][cnt] = (uint16_t)(j*TS + at);
dpMoveStartTi[u][cnt] = (uint8_t)firstTiTime[at];
cnt++;
}
dpMoveCnt[u] = cnt;
}
}
}
static int buildOrigins(const vector<int>& popOrder,
int originsUsed[ORIGIN_USE],
uint64_t originW[ORIGIN_USE],
const int16_t (*originLatest[ORIGIN_USE])[TS]) {
int originsCount = 0;
for (int i=0; i<min(ORIGIN_USE, N); i++) {
int city = popOrder[i];
originsUsed[originsCount] = city;
originW[originsCount] = (uint64_t)popW[city];
originLatest[originsCount] = latestCi[city];
originsCount++;
}
return originsCount;
}
// ===== debug score =====
static long long evalScoreEstimate() {
__int128 vci=0, vsq=0;
for (int o=0;o<N;o++){
for (int d=0;d<N;d++){
if (!validPair[o][d]) continue;
__int128 ww = (__int128)popW[o] * (__int128)popW[d];
for (int ti=0;ti<TGT;ti++){
if (s_ci[o][d][ti] > s_sq[o][d][ti]) vci += ww;
else vsq += ww;
}
}
}
if (vci+vsq==0) return 0;
long double S = (long double)vci / (long double)(vci+vsq);
return (long long)floor(1e6L * S + 1e-12L);
}
struct BeamState {
CSRAdj<20000> ci;
vector<vector<FlightOut>> routes;
__int128 score;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Skip UTF-8 BOM if present in local test files.
if (cin.peek() == 0xEF) {
char b1 = 0, b2 = 0, b3 = 0;
cin.get(b1);
cin.get(b2);
cin.get(b3);
if (!(b1 == (char)0xEF && b2 == (char)0xBB && b3 == (char)0xBF)) {
cin.clear();
}
}
{
int v;
if (parseEnvInt("SC_BEAM_WIDTH", v) && v >= 1) gBeamWidth = v;
if (parseEnvInt("SC_BRANCHES", v) && v >= 1) gBranches = v;
if (parseEnvInt("SC_TIE_MOVE", v)) gTieMove = v;
if (parseEnvInt("SC_TIE_POPDIV", v)) gTiePopDiv = v;
if (parseEnvInt("SC_TIE_ARR", v)) gTieArr = v;
if (parseEnvInt("SC_BRANCH_MODE", v)) gBranchMode = v;
if (parseEnvInt("SC_BRANCH_DIVW", v)) gBranchDivW = v;
if (parseEnvInt("SC_SCORE_MODE", v)) gScoreMode = v;
if (parseEnvInt("SC_BEAM_GAP", v)) gBeamGap = v;
if (parseEnvInt("SC_VERBOSE_STEP", v)) gVerboseStep = v;
if (parseEnvInt("SC_EVAL_FLIGHT_W", v)) gEvalFlightW = v;
if (parseEnvInt("SC_EVAL_POPDIV_W", v)) gEvalPopDivW = v;
if (parseEnvInt("SC_EVAL_LATEARR_W", v)) gEvalLateArrW = v;
}
cin >> N >> R;
vector<int> xs(N), ys(N);
for (int i=0;i<N;i++) cin >> xs[i] >> ys[i] >> popW[i];
for (int i=0;i<TGT;i++){
int minute = 11*60 + 30*i;
tgtIdx[i] = timeToIdx(minute);
}
{
int cur=0;
for (int t=0;t<TS;t++){
while (cur<TGT && tgtIdx[cur] < t) cur++;
firstTiTime[t] = cur;
}
}
double thr = 0.25 * (double)R;
for (int i=0;i<N;i++){
for (int j=0;j<N;j++){
double dx = (double)xs[i]-xs[j];
double dy = (double)ys[i]-ys[j];
double d = sqrt(dx*dx + dy*dy);
distMat[i][j]=d;
validPair[i][j] = (d >= thr);
if (i==j) durSlot[i][j]=0;
else {
double raw = 60.0 * d / 800.0 + 40.0;
int q = (int)ceil(raw / 5.0 - 1e-12);
durSlot[i][j] = q; // in 5-min slots
}
}
}
buildWeightTables(popW);
int M;
cin >> M;
sqAdj.init();
for (int k=0;k<M;k++){
int a,b;
string ss, tt;
cin >> a >> ss >> b >> tt;
--a; --b;
int s = timeToIdx(parseTimeStr(ss));
int t = timeToIdx(parseTimeStr(tt));
sqAdj.addEdge(a*TS + s, b, t);
}
sqAdj.build();
int K;
cin >> K;
(void)K;
ciAdj.init();
// Square: earliest/latest/targets
buildEarliestAndLatest(sqAdj, earliestSq, latestSq);
buildTargetsFromLatest(latestSq, s_sq);
// population order
vector<int> popOrder(N);
iota(popOrder.begin(), popOrder.end(), 0);
sort(popOrder.begin(), popOrder.end(), [&](int a,int b){ return popW[a]>popW[b]; });
vector<vector<int>> candDest = buildCandidateDestinations(popOrder);
vector<int> startCities = buildStartCities(popOrder);
buildDpTransitions(candDest);
// origins: all cities (pop order)
int originsUsed[ORIGIN_USE];
uint64_t originW[ORIGIN_USE];
const int16_t (*originLatest[ORIGIN_USE])[TS];
int originsCount = buildOrigins(popOrder, originsUsed, originW, originLatest);
vector<BeamState> beam;
beam.reserve(gBeamWidth);
BeamState root;
root.ci.init();
root.routes.reserve(K_FIXED);
root.score = 0;
beam.push_back(move(root));
for (int plane = 0; plane < K_FIXED; plane++) {
vector<BeamState> nextBeam;
nextBeam.reserve(gBeamWidth * gBranches);
for (auto& st : beam) {
st.ci.build();
buildEarliestAndLatest(st.ci, earliestCi, latestCi);
buildTargetsFromLatest(latestCi, s_ci);
long long parentTrueScore = 0;
if (gScoreMode == 1) parentTrueScore = evalScoreEstimate();
buildReachMaskFromEarliestFast(earliestCi);
buildFlipMaskForOrigins(originsUsed, originsCount);
buildActOrigins(originLatest, originW, originsCount);
auto candRoutes = solveOnePlaneDPTopK(startCities);
if (candRoutes.empty()) candRoutes.push_back(RouteCandidate{{}, 0});
for (int i = 0; i < (int)candRoutes.size(); i++) {
BeamState child = st;
if (gScoreMode == 1) {
child.score = (__int128)parentTrueScore + candRoutes[i].value;
} else {
child.score = st.score + candRoutes[i].value;
}
child.score += (__int128)routeEvalBonus(candRoutes[i].flights);
child.routes.push_back(candRoutes[i].flights);
for (const auto& f : candRoutes[i].flights) {
int uV = f.a * TS + f.dep_t;
child.ci.addEdge(uV, f.b, f.arr_t);
}
nextBeam.push_back(move(child));
}
}
if (nextBeam.empty()) {
cerr << "[beam step " << (plane + 1) << "] no candidates\n";
break;
}
sort(nextBeam.begin(), nextBeam.end(), [](const BeamState& a, const BeamState& b) {
return a.score > b.score;
});
if ((int)nextBeam.size() > gBeamWidth) nextBeam.resize(gBeamWidth);
if (gBeamGap >= 0 && !nextBeam.empty()) {
__int128 thr = nextBeam[0].score - (__int128)gBeamGap;
int keep = 0;
while (keep < (int)nextBeam.size() && nextBeam[keep].score >= thr) keep++;
if (keep <= 0) keep = 1;
if (keep < (int)nextBeam.size()) nextBeam.resize(keep);
}
beam.swap(nextBeam);
if (gVerboseStep) {
cerr << "[beam step " << (plane + 1) << "] beam_size=" << beam.size()
<< " best_flights=" << beam[0].routes.back().size() << "\n";
}
}
BeamState best = beam[0];
vector<vector<FlightOut>> routes = best.routes;
if ((int)routes.size() < K_FIXED) routes.resize(K_FIXED);
auto buildCiFromRoutes = [&](const vector<vector<FlightOut>>& rs, CSRAdj<20000>& outCi) {
outCi.init();
for (const auto& r : rs) {
for (const auto& f : r) outCi.addEdge(f.a * TS + f.dep_t, f.b, f.arr_t);
}
};
auto evalCiScore = [&](CSRAdj<20000>& ci) -> long long {
ci.build();
buildEarliestAndLatest(ci, earliestCi, latestCi);
buildTargetsFromLatest(latestCi, s_ci);
return evalScoreEstimate();
};
auto sameRoute = [&](const vector<FlightOut>& a, const vector<FlightOut>& b) -> bool {
if (a.size() != b.size()) return false;
for (int i = 0; i < (int)a.size(); i++) {
if (a[i].a != b[i].a || a[i].b != b[i].b || a[i].dep_t != b[i].dep_t || a[i].arr_t != b[i].arr_t) return false;
}
return true;
};
buildCiFromRoutes(routes, ciAdj);
long long bestTrueScore = evalCiScore(ciAdj);
// Small coordinate improvement: re-optimize weak (short) routes a few times.
{
static constexpr int REFINE_TRIALS = 3;
bool usedPlane[K_FIXED];
memset(usedPlane, 0, sizeof(usedPlane));
for (int tr = 0; tr < REFINE_TRIALS; tr++) {
int targetPlane = -1;
long long worstBonus = (1LL << 60);
int bestLen = INT_MAX;
for (int p = 0; p < K_FIXED; p++) {
if (usedPlane[p]) continue;
long long b = routeEvalBonus(routes[p]);
int len = (int)routes[p].size();
if (b < worstBonus || (b == worstBonus && len < bestLen)) {
worstBonus = b;
bestLen = len;
targetPlane = p;
}
}
if (targetPlane < 0) break;
usedPlane[targetPlane] = true;
vector<vector<FlightOut>> without = routes;
without[targetPlane].clear();
CSRAdj<20000> ciWithout;
buildCiFromRoutes(without, ciWithout);
evalCiScore(ciWithout);
buildReachMaskFromEarliestFast(earliestCi);
buildFlipMaskForOrigins(originsUsed, originsCount);
buildActOrigins(originLatest, originW, originsCount);
auto cand = solveOnePlaneDPTopK(startCities);
if (!cand.empty() && !sameRoute(cand[0].flights, routes[targetPlane])) {
auto old = routes[targetPlane];
routes[targetPlane] = cand[0].flights;
CSRAdj<20000> ciTry;
buildCiFromRoutes(routes, ciTry);
long long scTry = evalCiScore(ciTry);
if (scTry > bestTrueScore) {
bestTrueScore = scTry;
ciAdj = move(ciTry);
} else {
routes[targetPlane] = move(old);
}
}
}
}
// final debug
cerr << "[final estimated score] " << bestTrueScore << "\n";
// output
for (int p=0;p<K_FIXED;p++){
cout << routes[p].size() << "\n";
for (auto &f: routes[p]) {
cout << (f.a+1) << " " << fmtTimeIdx(f.dep_t) << " "
<< (f.b+1) << " " << fmtTimeIdx(f.arr_t) << "\n";
}
}
return 0;
}