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

• 問題: No.5023 Airlines Optimization
• ユーザー: sibasyun
• 提出日時: 2026-02-25 23:09:56
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 27 ms / 1,000 ms
• コード長: 11,358 bytes
• コンパイル時間: 3,245 ms
• コンパイル使用メモリ: 259,420 KB
• 実行使用メモリ: 17,664 KB
• スコア: 5,895,571
• 最終ジャッジ日時: 2026-02-25 23:10:08
• 合計ジャッジ時間: 10,670 ms
• ジャッジサーバーID （参考情報）: judge7 / judge1

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

ソースコード

#include <algorithm>
#include <array>
#include <bits/stdc++.h>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <math.h>
#include <random>
#include <vector>

using namespace std;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vl = vector<long long>;
using vvl = vector<vector<long long>>;
using vvvl = vector<vector<vector<long long>>>;

using ll = long long;
template <class T> using max_heap = priority_queue<T>;
template <class T> using min_heap = priority_queue<T, vector<T>, greater<>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, f, n) for (int i = (int)f; i < (int)(n); i++)
#define repd(i, n, l) for (int i = (int)n; i >= (int)l; i--)
#define all(p) p.begin(), p.end()
const ll inf = 1LL << 60;
void print() { putchar(' '); }
void print(bool a) { printf("%d", a); }
void print(int a) { printf("%d", a); }
void print(unsigned a) { printf("%u", a); }
void print(long a) { printf("%ld", a); }
void print(long long a) { printf("%lld", a); }
void print(unsigned long long a) { printf("%llu", a); }
void print(char a) { printf("%c", a); }
void print(char a[]) { printf("%s", a); }
void print(const char a[]) { printf("%s", a); }
void print(float a) { printf("%.15f", a); }
void print(double a) { printf("%.15f", a); }
void print(long double a) { printf("%.15Lf", a); }
void print(const string &a) {
  for (auto &&i : a)
    print(i);
}
template <class T> void print(const complex<T> &a) {
  if (a.real() >= 0)
    print('+');
  print(a.real());
  if (a.imag() >= 0)
    print('+');
  print(a.imag());
  print('i');
}
template <class T> void print(const vector<T> &);
template <class T, size_t size> void print(const array<T, size> &);
template <class T, class L> void print(const pair<T, L> &p);
template <class T, size_t size> void print(const T (&)[size]);
template <class T> void print(const vector<T> &a) {
  if (a.empty())
    return;
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    putchar(' ');
    print(*i);
  }
}
template <class T> void print(const deque<T> &a) {
  if (a.empty())
    return;
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    putchar(' ');
    print(*i);
  }
}
template <class T, size_t size> void print(const array<T, size> &a) {
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    putchar(' ');
    print(*i);
  }
}
template <class T, class L> void print(const pair<T, L> &p) {
  print(p.first);
  putchar(' ');
  print(p.second);
}
template <class T, size_t size> void print(const T (&a)[size]) {
  print(a[0]);
  for (auto i = a; ++i != end(a);) {
    putchar(' ');
    print(*i);
  }
}
template <class T> void print(const T &a) { cout << a; }

std::random_device seed_gen;
std::mt19937 engine(seed_gen());
uniform_real_distribution<> randR(0.0, 1.0);
using pii = pair<int, int>;
using vpii = vector<pii>;
using vvpii = vector<vector<pii>>;
using vvvpii = vector<vector<vector<pii>>>;

// https://atcoder.jp/contests/ahc002/submissions/47959319
//  時間をDouble型で管理し、経過時間も取り出せるクラス
class TimeKeeperDouble {
private:
  std::chrono::high_resolution_clock::time_point start_time_;
  double time_threshold_;

  double now_time_ = 0;

public:
  // 時間制限をミリ秒単位で指定してインスタンスをつくる。
  TimeKeeperDouble(const double time_threshold)
      : start_time_(std::chrono::high_resolution_clock::now()),
        time_threshold_(time_threshold) {}

  // 経過時間をnow_time_に格納する。
  void setNowTime() {
    auto diff = std::chrono::high_resolution_clock::now() - this->start_time_;
    this->now_time_ =
        std::chrono::duration_cast<std::chrono::microseconds>(diff).count() *
        1e-3; // ms
  }

  // 経過時間をnow_time_に取得する。
  double getNowTime() const { return this->now_time_; }

  // インスタンス生成した時から指定した時間制限を超過したか判定する。
  bool isTimeOver() const { return now_time_ >= time_threshold_; }
};

// 乱数を生成するクラス
class Random {
public:
  std::mt19937 mt_; // シード0でメルセンヌツイスターの乱数生成器を初期化
  // 0以上1.0未満の実数の範囲の乱数生成
  uniform_real_distribution<double> dd_{0, 1.0};

  // seedを指定して初期化
  Random(const int seed = 0) : mt_(std::mt19937(seed)) {}

  // 0以上m未満の整数の範囲の乱数
  inline int nextInt(const int m) {
    uniform_int_distribution<int> di(0, m - 1);
    return di(mt_);
  }

  // 0以上1.0未満の実数の範囲の乱数
  inline double nextDouble() { return dd_(mt_); }

  // 0以上1.0未満の実数の範囲の乱数のlog。焼きなまし法で使いやすい。
  inline double nextLog() { return log(dd_(mt_)); }
};

// ここから

const int N = 47;
const int R = 1000;
const int M = 400;
const int K = 25;

// 座標を格納する構造体
struct Coord{
    double x, y;
    Coord(double x, double y) : x(x), y(y) {}
    Coord() : x(0), y(0) {}
};

double dist(Coord a, Coord b){
    return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

vector<vector<double>> dist_matrix(N, vector<double>(N));

struct Flight{
    int from, to;
    int start, end;
    Flight(int from, int to, int start, int end) : from(from), to(to), start(start), end(end) {}
    Flight() : from(0), to(0), start(0), end(0) {}
};

vector<Coord> coords(N, Coord());
vector<ll> w(N);
vector<Flight> square_flights(M, Flight());
vector<vector<Flight>> flights(K, vector<Flight>());

// hh:mm -> int
int time2int(string time){
    int h, m;
    sscanf(time.c_str(), "%d:%d", &h, &m);
    return h*60 + m;
}

// int -> hh:mm
string int2time(int time){
    int h = time / 60;
    int m = time % 60;
    stringstream ss;
    ss << setw(2) << setfill('0') << h << ":" << setw(2) << setfill('0') << m;
    return ss.str();
}

struct Input{
    int N_, R_, M_, K_;
    void input(){
        cin >> N_ >> R_;
        assert(N_ == N && R_ == R);
        rep(i, N)
            cin >> coords[i].x >> coords[i].y >> w[i];
        cin >> M_;
        assert(M_ == M);
        rep(i, M){
            int from, to;
            string start, end;
            cin >> from >> start >> to >> end;
            from--, to--;
            int _s = time2int(start), _e = time2int(end);
            square_flights[i] = Flight(from, to, _s, _e);
        }
        cin >> K_;
        rep(i, N) rep(j, N){
            dist_matrix[i][j] = dist(coords[i], coords[j]);
        }
    }
};

void output(){
    rep(i, K){
        cout << flights[i].size() << endl;
        for (auto flight : flights[i]){
            cout << flight.from + 1 << ' ' << int2time(flight.start) << ' ' << flight.to + 1 << ' ' << int2time(flight.end) << endl;
        }
    }
}

// ユークリッド距離が0.25R以上のi, jの数を数える
void test(){
    int ans = 0;
    rep(i, N) rep(j, N){
        if (dist(coords[i], coords[j]) >= 0.25*R){
            ans++;
        }
    }
    cout << ans << endl;
}
const int INF = 10000;
// 時刻t(11:00, 11:30,,,,)までに、頂点jに到達するフライトのうち、各頂点から最も遅く出発できる時間を求める
vvvi latest(N, vvi(N, vi(24*60, -INF)));
vector<vector<tuple<int, int, int>>> G(N); // tuple : from, start time, end time. 逆辺を張る
void calc_latest(){
    int et = 11 * 60; // 11:00から、30分刻みでスタート
    vi added(M, 0);
    while (et <= 21 * 60){
        // グラフの更新
        rep(i, M) {
            if (added[i]) continue;
            if (square_flights[i].end <= et) {
                added[i] = 1;
                G[square_flights[i].to].push_back(make_tuple(square_flights[i].from, square_flights[i].start, square_flights[i].end));
            }
        }
        // 各頂点について、最も遅く到達できる時間を求める
        rep(i, N){
            // latest[i][i][et] = et; // 自分に到達できる最も遅い時間はetとなる
            max_heap<pair<int, int>> hq;
            hq.push({et, i});
            while (!hq.empty()){
                auto [t, v] = hq.top(); hq.pop();
                if (latest[i][v][t] > t) continue;
                latest[i][v][t] = t;
                for (auto [from, start, end] : G[v]){
                    if (end > t) continue;
                    if (latest[from][i][et] < start){
                        latest[from][i][et] = start;
                        hq.push({start, from});
                    }
                }
            }
        }
        et += 30;
    }
}

// 各et(11:00, 11:30,,,,)について、0.25R以上の距離の組について、wi * wj, 及び最も遅くスタートできる時間を格納する
vector<vector<tuple<ll, int, int, int>>> values(24*60);
void calc_values(){
    for (int et = 11 * 60; et <= 21 * 60; et += 30){
        rep(i, N) rep(j, N){
            if (dist(coords[i], coords[j]) < 0.25*R) continue;
            values[et].push_back(make_tuple(w[i] * w[j], latest[i][j][et], i, j));
        }
        sort(all(values[et]));
        reverse(all(values[et]));
        // debug
        // cout << values[et].size() << endl;
        // for (auto [value, start, i, j] : values[et]){
        //     cout << value << ' ' << int2time(start) << ' ' << i + 1 << ' ' << j + 1 << endl;
        // }
    }
}

// 貪欲に各飛行機を価値が高い順に割り付ける
// 飛行機の到達時間及び到着地をもつ必要があるが、それは答えの配列で管理可能
// wi * wjのmaxに対して10%未満の便については無視してもよいか？

// 5分単位で切り上げる
int leadtime(int i, int j){
    return ceil((60 * dist_matrix[i][j] / 800.0 + 40.0) / 5.0) * 5;
}

// struct Flight{
//     int from, to;
//     int start, end;
//     Flight(int from, int to, int start, int end) : from(from), to(to), start(start), end(end) {}
//     Flight() : from(0), to(0), start(0), end(0) {}
// };

void greedy(){
    ll max_value = 0;
    rep(i, N) rep(j, N){
        if (dist(coords[i], coords[j]) < 0.25*R) continue;
        max_value = max(max_value, w[i] * w[j]);
    }
    // 10%未満の便については無視してもよい
    ll threshold = max_value / 10;
    for (int et = 11 * 60; et <= 21 * 60; et += 30){
        for (auto [value, start, i, j] : values[et]){
            if (value < threshold) break;
            int lt = leadtime(i, j);
            if (et - lt < 6 * 60) continue; // 6時未満の便はスキップ
            if (et - lt > start) continue;
            rep(k, K){
                if (flights[k].size() == 0) {
                    flights[k].push_back(Flight(i, j, et - lt, et));
                    break;
                } else {
                    int now = flights[k].back().to;
                    if (now != i) continue;
                    if (now == j) continue;
                    int nt = flights[k].back().end;
                    if (et - lt >= nt){
                        flights[k].push_back(Flight(i, j, et - lt, et));
                        break;
                    }
                }
            }
        }
    }
}

int main(){
    TimeKeeperDouble tk(1.9);
    Input input;
    input.input();
    calc_latest();
    calc_values();
    greedy();
    output();
    return 0;
}