#1150854 (C++23) No.5023 Airlines Optimization

• 問題: No.5023 Airlines Optimization
• ユーザー: ぴぃいいいい
• 提出日時: 2026-03-01 01:32:13
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 428 ms / 1,000 ms
• コード長: 14,573 bytes
• コンパイル時間: 6,266 ms
• コンパイル使用メモリ: 367,496 KB
• 実行使用メモリ: 13,108 KB
• スコア: 54,890,548
• 最終ジャッジ日時: 2026-03-01 01:33:06
• 合計ジャッジ時間: 40,815 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
other	AC * 100

ソースコード

// yukicoder No.5023 Airlines Optimization
// Greedy by plane: build k-th plane route by DP on time-expanded graph,
// where each flight-edge weight = (approx.) additional wins vs Square when ONLY that edge is added.
//
// 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;

// ====== speed/quality knobs (heuristics) ======
static constexpr int ORIGIN_USE = 30;
static constexpr int START_USE  = 12;
static constexpr int NEAR_CAND  = 6;
static constexpr int POP_CAND   = 6;

static constexpr int K_FIXED = 25;
static constexpr int M_FIXED = 400;

// Target arrival times: 11:00, 11:30, ..., 21:00 (21 values)
static constexpr int TGT = 21;

struct FlightOut {
  int a, b;     // 0-based cities
  int dep_t;    // time index
  int 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;
  int 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;
}

// ===== global buffers =====
static uint32_t popW[MAXN];
static int N, R;

static int durSlot[MAXN][MAXN];
static double distMat[MAXN][MAXN];
static bool validPair[MAXN][MAXN];

static uint16_t earliestSq[MAXN][MAXN][TS];
static uint16_t earliestCi[MAXN][MAXN][TS];
static constexpr uint16_t INF16 = 65535;

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];

static uint64_t reachMask[V][TGT];
static bool oldWin[MAXN][MAXN][TGT];
static uint64_t flipMask[ORIGIN_USE][TGT][TS];

static int tgtIdx[TGT];
static int firstTiTime[TS]; // first target index whose deadline >= timeIdx, else TGT

// ===== fast sumW(mask) with static 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) {
  // chunk0 bits 0..15
  T0[0]=0;
  for (uint32_t m=1; m<(1u<<16); m++) {
    uint32_t b = __builtin_ctz(m);
    uint32_t pm = m & (m-1);
    T0[m] = T0[pm] + (uint64_t)w[b];
  }
  // chunk1 bits 16..31
  T1[0]=0;
  for (uint32_t m=1; m<(1u<<16); m++) {
    uint32_t b = __builtin_ctz(m);
    uint32_t pm = m & (m-1);
    T1[m] = T1[pm] + (uint64_t)w[16 + b];
  }
  // chunk2 bits 32..46 (15 bits)
  T2[0]=0;
  for (uint32_t m=1; m<(1u<<15); m++) {
    uint32_t b = __builtin_ctz(m);
    uint32_t pm = m & (m-1);
    T2[m] = T2[pm] + (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); // 15 bits
  return T0[a] + T1[b] + T2[c];
}

// ===== adjacency list (fixed array) =====
template<int MAXE>
struct Adj {
  int head[V];
  uint8_t to[MAXE];
  uint8_t arr_t[MAXE];
  int nxt[MAXE];
  int ecnt;

  void init() {
    std::fill(head, head+V, -1);
    ecnt = 0;
  }
  inline void addEdge(int u, int v, int at) {
    to[ecnt] = (uint8_t)v;
    arr_t[ecnt] = (uint8_t)at;
    nxt[ecnt] = head[u];
    head[u] = ecnt++;
  }
};

static Adj<M_FIXED + 5> sqAdj;
static Adj<20000> ciAdj; // plenty

// ===== Build earliest and latest arrays for a schedule =====
static void buildEarliestAndLatest(const int* head,
                                  const uint8_t* to,
                                  const uint8_t* arr_t,
                                  const int* nxt,
                                  uint16_t earliest[MAXN][MAXN][TS],
                                  int16_t latest[MAXN][MAXN][TS]) {
  // earliest
  for (int d=0; d<N; d++) {
    for (int t=TS-1; t>=0; t--) {
      for (int c=0; c<N; c++) {
        uint16_t best = INF16;
        if (c == d) best = (uint16_t)t;
        if (t+1 < TS) best = min(best, earliest[d][c][t+1]); // wait
        int u = c*TS + t;
        for (int ei=head[u]; ei!=-1; ei=nxt[ei]) {
          best = min(best, earliest[d][to[ei]][arr_t[ei]]);
        }
        earliest[d][c][t] = best;
      }
    }
  }

  // latestStart 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][o][s];
        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][MAXN][TS]) {
  uint64_t tmp[TGT];
  for (int vtx=0; vtx<N*TS; vtx++) {
    int c = vtx / TS;
    int t = vtx % TS;
    (void)t;
    for (int i=0;i<TGT;i++) tmp[i]=0;

    for (int d=0; d<N; d++) {
      uint16_t arr = earliest[d][c][t];
      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; }
        int16_t sq = s_sq[o][d][ti];
        int16_t ci = s_ci[o][d][ti];
        oldWin[o][d][ti] = (ci > sq);
      }
    }
  }
}

static void buildFlipMaskForOrigins(const vector<int>& originsUsed) {
  for (int oi=0; oi<(int)originsUsed.size(); oi++) {
    int o = originsUsed[oi];
    (void)o;
    for (int ti=0; ti<TGT; ti++) {
      uint64_t addAt[TS];
      for (int s=0;s<TS;s++) addAt[s]=0;
      for (int d=0; d<N; d++) {
        if (!validPair[originsUsed[oi]][d]) continue;
        if (oldWin[originsUsed[oi]][d][ti]) continue;
        int16_t sq = s_sq[originsUsed[oi]][d][ti];
        int thr = (sq < 0 ? 0 : (int)sq + 1); // need start > sq
        if (thr <= TS-1) addAt[thr] |= (1ull << d);
      }
      uint64_t cur=0;
      for (int s=0; s<TS; s++) {
        cur |= addAt[s];
        flipMask[oi][ti][s] = cur;
      }
    }
  }
}

// ===== active origins per vertex (skip latestCi < 0) =====
struct ActOrigins {
  uint8_t cnt;
  uint8_t oi[ORIGIN_USE];
  int16_t sidx[ORIGIN_USE];
  uint32_t wo[ORIGIN_USE];
};
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].oi[cnt] = (uint8_t)oi;
      act[u].sidx[cnt] = s;
      act[u].wo[cnt] = popW[oCity];
      cnt++;
    }
    act[u].cnt = cnt;
  }
}

// ===== Edge weight computation (same math, faster) =====
static inline uint64_t edgeGainUV(int u, int vtx) {
  uint64_t gain = 0;
  const ActOrigins& A = act[u];
  const uint64_t* rm = reachMask[vtx];
  int startTi = firstTiTime[vtx % TS];
  for (int k=0; k<(int)A.cnt; k++) {
    uint8_t oi = A.oi[k];
    int16_t s  = A.sidx[k];
    uint64_t wo = (uint64_t)A.wo[k];

    // flipMask[oi][ti][s] : ti stride is TS
    const uint64_t* fp = &flipMask[oi][0][s];
    fp += (size_t)startTi * TS;

    for (int ti=startTi; ti<TGT; ti++, fp += TS) {
      uint64_t m = (*fp) & rm[ti];
      if (!m) continue;
      gain += wo * sumW_mask(m);
    }
  }
  return gain;
}

// ===== Solve one plane by DP on time-expanded graph =====
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; }
      }

      // flights (candidate destinations only) - order preserved
      for (int j: candDest[c]) {
        int dt = durSlot[c][j];
        int at = t + dt;
        if (at >= TS) continue;
        int v = j*TS + at;

        uint64_t g = edgeGainUV(u, v);
        __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;
}

// ===== score evaluation (debug) =====
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++){
        int16_t sq = s_sq[o][d][ti];
        int16_t ci = s_ci[o][d][ti];
        if (ci > sq) vci += ww;
        else vsq += ww;
      }
    }
  }
  if (vci+vsq==0) return 0;
  long double S = (long double)vci / (long double)(vci+vsq);
  long long score = (long long)floor(1e6L * S + 1e-12L);
  return score;
}

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);
  }
  // precompute firstTiTime for all time indices 0..TS-1
  {
    int cur=0;
    for (int t=0;t<TS;t++){
      while (cur<TGT && tgtIdx[cur] < t) cur++;
      firstTiTime[t] = cur; // may be TGT
    }
  }

  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);
        int durMin = q * 5;
        durSlot[i][j] = durMin / 5;
      }
    }
  }

  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);
  }

  int K;
  cin >> K;
  (void)K;

  ciAdj.init();

  // Precompute Square: earliestSq, latestSq, s_sq
  buildEarliestAndLatest(sqAdj.head, sqAdj.to, sqAdj.arr_t, sqAdj.nxt, earliestSq, latestSq);
  buildTargetsFromLatest(latestSq, s_sq);

  // candidate destinations per city
  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(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(NEAR_CAND + POP_CAND + 4);
    for (int k=0;k<(int)near.size() && (int)cand.size()<NEAR_CAND;k++){
      cand.push_back(near[k].second);
    }
    for (int k=0;k<N && (int)cand.size()<NEAR_CAND+POP_CAND;k++){
      int j = popOrder[k];
      if (j==i) continue;
      cand.push_back(j);
    }
    sort(cand.begin(), cand.end());
    cand.erase(unique(cand.begin(), cand.end()), cand.end());
    candDest[i]=cand;
  }

  vector<int> startCities;
  for (int i=0;i<min(START_USE, N); i++) startCities.push_back(popOrder[i]);

  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++) {
    // current circle earliest/latest + s_ci
    buildEarliestAndLatest(ciAdj.head, ciAdj.to, ciAdj.arr_t, ciAdj.nxt, earliestCi, latestCi);
    buildTargetsFromLatest(latestCi, s_ci);

    // reach masks
    buildReachMaskFromEarliestFast(earliestCi);

    // oldWin + flipMask
    buildOldWin();
    buildFlipMaskForOrigins(originsUsed);

    // active origins list per vertex (skip latestCi < 0)
    buildActOrigins(originsUsed);

    // solve plane
    auto fl = solveOnePlaneDP(candDest, startCities);
    routes[plane] = fl;

    // add flights to circle schedule
    for (auto &f: fl) {
      int u = f.a*TS + f.dep_t;
      ciAdj.addEdge(u, f.b, f.arr_t);
    }

    cerr << "[plane " << (plane+1) << "] flights=" << fl.size() << "\n";
  }

  // final debug score estimate
  {
    buildEarliestAndLatest(ciAdj.head, ciAdj.to, ciAdj.arr_t, ciAdj.nxt, earliestCi, latestCi);
    buildTargetsFromLatest(latestCi, s_ci);
    long long est = evalScoreEstimate();
    cerr << "[final estimated score] " << est << "\n";
  }

  // output routes
  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;
}