結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 ぴぃいいいい
|
| 提出日時 | 2026-03-01 09:20:18 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 837 ms / 1,000 ms |
| コード長 | 15,741 bytes |
| 記録 | |
| コンパイル時間 | 4,261 ms |
| コンパイル使用メモリ | 370,752 KB |
| 実行使用メモリ | 18,388 KB |
| スコア | 63,076,860 |
| 最終ジャッジ日時 | 2026-03-01 09:22:38 |
| 合計ジャッジ時間 | 83,386 ms |
|
ジャッジサーバーID （参考情報） |
judge6 / judge2 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
// yukicoder No.5023 Airlines Optimization
// Fixed hyperparams (behavior same except faster):
// candDest[i] = nearest 18 + top-pop 26
// origin limit = 47 (all cities)
// DP start cities = 47 (all cities)
//
// Compile: g++ -O2 -std=c++17 -pipe -static -s main.cpp -o main
#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;
// 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
};
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;
}
// ===== 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];
static bool oldWin[MAXN][MAXN][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)
// ===== sumW(mask) tables =====
static uint64_t T0[1<<16];
static uint64_t T1[1<<16];
static uint64_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)] + (uint64_t)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)] + (uint64_t)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)] + (uint64_t)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 =====
static void buildEarliestAndLatest(const CSRAdj<20000>& adj,
uint16_t earliest[MAXN][TS][MAXN],
int16_t latest[MAXN][MAXN][TS]) {
// 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;
}
}
}
// 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;
}
}
}
}
// overload for square-size adjacency
static void buildEarliestAndLatest_sq(const CSRAdj<M_FIXED + 8>& adj,
uint16_t earliest[MAXN][TS][MAXN],
int16_t latest[MAXN][MAXN][TS]) {
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]);
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 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;
}
}
}
}
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;
}
}
}
static void buildOldWin() {
for (int o=0;o<N;o++){
for (int d=0;d<N;d++){
for (int ti=0;ti<TGT;ti++){
if (!validPair[o][d]) { oldWin[o][d][ti]=false; continue; }
oldWin[o][d][ti] = (s_ci[o][d][ti] > s_sq[o][d][ti]);
}
}
}
}
// build flipMask[oi][s][ti]
static void buildFlipMaskForOrigins(const vector<int>& originsUsed) {
for (int oi=0; oi<(int)originsUsed.size(); 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 (oldWin[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 vector<int>& originsUsed) {
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<(int)originsUsed.size(); oi++) {
int oCity = originsUsed[oi];
int16_t s = latestCi[oCity][c][t];
if (s < 0) continue;
act[u].wo[cnt] = (uint64_t)popW[oCity];
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 arrT) {
uint64_t gain = 0;
const ActOrigins& A = act[u];
const uint64_t* rm = reachMask[vtx];
int startTi = firstTiTime[arrT];
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;
gain += wo * sumW_mask(m);
}
}
return gain;
}
// ===== DP for one plane =====
static vector<FlightOut> solveOnePlaneDP(const vector<vector<int>>& candDest,
const vector<int>& startCities) {
static __int128 dp[V];
static int prevv[V];
const __int128 NEG = -((__int128)1<<120);
for (int i=0;i<V;i++){ dp[i]=NEG; prevv[i]=-1; }
for (int c: startCities) dp[c*TS + 0] = 0;
__int128 bestVal = 0;
int bestVtx = startCities.empty() ? 0 : startCities[0]*TS;
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;
if (cur > bestVal) { bestVal=cur; bestVtx=u; }
// wait
if (t+1 < TS) {
int v = u+1;
if (cur > dp[v]) { dp[v]=cur; prevv[v]=u; }
}
// flight candidates (order preserved: candDest[c] is sorted asc)
const auto& cd = candDest[c];
for (int j: cd) {
int at = t + durSlot[c][j];
if (at >= TS) continue;
int v = j*TS + at;
uint64_t g = edgeGainUV(u, v, at);
__int128 nv = cur + (__int128)g;
if (nv > dp[v]) {
dp[v]=nv;
prevv[v]=u;
}
}
}
}
for (int u=0;u<V;u++){
if (dp[u] > bestVal) { bestVal=dp[u]; bestVtx=u; }
}
vector<FlightOut> revFlights;
int cur = bestVtx;
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;
}
// ===== 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);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
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_sq(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]; });
// candDest: nearest 18 + top-pop 26, then sort+unique (same behavior pattern)
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;
}
// starts: all cities (pop order)
vector<int> startCities;
for (int i=0;i<min(START_USE, N); i++) startCities.push_back(popOrder[i]);
// origins: all cities (pop order)
vector<int> originsUsed;
for (int i=0;i<min(ORIGIN_USE, N); i++) originsUsed.push_back(popOrder[i]);
vector<vector<FlightOut>> routes(K_FIXED);
for (int plane=0; plane<K_FIXED; plane++) {
// rebuild CSR for current circle schedule (fast, contiguous)
ciAdj.build();
buildEarliestAndLatest(ciAdj, earliestCi, latestCi);
buildTargetsFromLatest(latestCi, s_ci);
buildReachMaskFromEarliestFast(earliestCi);
buildOldWin();
buildFlipMaskForOrigins(originsUsed);
buildActOrigins(originsUsed);
auto fl = solveOnePlaneDP(candDest, startCities);
routes[plane] = fl;
for (auto &f: fl) {
int uV = f.a*TS + f.dep_t;
ciAdj.addEdge(uV, f.b, f.arr_t);
}
cerr << "[plane " << (plane+1) << "] flights=" << fl.size() << "\n";
}
// final debug
{
ciAdj.build();
buildEarliestAndLatest(ciAdj, earliestCi, latestCi);
buildTargetsFromLatest(latestCi, s_ci);
cerr << "[final estimated score] " << evalScoreEstimate() << "\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;
}