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

• 問題: No.5023 Airlines Optimization
• ユーザー: Ang1077
• 提出日時: 2026-02-25 22:25:22
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 20,551 bytes
• コンパイル時間: 5,061 ms
• コンパイル使用メモリ: 366,356 KB
• 実行使用メモリ: 8,096 KB
• スコア: 0
• 最終ジャッジ日時: 2026-02-25 22:30:49
• 合計ジャッジ時間: 111,708 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

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

ソースコード

// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
constexpr bool DEBUG = true;
constexpr double TIME_LIMIT = 1.95;

// Macros
#define el '\n'
#define all(v) (v).begin(), (v).end()
using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
#define rep(i, n) for (i64 i = 0; i < (i64)(n); i++)
template <class T> using min_queue = priority_queue<T, vector<T>, greater<T>>;
template <class T> using max_queue = priority_queue<T>;

// Constant
const double pi = 3.141592653589793238;
const i32 inf32 = 1073741823;
const i64 inf64 = 1LL << 60;
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string abc = "abcdefghijklmnopqrstuvwxyz";
const int MOD = 998244353;
const array<int, 8> dx = {0, 0, -1, 1, -1, -1, 1, 1};
const array<int, 8> dy = {-1, 1, 0, 0, -1, 1, -1, 1};

// Printing
template <class T> void print_collection(ostream &out, T const &x);
template <class T, size_t... I>
void print_tuple(ostream &out, T const &a, index_sequence<I...>);
namespace std {
template <class... A> ostream &operator<<(ostream &out, tuple<A...> const &x) {
    print_tuple(out, x, index_sequence_for<A...>{});
    return out;
}
template <class... A> ostream &operator<<(ostream &out, pair<A...> const &x) {
    print_tuple(out, x, index_sequence_for<A...>{});
    return out;
}
template <class A, size_t N>
ostream &operator<<(ostream &out, array<A, N> const &x) {
    print_collection(out, x);
    return out;
}
template <class A> ostream &operator<<(ostream &out, vector<A> const &x) {
    print_collection(out, x);
    return out;
}
template <class A> ostream &operator<<(ostream &out, deque<A> const &x) {
    print_collection(out, x);
    return out;
}
template <class A> ostream &operator<<(ostream &out, multiset<A> const &x) {
    print_collection(out, x);
    return out;
}
template <class A, class B>
ostream &operator<<(ostream &out, multimap<A, B> const &x) {
    print_collection(out, x);
    return out;
}
template <class A> ostream &operator<<(ostream &out, set<A> const &x) {
    print_collection(out, x);
    return out;
}
template <class A, class B>
ostream &operator<<(ostream &out, map<A, B> const &x) {
    print_collection(out, x);
    return out;
}
template <class A, class B>
ostream &operator<<(ostream &out, unordered_set<A> const &x) {
    print_collection(out, x);
    return out;
}
} // namespace std
template <class T, size_t... I>
void print_tuple(ostream &out, T const &a, index_sequence<I...>) {
    using swallow = int[];
    out << '(';
    (void)swallow{0, (void(out << (I == 0 ? "" : ", ") << get<I>(a)), 0)...};
    out << ')';
}
template <class T> void print_collection(ostream &out, T const &x) {
    int f = 0;
    out << '[';
    for (auto const &i : x) {
        out << (f++ ? "," : "");
        out << i;
    }
    out << "]";
}
// Random
struct RNG {
    uint64_t s[2];
    RNG(u64 seed) { reset(seed); }
    RNG() { reset(time(0)); }
    using result_type = u32;
    static constexpr u32 min() { return numeric_limits<u32>::min(); }
    static constexpr u32 max() { return numeric_limits<u32>::max(); }
    u32 operator()() { return randomInt32(); }
    static __attribute__((always_inline)) inline uint64_t rotl(const uint64_t x,
                                                               int k) {
        return (x << k) | (x >> (64 - k));
    }
    inline void reset(u64 seed) {
        struct splitmix64_state {
            u64 s;
            u64 splitmix64() {
                u64 result = (s += 0x9E3779B97f4A7C15);
                result = (result ^ (result >> 30)) * 0xBF58476D1CE4E5B9;
                result = (result ^ (result >> 27)) * 0x94D049BB133111EB;
                return result ^ (result >> 31);
            }
        };
        splitmix64_state sm{seed};
        s[0] = sm.splitmix64();
        s[1] = sm.splitmix64();
    }
    uint64_t next() {
        const uint64_t s0 = s[0];
        uint64_t s1 = s[1];
        const uint64_t result = rotl(s0 * 5, 7) * 9;
        s1 ^= s0;
        s[0] = rotl(s0, 24) ^ s1 ^ (s1 << 16); // a, b
        s[1] = rotl(s1, 37);                   // c
        return result;
    }
    inline u32 randomInt32() { return next(); }
    inline u64 randomInt64() { return next(); }
    inline u32 random32(u32 r) { return (((u64)randomInt32()) * r) >> 32; }
    inline u64 random64(u64 r) { return randomInt64() % r; }
    inline u32 randomRange32(u32 l, u32 r) { return l + random32(r - l + 1); }
    inline u64 randomRange64(u64 l, u64 r) { return l + random64(r - l + 1); }
    inline double randomDouble() {
        return (double)randomInt32() / 4294967296.0;
    }
    inline double randomDoubleOpen01() {
        return (randomInt32() + 1.0) / 4294967297.0;
    }
    inline float randomFloat() { return (float)randomInt32() / 4294967296.0; }
    inline double randomRangeDouble(double l, double r) {
        return l + randomDouble() * (r - l);
    }
    inline double randomGaussian(double mean = 0.0, double stddev = 1.0) {
        double u1 = randomDoubleOpen01();
        double u2 = randomDouble();
        double z = sqrt(-2.0 * log(u1)) * cos(2.0 * 3.141592653589793238 * u2);
        return mean + stddev * z;
    }
    template <class T> void shuffle(vector<T> &v) {
        i32 sz = v.size();
        for (i32 i = sz; i > 1; i--) {
            i32 p = random32(i);
            swap(v[i - 1], v[p]);
        }
    }
    template <class T> void shuffle(T *fr, T *to) {
        i32 sz = distance(fr, to);
        for (int i = sz; i > 1; i--) {
            int p = random32(i);
            swap(fr[i - 1], fr[p]);
        }
    }
    template <class T> inline int sample_index(vector<T> const &v) {
        return random32(v.size());
    }
    template <class T> inline T sample(vector<T> const &v) {
        return v[sample_index(v)];
    }
} rng;
class FenwickWeightedSampler {
  private:
    int n_ = 0;
    vector<double> bit_;
    vector<double> weight_;
    double total_ = 0.0;

    void add_internal(int idx0, double delta) {
        int i = idx0 + 1;
        while (i <= n_) {
            bit_[i] += delta;
            i += i & -i;
        }
    }

  public:
    // Complexity: O(n)
    void init(int n, double initial_weight = 0.0) {
        n_ = n;
        bit_.assign(n_ + 1, 0.0);
        weight_.assign(n_, initial_weight);
        total_ = 0.0;
        if (initial_weight != 0.0) {
            for (int i = 0; i < n_; i++) {
                add_internal(i, initial_weight);
            }
            total_ = initial_weight * n_;
        }
    }

    // Complexity: O(n log n)
    void build(const vector<double> &weights) {
        init((int)weights.size(), 0.0);
        for (int i = 0; i < n_; i++) {
            weight_[i] = weights[i];
            add_internal(i, weights[i]);
            total_ += weights[i];
        }
    }

    // Complexity: O(log n)
    void set_weight(int idx, double new_weight) {
        assert(0 <= idx && idx < n_);
        const double delta = new_weight - weight_[idx];
        weight_[idx] = new_weight;
        add_internal(idx, delta);
        total_ += delta;
    }

    // Complexity: O(log n)
    void add_weight(int idx, double delta) {
        assert(0 <= idx && idx < n_);
        weight_[idx] += delta;
        add_internal(idx, delta);
        total_ += delta;
    }

    // Complexity: O(log n)
    int sample() const {
        assert(n_ > 0);
        assert(total_ > 0.0);
        const double r = rng.randomDouble() * total_;

        int idx = 0;
        double prefix = 0.0;
        int step = 1;
        while ((step << 1) <= n_)
            step <<= 1;
        for (int k = step; k > 0; k >>= 1) {
            const int nxt = idx + k;
            if (nxt <= n_ && prefix + bit_[nxt] <= r) {
                idx = nxt;
                prefix += bit_[nxt];
            }
        }
        if (idx >= n_)
            idx = n_ - 1;
        return idx;
    }

    int size() const { return n_; }
    double total_weight() const { return total_; }
    double weight(int idx) const {
        assert(0 <= idx && idx < n_);
        return weight_[idx];
    }
};
class AliasWeightedSampler {
  private:
    int n_ = 0;
    vector<double> weight_;
    double total_ = 0.0;
    vector<double> prob_;
    vector<int> alias_;
    bool dirty_ = true;

    // Complexity: O(n)
    void rebuild_alias_table() {
        prob_.assign(n_, 0.0);
        alias_.assign(n_, 0);
        total_ = 0.0;
        for (double w : weight_)
            total_ += w;
        assert(total_ > 0.0);

        vector<double> scaled(n_);
        vector<int> small;
        vector<int> large;
        small.reserve(n_);
        large.reserve(n_);
        for (int i = 0; i < n_; i++) {
            scaled[i] = weight_[i] * n_ / total_;
            if (scaled[i] < 1.0) {
                small.push_back(i);
            } else {
                large.push_back(i);
            }
        }

        while (!small.empty() && !large.empty()) {
            const int s = small.back();
            small.pop_back();
            const int l = large.back();
            large.pop_back();
            prob_[s] = scaled[s];
            alias_[s] = l;
            scaled[l] -= (1.0 - scaled[s]);
            if (scaled[l] < 1.0) {
                small.push_back(l);
            } else {
                large.push_back(l);
            }
        }
        while (!large.empty()) {
            const int i = large.back();
            large.pop_back();
            prob_[i] = 1.0;
            alias_[i] = i;
        }
        while (!small.empty()) {
            const int i = small.back();
            small.pop_back();
            prob_[i] = 1.0;
            alias_[i] = i;
        }
        dirty_ = false;
    }

  public:
    // Complexity: O(n)
    void init(int n, double initial_weight = 0.0) {
        n_ = n;
        weight_.assign(n_, initial_weight);
        total_ = initial_weight * n_;
        prob_.clear();
        alias_.clear();
        dirty_ = true;
    }

    // Complexity: O(n)
    void build(const vector<double> &weights) {
        n_ = (int)weights.size();
        weight_ = weights;
        dirty_ = true;
        // Build lazily on sample() to allow batch updates before first use.
    }

    // Complexity: O(1), table becomes dirty
    void set_weight(int idx, double new_weight) {
        assert(0 <= idx && idx < n_);
        weight_[idx] = new_weight;
        dirty_ = true;
    }

    // Complexity: O(1), table becomes dirty
    void add_weight(int idx, double delta) {
        assert(0 <= idx && idx < n_);
        weight_[idx] += delta;
        dirty_ = true;
    }

    // Complexity: O(1) after table is ready, O(n) if rebuild is needed
    int sample() {
        assert(n_ > 0);
        if (dirty_)
            rebuild_alias_table();
        const int i = (int)rng.random32((uint32_t)n_);
        return (rng.randomDouble() < prob_[i]) ? i : alias_[i];
    }

    int size() const { return n_; }
    double total_weight() {
        if (dirty_)
            rebuild_alias_table();
        return total_;
    }
    double weight(int idx) const {
        assert(0 <= idx && idx < n_);
        return weight_[idx];
    }
};
// Timer
struct Timer {
    chrono::steady_clock::time_point t_begin;
    Timer() { t_begin = chrono::steady_clock::now(); }
    void reset() { t_begin = chrono::steady_clock::now(); }
    float elapsed() const {
        return chrono::duration<float>(chrono::steady_clock::now() - t_begin)
            .count();
    }
} timer;
// Util
template <class T> T &smin(T &x, T const &y) {
    x = min(x, y);
    return x;
}
template <class T> T &smax(T &x, T const &y) {
    x = max(x, y);
    return x;
}
template <typename T> int sgn(T val) {
    if (val < 0)
        return -1;
    if (val > 0)
        return 1;
    return 0;
}
static inline string int_to_string(int val, int digits = 0) {
    string s = to_string(val);
    reverse(begin(s), end(s));
    while ((int)s.size() < digits)
        s.push_back('0');
    reverse(begin(s), end(s));
    return s;
}
// Debug
static inline void debug() { cerr << "\n"; }
template <class T, class... V> void debug(T const &t, V const &...v) {
    if constexpr (DEBUG) {
        cerr << t;
        if (sizeof...(v)) {
            cerr << ", ";
        }
        debug(v...);
    }
}
// Bits
__attribute__((always_inline)) inline u64 bit(u64 x) { return 1ull << x; }
__attribute__((always_inline)) inline void setbit(u64 &a, u32 b,
                                                  u64 value = 1) {
    a = (a & ~bit(b)) | (value << b);
}
__attribute__((always_inline)) inline u64 getbit(u64 a, u32 b) {
    return (a >> b) & 1;
}
__attribute__((always_inline)) inline u64 lsb(u64 a) {
    return __builtin_ctzll(a);
}
__attribute__((always_inline)) inline int msb(uint64_t bb) {
    return __builtin_clzll(bb) ^ 63;
}
struct Init {
    Init() {
        ios::sync_with_stdio(0);
        cin.tie(0);
    }
} init;

// ==========================================
// Input & State
// ==========================================
struct Flight {
    i32 from = -1;
    i32 to = -1;
    i32 dep = -1;
    i32 arr = -1;
};

constexpr i32 START_MIN = 6 * 60;
constexpr i32 END_MIN = 21 * 60;
constexpr i32 STEP_MIN = 5;

struct Input {
    i32 N = 0, R = 0, M = 0, K = 0;
    vector<i32> x, y;
    vector<i64> w;
    vector<Flight> sq_flights;

    static i32 parse_time(string const &s) {
        i32 hh = stoi(s.substr(0, 2));
        i32 mm = stoi(s.substr(3, 2));
        return hh * 60 + mm;
    }

    void input() {
        string head;
        cin >> head;
        if (!head.empty() && (unsigned char)head[0] == 0xEF) {
            if (head.size() >= 3 && (unsigned char)head[1] == 0xBB &&
                (unsigned char)head[2] == 0xBF) {
                head = head.substr(3);
            }
        }
        N = stoi(head);
        cin >> R;
        x.resize(N);
        y.resize(N);
        w.resize(N);
        rep(i, N) { cin >> x[i] >> y[i] >> w[i]; }

        cin >> M;
        sq_flights.resize(M);
        rep(i, M) {
            i32 a, b;
            string s, t;
            cin >> a >> s >> b >> t;
            --a;
            --b;
            sq_flights[i] = Flight{a, b, parse_time(s), parse_time(t)};
        }
        cin >> K;
    }
} in;

// ==========================================
// Solver
// ==========================================
class Solver {
    struct PairInfo {
        i16 src = -1;
        i16 dst = -1;
        i64 gain = 0;
    };

    vector<i32> targets;
    vector<vector<i32>> duration;
    vector<PairInfo> pair_infos;
    vector<vector<Flight>> best_plan;
    double best_share = -1.0;
    vector<i16> dp_sq_flat;
    vector<i16> dp_ci_flat;
    __int128 total_gain_all = 0;

    inline i32 dp_index(i32 dest, i32 k, i32 src) const {
        return (dest * (i32)targets.size() + k) * in.N + src;
    }

    static string format_time(i32 m) {
        i32 hh = m / 60;
        i32 mm = m % 60;
        string res = int_to_string(hh, 2) + ":" + int_to_string(mm, 2);
        return res;
    }

    static i32 flight_duration_min(double d) {
        double raw = 60.0 * d / 800.0 + 40.0;
        i32 v = (i32)ceil(raw / 5.0) * 5;
        return v;
    }

    static void sort_desc_inplace(vector<Flight> &flights) {
        sort(all(flights), [](Flight const &l, Flight const &r) {
            if (l.dep != r.dep)
                return l.dep > r.dep;
            return l.arr > r.arr;
        });
    }

    void compute_all_dp_flat_sorted(vector<Flight> const &flights_sorted,
                                    vector<i16> &out_dp) {
        i32 N = in.N;
        i32 TK = (i32)targets.size();
        out_dp.assign(N * TK * N, -1);

        rep(dest, N) {
            rep(k, TK) {
                i16 *cur = out_dp.data() + dp_index((i32)dest, (i32)k, 0);
                cur[dest] = (i16)targets[k];
                for (auto const &e : flights_sorted) {
                    if (cur[e.to] >= e.arr && e.dep > cur[e.from]) {
                        cur[e.from] = (i16)e.dep;
                    }
                }
            }
        }
    }

    double evaluate_share(vector<vector<Flight>> const &plan) {
        vector<Flight> ci;
        ci.reserve(512);
        for (auto const &vec : plan) {
            for (auto const &f : vec)
                ci.push_back(f);
        }
        sort_desc_inplace(ci);
        compute_all_dp_flat_sorted(ci, dp_ci_flat);

        __int128 v_ci = 0;
        for (auto const &pi : pair_infos) {
            __int128 gain = (__int128)pi.gain;
            rep(k, targets.size()) {
                i16 s_sq = dp_sq_flat[dp_index(pi.dst, (i32)k, pi.src)];
                i16 s_ci = dp_ci_flat[dp_index(pi.dst, (i32)k, pi.src)];
                if (s_sq < s_ci)
                    v_ci += gain;
            }
        }
        if (total_gain_all == 0)
            return 0.0;
        return (double)v_ci / (double)total_gain_all;
    }

    vector<vector<Flight>> build_random_plan() {
        i32 N = in.N;
        i32 K = in.K;
        vector<vector<Flight>> plan(K);

        rep(p, K) {
            i32 cur_city = rng.random32(N);
            i32 cur_time = START_MIN;
            plan[p].reserve(16);
            while (true) {
                i32 dst = rng.random32(N - 1);
                if (dst >= cur_city)
                    ++dst;

                i32 dur = duration[cur_city][dst];
                i32 dep = cur_time; // 到着後は即時出発
                i32 arr = dep + dur;
                if (arr > END_MIN)
                    break;
                plan[p].push_back(Flight{cur_city, dst, dep, arr});
                cur_city = dst;
                cur_time = arr;
            }
        }
        return plan;
    }

  public:
    Solver() {}
    void solve() {
        i32 N = in.N;
        i32 R = in.R;

        for (i32 t = 11 * 60; t <= 21 * 60; t += 30)
            targets.push_back(t);

        duration.assign(N, vector<i32>(N, 0));
        rep(i, N) {
            rep(j, N) {
                if (i == j)
                    continue;
                double ddx = (double)in.x[i] - (double)in.x[j];
                double ddy = (double)in.y[i] - (double)in.y[j];
                double dist = sqrt(ddx * ddx + ddy * ddy);
                duration[i][j] = flight_duration_min(dist);
                if (dist >= 0.25 * (double)R) {
                    pair_infos.push_back(PairInfo{(i16)i, (i16)j,
                                                  in.w[i] * in.w[j]});
                }
            }
        }
        total_gain_all = 0;
        for (auto const &pi : pair_infos) {
            total_gain_all += (__int128)pi.gain * (__int128)targets.size();
        }

        vector<Flight> sq_sorted = in.sq_flights;
        sort_desc_inplace(sq_sorted);
        compute_all_dp_flat_sorted(sq_sorted, dp_sq_flat);
        dp_ci_flat.resize(N * (i32)targets.size() * N, -1);

        best_plan.assign(in.K, {});
        Timer local_timer;
        i64 iterations = 0;
        while (local_timer.elapsed() < 1.0f) {
            ++iterations;
            auto plan = build_random_plan();
            double share = evaluate_share(plan);
            if (share > best_share) {
                double old_share = best_share;
                i64 old_score =
                    (old_share < 0.0) ? -1 : (i64)floor(1000000.0 * old_share);
                i64 new_score = (i64)floor(1000000.0 * share);
                cerr << fixed << setprecision(6)
                     << "improved: score " << old_score << " -> " << new_score
                     << ", share " << old_share << " -> " << share
                     << ", iter " << iterations << ", elapsed "
                     << local_timer.elapsed() << "s" << el;
                best_share = share;
                best_plan = move(plan);
            }
        }
        cerr << "total_iterations: " << iterations << el;
    }
    void print() {
        rep(p, in.K) {
            cout << best_plan[p].size() << el;
            for (auto const &f : best_plan[p]) {
                cout << (f.from + 1) << ' ' << format_time(f.dep) << ' '
                     << (f.to + 1) << ' ' << format_time(f.arr) << el;
            }
        }
    }
};

int main() {
    in.input();
    Solver solver;
    solver.solve();
    solver.print();

    // 高速に終了する
    cout.flush();
    cerr.flush();
    _Exit(0);
}