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

• 問題: No.5023 Airlines Optimization
• ユーザー: mtmr_s1
• 提出日時: 2026-02-25 22:09:36
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 986 ms / 1,000 ms
• コード長: 12,081 bytes
• コンパイル時間: 3,400 ms
• コンパイル使用メモリ: 255,984 KB
• 実行使用メモリ: 7,844 KB
• スコア: 35,475,188
• 最終ジャッジ日時: 2026-02-25 22:11:25
• 合計ジャッジ時間: 108,033 ms
• ジャッジサーバーID （参考情報）: judge2 / judge6

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

ソースコード

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

/*
  Simulated Annealing Solver (C++20) - "Important cities / latest-departure wins"

  - We maximize v_ci (weighted wins), since denominator is constant.
  - Compare, for each (src i, dest j, deadline T):
        s_sq(i->j,T) < s_ci(i->j,T)  => Circle wins, add w_i*w_j to v_ci.
    where s_* is the latest departure time (5-min ticks) that can still arrive by T.
  - We compute latest departure via backward reachability DP on time-expanded DAG-ish flights:
        L[dest]=T, others=-INF
        if there is flight u(s->t)->v and t<=L[v], then L[u]=max(L[u], s)

  Representation (Circle):
    - Each plane is a simple shuttle between two cities u<->v
    - Start offset in [0..11] meaning 06:00 + 5*offset
    - Plane runs greedily back and forth until 21:00.

  SA moves:
    - Toggle plane enabled
    - Change plane pair among top-P important cities
    - Change plane start offset
    - Swap two planes

  NOTE: This is a "working baseline SA". It is not fast-optimal.
*/

static constexpr int START_MIN = 6 * 60;
static constexpr int END_MIN   = 21 * 60;
static constexpr int STEP_MIN  = 5;

// 06:00..21:00 inclusive => indices 0..180 (181 values)
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; // 0..180
};

struct IncomingEdge {
  int a; // from
  int s; // depart
  int t; // arrive
};

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 double dist_euclid(const City& A, const City& B) {
  double dx = double(A.x - B.x);
  double dy = double(A.y - B.y);
  return sqrt(dx*dx + dy*dy);
}

// duration: ceil_to_5(60*d/800 + 40) minutes => ticks
static int dur_ticks(const City& A, const City& B) {
  double d = dist_euclid(A,B);
  double raw = 60.0 * d / 800.0 + 40.0; // minutes
  int raw_int = (int)ceil(raw - 1e-12);
  int rounded = ((raw_int + 4) / 5) * 5;
  return rounded / 5;
}

// ------------------------------------------------------------
// Latest departure DP (single dest & deadline) with incremental processing
// incoming_sorted_by_t[v] must be sorted by t ascending.
// We maintain a pointer ptr[v] meaning "processed all incoming with t <= current L[v] up to ptr[v]".
// When L[v] increases, newly eligible flights are processed once.
// ------------------------------------------------------------
static vector<int> compute_latest_departure_single_dest_deadline(
    int N,
    const vector<vector<IncomingEdge>>& incoming_sorted_by_t,
    int dest,
    int deadline_T
) {
  vector<int> L(N, NEG_INF);
  vector<int> ptr(N, 0);

  deque<int> q;
  L[dest] = deadline_T;
  q.push_back(dest);

  while(!q.empty()) {
    int v = q.front(); q.pop_front();
    int Lv = L[v];
    if (Lv == NEG_INF) continue;

    const auto& inc = incoming_sorted_by_t[v];
    int &p = ptr[v];

    while (p < (int)inc.size() && inc[p].t <= Lv) {
      const auto &e = inc[p];
      p++;
      if (e.s > L[e.a]) {
        L[e.a] = e.s;
        q.push_back(e.a);
      }
    }
  }
  return L;
}

static vector<vector<vector<int>>> precompute_latest_all(
    int N,
    const vector<Flight>& flights,
    const vector<int>& deadlines
) {
  // incoming[v] = list of flights that arrive at v
  vector<vector<IncomingEdge>> incoming(N);
  for (const auto& f : flights) {
    incoming[f.b].push_back(IncomingEdge{f.a, f.s, f.t});
  }
  for (int v = 0; v < N; v++) {
    auto &inc = incoming[v];
    sort(inc.begin(), inc.end(), [](const IncomingEdge& p, const IncomingEdge& q){
      if (p.t != q.t) return p.t < q.t;
      return p.s < q.s;
    });
  }

  vector<vector<vector<int>>> latest(N, vector<vector<int>>(deadlines.size(), vector<int>(N, NEG_INF)));
  for (int dest = 0; dest < N; dest++) {
    for (int dk = 0; dk < (int)deadlines.size(); dk++) {
      int T = deadlines[dk];
      auto L = compute_latest_departure_single_dest_deadline(N, incoming, dest, T);
      latest[dest][dk] = std::move(L);
    }
  }
  return latest;
}

// ------------------------------------------------------------
// Circle schedule model: each plane is a shuttle u<->v with a start offset.
// ------------------------------------------------------------
struct Plane {
  int u = -1;
  int v = -1;
  int start = 0;  // 0..11 => 06:00 + 5*start
  bool enabled = false;
};

static vector<Flight> build_circle_flights_from_planes(
    const vector<City>& cities,
    const vector<Plane>& planes
) {
  vector<Flight> out;
  out.reserve(800);

  for (const auto& pl : planes) {
    if (!pl.enabled) continue;
    int u = pl.u, v = pl.v;
    if (u < 0 || v < 0 || u == v) continue;

    int cur_city = u;
    int other = v;
    int cur_t = pl.start;

    while (true) {
      int d = dur_ticks(cities[cur_city], cities[other]);
      int arr = cur_t + d;
      if (arr > TICK_MAX) break;
      out.push_back(Flight{cur_city, other, cur_t, arr});
      cur_t = arr;
      swap(cur_city, other);
    }
  }
  return out;
}

// ------------------------------------------------------------
// Scoring (objective): v_ci maximize
// ------------------------------------------------------------
struct PairSample {
  int i, j;         // src, dest
  long long wprod;  // w_i * w_j
};

static long long evaluate_v_ci(
    const vector<vector<vector<int>>>& sq_latest,
    const vector<vector<vector<int>>>& ci_latest,
    const vector<PairSample>& samples,
    int num_deadlines
) {
  long long vci = 0;
  for (const auto& ps : samples) {
    int i = ps.i, j = ps.j;
    long long wprod = ps.wprod;
    for (int dk = 0; dk < num_deadlines; dk++) {
      int ssq = sq_latest[j][dk][i];
      int sci = ci_latest[j][dk][i];
      if (ssq < sci) vci += wprod;
    }
  }
  return vci;
}

// RNG
struct XorShift {
  uint64_t x=88172645463325252ULL;
  uint64_t next_u64() {
    x ^= x<<7;
    x ^= x>>9;
    return x;
  }
  int next_int(int lo, int hi) { // inclusive
    return lo + (int)(next_u64() % (uint64_t)(hi - lo + 1));
  }
  double next_double() {
    return (next_u64() >> 11) * (1.0/9007199254740992.0); // [0,1)
  }
};

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 k = 0; k < M; k++) {
    int a, b;
    string s_str, t_str;
    cin >> a >> s_str >> b >> t_str;
    --a; --b;
    square[k] = Flight{a, b, time_to_idx(s_str), time_to_idx(t_str)};
  }
  int K;
  cin >> K;

  // deadlines: 11:00, 11:30, ..., 21:00 (21 values)
  vector<int> deadlines;
  {
    int idx_1100 = (11*60 - START_MIN) / STEP_MIN; // 60
    for (int k = 0; k < 21; k++) deadlines.push_back(idx_1100 + 6*k);
  }

  // Precompute square latest table once
  auto sq_latest = precompute_latest_all(N, square, deadlines);

  // Important city set: top-P by population
  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;
  });
  int P = 15;
  P = min(P, N);
  vector<int> top(order.begin(), order.begin()+P);

  // Samples: all directed pairs (i,j) with dist>=0.25R, i!=j
  vector<PairSample> samples;
  samples.reserve(N*N);
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) if (i != j) {
      if (dist_euclid(cities[i], cities[j]) >= 0.25 * (double)R) {
        long long wprod = cities[i].w * cities[j].w;
        samples.push_back(PairSample{i, j, wprod});
      }
    }
  }

  // Initial state: fill planes with distinct pairs among top cities
  vector<Plane> cur(K), best_state(K);
  {
    for (int pi = 0; pi < K; pi++) {
      cur[pi].enabled = false;
      cur[pi].u = top[0];
      cur[pi].v = top[min(1, P-1)];
      cur[pi].start = 0;
    }
    int idx = 0;
    for (int ii = 0; ii < P && idx < K; ii++) {
      for (int jj = ii+1; jj < P && idx < K; jj++) {
        int u = top[ii], v = top[jj];
        if (dist_euclid(cities[u], cities[v]) < 0.25 * (double)R) continue;
        cur[idx].enabled = true;
        cur[idx].u = u;
        cur[idx].v = v;
        cur[idx].start = (idx % 12);
        idx++;
      }
    }
  }

  // Evaluate initial
  {
    auto cur_flights = build_circle_flights_from_planes(cities, cur);
    auto cur_latest  = precompute_latest_all(N, cur_flights, deadlines);
    long long cur_vci = evaluate_v_ci(sq_latest, cur_latest, samples, (int)deadlines.size());

    long long best_vci = cur_vci;
    best_state = cur;

    XorShift rng;
    auto start_clock = chrono::high_resolution_clock::now();

    // SA params
    const double TIME_LIMIT_SEC = 0.98;
    const double T0 = 2.0e12; // scale large
    const double T1 = 1.0e9;

    auto elapsed_sec = [&](){
      auto now = chrono::high_resolution_clock::now();
      return chrono::duration<double>(now - start_clock).count();
    };
    auto temperature = [&](double t){
      double x = min(1.0, t / TIME_LIMIT_SEC);
      double logT = log(T0) * (1.0 - x) + log(T1) * x;
      return exp(logT);
    };

    auto apply_random_move = [&](vector<Plane>& st){
      int p = rng.next_int(0, K-1);
      int typ = rng.next_int(0, 99);

      if (typ < 20) {
        // toggle enabled
        st[p].enabled = !st[p].enabled;
        if (st[p].enabled && (st[p].u < 0 || st[p].v < 0 || st[p].u == st[p].v)) {
          st[p].u = top[0];
          st[p].v = top[min(1, P-1)];
          st[p].start = rng.next_int(0, 11);
        }
      } else if (typ < 55) {
        // change pair among top cities
        int u = top[rng.next_int(0, P-1)];
        int v = top[rng.next_int(0, P-1)];
        while (v == u) v = top[rng.next_int(0, P-1)];
        st[p].u = u;
        st[p].v = v;
        st[p].enabled = true;
      } else if (typ < 80) {
        // change start offset
        st[p].start = rng.next_int(0, 11);
        st[p].enabled = true;
      } else {
        // swap two planes
        int q = rng.next_int(0, K-1);
        swap(st[p], st[q]);
      }
    };

    while (true) {
      double t = elapsed_sec();
      if (t >= TIME_LIMIT_SEC) break;
      double Temp = temperature(t);

      vector<Plane> nxt = cur;
      apply_random_move(nxt);

      auto nxt_flights = build_circle_flights_from_planes(cities, nxt);
      auto nxt_latest  = precompute_latest_all(N, nxt_flights, deadlines);
      long long nxt_vci = evaluate_v_ci(sq_latest, nxt_latest, samples, (int)deadlines.size());

      long long delta = nxt_vci - cur_vci;

      bool accept = false;
      if (delta >= 0) {
        accept = true;
      } else {
        double prob = exp((double)delta / Temp);
        if (rng.next_double() < prob) accept = true;
      }

      if (accept) {
        cur = std::move(nxt);
        cur_vci = nxt_vci;
        if (cur_vci > best_vci) {
          best_vci = cur_vci;
          best_state = cur;
        }
      }
    }
  }

  // Output best schedule
  for (int pi = 0; pi < K; pi++) {
    const auto& pl = best_state[pi];
    if (!pl.enabled || pl.u < 0 || pl.v < 0 || pl.u == pl.v) {
      cout << 0 << "\n";
      continue;
    }

    vector<Flight> legs;
    int cur_city = pl.u;
    int other = pl.v;
    int cur_t = pl.start;

    while (true) {
      int d = dur_ticks(cities[cur_city], cities[other]);
      int arr = cur_t + d;
      if (arr > TICK_MAX) break;
      legs.push_back(Flight{cur_city, other, cur_t, arr});
      cur_t = arr;
      swap(cur_city, other);
    }

    cout << legs.size() << "\n";
    for (const auto& f : legs) {
      cout << (f.a + 1) << " " << idx_to_time(f.s) << " "
           << (f.b + 1) << " " << idx_to_time(f.t) << "\n";
    }
  }

  return 0;
}