#1149337 (C++17) No.5023 Airlines Optimization

• 問題: No.5023 Airlines Optimization
• ユーザー: mtmr_s1
• 提出日時: 2026-02-25 22:53:37
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 90 ms / 1,000 ms
• コード長: 9,185 bytes
• コンパイル時間: 3,108 ms
• コンパイル使用メモリ: 252,428 KB
• 実行使用メモリ: 7,848 KB
• スコア: 39,819,837
• 最終ジャッジ日時: 2026-02-25 22:54:03
• 合計ジャッジ時間: 16,125 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

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

ソースコード

#include <bits/stdc++.h>
using namespace std;

static constexpr int START_MIN = 6 * 60;
static constexpr int END_MIN = 21 * 60;
static constexpr int STEP_MIN = 5;
static constexpr int TICK_MAX = (END_MIN - START_MIN) / STEP_MIN; // 180
static constexpr int NEG_INF = -1;

struct City {
  int x, y;
  long long w;
};

struct Flight {
  int a, b; // 0-based city
  int s, t; // tick [0..180]
};

struct Candidate {
  bool valid = false;
  int b = -1;
  int t = -1;
  int dur = -1;
  long long delta = LLONG_MIN;
  long long potential = LLONG_MIN;
  long long pop = LLONG_MIN;
};

static int time_to_idx(const string &hhmm) {
  int hh = stoi(hhmm.substr(0, 2));
  int mm = stoi(hhmm.substr(3, 2));
  int mins = hh * 60 + mm;
  return (mins - START_MIN) / STEP_MIN;
}

static string idx_to_time(int idx) {
  int mins = START_MIN + idx * STEP_MIN;
  int hh = mins / 60;
  int mm = mins % 60;
  ostringstream oss;
  oss << setw(2) << setfill('0') << hh << ":" << setw(2) << setfill('0') << mm;
  return oss.str();
}

static int duration_ticks(const City &c1, const City &c2) {
  double dx = double(c1.x - c2.x);
  double dy = double(c1.y - c2.y);
  double dist = sqrt(dx * dx + dy * dy);
  double raw = 60.0 * dist / 800.0 + 40.0;
  int rounded = int(ceil(raw / 5.0 - 1e-12) * 5.0);
  return rounded / 5;
}

static inline int latest_idx(int n, int dcount, int dest, int dk, int orig) {
  return ((dest * dcount) + dk) * n + orig;
}

static void compute_latest_all_sorted(
    int n,
    const vector<int> &deadlines,
    const vector<Flight> &flights_desc,
    vector<int> &latest_out) {
  const int dcount = (int)deadlines.size();
  latest_out.assign(n * dcount * n, NEG_INF);

  for (int dest = 0; dest < n; dest++) {
    for (int dk = 0; dk < dcount; dk++) {
      int deadline = deadlines[dk];
      int base = latest_idx(n, dcount, dest, dk, 0);
      int *L = &latest_out[base];
      fill(L, L + n, NEG_INF);
      L[dest] = deadline;

      for (const auto &f : flights_desc) {
        if (f.t > deadline) {
          continue;
        }
        if (L[f.b] >= f.t && f.s > L[f.a]) {
          L[f.a] = f.s;
        }
      }
    }
  }
}

static long long evaluate_vci(
    int n,
    const vector<int> &deadlines,
    const vector<int> &sq_latest,
    const vector<int> &ci_latest,
    const vector<vector<pair<int, long long>>> &relevant_dests) {
  const int dcount = (int)deadlines.size();
  long long vci = 0;
  for (int orig = 0; orig < n; orig++) {
    for (const auto &[dest, wprod] : relevant_dests[orig]) {
      for (int dk = 0; dk < dcount; dk++) {
        int sq = sq_latest[latest_idx(n, dcount, dest, dk, orig)];
        int ci = ci_latest[latest_idx(n, dcount, dest, dk, orig)];
        if (sq < ci) {
          vci += wprod;
        }
      }
    }
  }
  return vci;
}

static long long estimate_delta_origin_only(
    int n,
    const vector<int> &deadlines,
    const vector<int> &sq_latest,
    const vector<int> &ci_latest,
    const vector<vector<pair<int, long long>>> &relevant_dests,
    int a,
    int b,
    int s,
    int t) {
  const int dcount = (int)deadlines.size();
  long long delta = 0;

  for (const auto &[dest, wprod] : relevant_dests[a]) {
    for (int dk = 0; dk < dcount; dk++) {
      int idx_b = latest_idx(n, dcount, dest, dk, b);
      if (ci_latest[idx_b] < t) {
        continue;
      }

      int idx_a = latest_idx(n, dcount, dest, dk, a);
      int old_ci = ci_latest[idx_a];
      if (old_ci >= s) {
        continue;
      }

      int sq = sq_latest[idx_a];
      bool old_win = (sq < old_ci);
      bool new_win = (sq < s);
      if (!old_win && new_win) {
        delta += wprod;
      }
    }
  }

  return delta;
}

static bool better_candidate(const Candidate &lhs, const Candidate &rhs) {
  if (!lhs.valid) return false;
  if (!rhs.valid) return true;
  if (lhs.delta != rhs.delta) return lhs.delta > rhs.delta;
  if (lhs.potential != rhs.potential) return lhs.potential > rhs.potential;
  if (lhs.pop != rhs.pop) return lhs.pop > rhs.pop;
  if (lhs.dur != rhs.dur) return lhs.dur < rhs.dur;
  return lhs.b < rhs.b;
}

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> square(m);
  for (int i = 0; i < m; i++) {
    int a, b;
    string ss, tt;
    cin >> a >> ss >> b >> tt;
    --a;
    --b;
    square[i] = Flight{a, b, time_to_idx(ss), time_to_idx(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) continue;
      dur[i][j] = duration_ticks(cities[i], cities[j]);
    }
  }

  vector<int> deadlines;
  {
    int base = (11 * 60 - START_MIN) / STEP_MIN; // 11:00
    for (int t = 0; t < 21; t++) {
      deadlines.push_back(base + t * 6); // every 30 min
    }
  }

  vector<Flight> square_desc = square;
  sort(square_desc.begin(), square_desc.end(), [](const Flight &p, const Flight &q) {
    if (p.s != q.s) return p.s > q.s;
    return p.t > q.t;
  });

  vector<int> sq_latest;
  compute_latest_all_sorted(n, deadlines, square_desc, sq_latest);

  vector<vector<pair<int, long long>>> relevant_dests(n);
  {
    long long rr = 1LL * r * r;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        long long dx = 1LL * cities[i].x - cities[j].x;
        long long dy = 1LL * cities[i].y - cities[j].y;
        long long d2 = dx * dx + dy * dy;
        if (16LL * d2 >= rr) {
          relevant_dests[i].push_back({j, cities[i].w * cities[j].w});
        }
      }
    }
  }

  vector<vector<long long>> need_score(n, vector<long long>(TICK_MAX + 1, 0));
  {
    const int dcount = (int)deadlines.size();
    for (int orig = 0; orig < n; orig++) {
      for (int s = 0; s <= TICK_MAX; s++) {
        long long val = 0;
        for (const auto &[dest, wprod] : relevant_dests[orig]) {
          for (int dk = 0; dk < dcount; dk++) {
            int sq = sq_latest[latest_idx(n, dcount, dest, dk, orig)];
            if (sq < s) {
              val += wprod;
            }
          }
        }
        need_score[orig][s] = val;
      }
    }
  }

  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int a, int b) {
    return cities[a].w > cities[b].w;
  });

  vector<int> plane_city(k), plane_time(k, 0);
  vector<vector<Flight>> plane_legs(k);
  for (int p = 0; p < k; p++) {
    plane_city[p] = order[p % n];
  }

  vector<Flight> circle_desc;
  vector<int> ci_latest;
  compute_latest_all_sorted(n, deadlines, circle_desc, ci_latest);

  auto insert_flight_desc = [&](const Flight &f) {
    auto it = lower_bound(
        circle_desc.begin(),
        circle_desc.end(),
        f,
        [](const Flight &x, const Flight &y) {
          if (x.s != y.s) return x.s > y.s;
          return x.t > y.t;
        });
    circle_desc.insert(it, f);
  };

  int steps = 0;
  while (true) {
    int p = -1;
    int best_time = TICK_MAX + 1;
    for (int i = 0; i < k; i++) {
      if (plane_time[i] <= TICK_MAX && plane_time[i] < best_time) {
        best_time = plane_time[i];
        p = i;
      }
    }
    if (p < 0) {
      break;
    }

    int a = plane_city[p];
    int s = plane_time[p];

    Candidate best;
    best.valid = false;

    for (int b = 0; b < n; b++) {
      if (b == a) continue;
      int d = dur[a][b];
      if (d <= 0) continue;
      int t = s + d;
      if (t > TICK_MAX) continue;

      long long delta = estimate_delta_origin_only(
          n, deadlines, sq_latest, ci_latest, relevant_dests, a, b, s, t);
      long long potential = need_score[b][t];

      Candidate cand;
      cand.valid = true;
      cand.b = b;
      cand.t = t;
      cand.dur = d;
      cand.delta = delta;
      cand.potential = potential;
      cand.pop = cities[b].w;

      if (better_candidate(cand, best)) {
        best = cand;
      }
    }

    if (!best.valid) {
      plane_time[p] = TICK_MAX + 1;
      continue;
    }

    if (best.delta <= 0 && best.potential <= 0) {
      plane_time[p] = TICK_MAX + 1;
      continue;
    }

    Flight f{a, best.b, s, best.t};
    plane_legs[p].push_back(f);
    insert_flight_desc(f);

    plane_city[p] = best.b;
    plane_time[p] = best.t;
    steps++;

    compute_latest_all_sorted(n, deadlines, circle_desc, ci_latest);

    if (steps % 40 == 0) {
      long long cur_vci = evaluate_vci(n, deadlines, sq_latest, ci_latest, relevant_dests);
      cerr << "[greedy] steps=" << steps
           << " flights=" << circle_desc.size()
           << " v_ci=" << cur_vci << '\n';
    }

    if (steps >= 2000) {
      break;
    }
  }

  long long final_vci = evaluate_vci(n, deadlines, sq_latest, ci_latest, relevant_dests);
  cerr << "[greedy] done flights=" << circle_desc.size() << " v_ci=" << final_vci << '\n';

  for (int p = 0; p < k; p++) {
    cout << plane_legs[p].size() << '\n';
    for (const auto &f : plane_legs[p]) {
      cout << (f.a + 1) << ' ' << idx_to_time(f.s) << ' '
           << (f.b + 1) << ' ' << idx_to_time(f.t) << '\n';
    }
  }

  return 0;
}