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

• 問題: No.5023 Airlines Optimization
• ユーザー: twins_fuyu
• 提出日時: 2026-02-25 23:14:04
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 220 ms / 1,000 ms
• コード長: 10,982 bytes
• コンパイル時間: 7,295 ms
• コンパイル使用メモリ: 491,432 KB
• 実行使用メモリ: 7,848 KB
• スコア: 39,656,609
• 最終ジャッジ日時: 2026-02-25 23:14:36
• 合計ジャッジ時間: 29,521 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

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

ソースコード

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "immintrin.h"
using namespace std;
#define rep1(a) for (int _ = 0; _ < (a); ++_)
#define rep2(i, a) for (int i = 0; i < (a); ++i)
#define rep3(i, a, b) for (int i = a; i < (b); ++i)
#define rrep1(a) for (int i = (a) - 1; i >= 0; --i)
#define rrep2(i, a) for (int i = (a) - 1; i >= 0; --i)
#define rrep3(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define overload3(a, b, c, d, ...) d
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(...) overload3(__VA_ARGS__, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define in(i, vec) for (auto i : (vec))
template <class T>
using pqueue = priority_queue<T, vector<T>>; // 大きい順
template <class T>
using pqueue_g = priority_queue<T, vector<T>, greater<T>>; // 小さい順

namespace library
{
    class xorshift128plus
    {
    private:
        uint64_t s[2];

    public:
        using result_type = uint64_t;

        xorshift128plus(uint64_t seed = 1)
        {
            seed_gen(seed);
        }

        void seed(uint64_t seed_val)
        {
            seed_gen(seed_val);
        }

        static constexpr result_type min()
        {
            return std::numeric_limits<result_type>::min();
        }

        static constexpr result_type max()
        {
            return std::numeric_limits<result_type>::max();
        }

        result_type operator()()
        {
            uint64_t s1 = s[0];
            uint64_t s0 = s[1];
            s[0] = s0;
            s1 ^= s1 << 23;
            s[1] = s1 ^ s0 ^ (s1 >> 17) ^ (s0 >> 26);
            return s[1] + s0;
        }

    private:
        void seed_gen(uint64_t seed_val)
        {
            // SplitMix64 で状態2個を初期化
            s[0] = splitmix64(seed_val);
            s[1] = splitmix64(s[0]);
        }

        static uint64_t splitmix64(uint64_t &x)
        {
            x += 0x9E3779B97F4A7C15ULL;
            uint64_t z = x;
            z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9ULL;
            z = (z ^ (z >> 27)) * 0x94D049BB133111EBULL;
            return z ^ (z >> 31);
        }
    };

    struct Timer
    {
        chrono::steady_clock::time_point start;
        Timer() : start(chrono::steady_clock::now()) {}
        double elapse()
        {
            return chrono::duration<double>(chrono::steady_clock::now() - start).count();
        }
        bool over(double t)
        {
            return elapse() > t;
        }
        bool operator()(double t)
        {
            return elapse() < t;
        }
    };

    void fast_io()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }

    uint64_t exp_table[2001];

    bool init_exp_table(){
        for(int i=0;i<=2000;++i){
            exp_table[i]=numeric_limits<uint64_t>::max()*exp(double(-i)/100.0);
        }
        return true;
    }
    bool exp_table_initialized = init_exp_table();

    uint64_t sa_exp(double diff, double temperature){
        if(temperature==0) return 0;
        else if (diff>=0) return numeric_limits<uint64_t>::max();
        int index = int(-diff * 100.0 / temperature);
        if(index>2000) return 0;
        return exp_table[index];
    }

} // namespace library

uniform_real_distribution<double> rnd(0.0, 1.0);
normal_distribution<double> randn(0.0, 1.0);
library::xorshift128plus rng(12345);
library::Timer timer;
double TL = 1.9;

constexpr int N = 47;
constexpr int M = 400;
constexpr int R = 1000;
long long W[N];
int DIST[N][N];
bool near[N][N];

vector<tuple<int,int,int,int>> querys;

struct State{
    vector<tuple<int,int,int>> G[N]; // goal -> (start, start_time, goal_time)

    void sort_g(){
        rep(i,N){
            sort(G[i].begin(), G[i].end(), [](const auto& a, const auto& b){
                return get<2>(a) < get<2>(b);
            });
        }
    }

    int query(int start, int goal, int goal_time) const{
        // 逆向きダイクストラ
        bool vis[N] = {};
        vis[goal] = true;
        pqueue<tuple<int,int>> pq;
        for(auto [prv,st,gt]:G[goal]){
            if(gt > goal_time) break;
            pq.emplace(st, prv);
        }
        while(!pq.empty()){
            auto [cur_time, cur] = pq.top(); pq.pop();
            if(cur == start) return cur_time;
            if(vis[cur]) continue;
            vis[cur] = true;
            for(auto [prv, st, gt]:G[cur]){
                if(gt > cur_time) break;
                if(vis[prv]) continue;
                pq.emplace(st, prv);
            }
        }
        return -1;
    }
};

State SQUARE;


constexpr int K = 25;

int get_time(int d_squared){
    double d = sqrt(d_squared);
    long long m = max(0.0 ,(3*d) / 200 - 1);
    long long d_squared_ll = d_squared;
    while ((200*m)*(200*m) < 9*d_squared_ll) {
        m += 1;
    }
    return 40 + 5*m;
}

int parse(const string& s){
    // s 06:00 ~ 21:00
    int hour = stoi(s.substr(0, 2));
    int minute = stoi(s.substr(3, 2));
    return (hour - 6) * 60 + minute;
}
string format_time(int t){
    int hour = 6 + t / 60;
    int minute = t % 60;
    string res;
    if(hour < 10) res += "0";
    res += to_string(hour) + ":";
    if(minute < 10) res += "0";
    res += to_string(minute);
    return res;
}

void get_input(){
    int n,r; cin>>n>>r;
    assert(n==N && r==R);
    pair<int,int> xy[N];
    rep(i,N){
        int x,y,w; cin>>x>>y>>w;
        xy[i] = {x,y};
        W[i] = w;
    }
    rep(i,N)DIST[i][i] = 0, near[i][i] = true;
    rep(i,N)rep(j,i+1,N){
        int dx = xy[i].first - xy[j].first;
        int dy = xy[i].second - xy[j].second;
        DIST[i][j] = get_time(dx*dx + dy*dy);
        DIST[j][i] = DIST[i][j];
        near[i][j] = (16*(dx*dx + dy*dy) < R*R) ? true : false;
    }
    int m; cin>>m;
    assert(m==M);
    rep(i,M){
        int a,b;
        string s,t;
        cin >> a >> s >> b >> t;
        a--; b--;
        SQUARE.G[b].emplace_back(a, parse(s), parse(t));
    }
    SQUARE.sort_g();

    for(int goal_time = 300; goal_time <= 900; goal_time += 30){
        for(int start = 0; start < N; ++start){
            for(int goal = 0; goal < N; ++goal){
                if(start == goal) continue;
                if(near[start][goal])continue;
                int start_time = SQUARE.query(start, goal, goal_time);
                querys.emplace_back(start, goal, goal_time, start_time);
            }
        }
    }
}

double get_score(const State& state){
    long long w_player = 0;
    long long w_opponent = 0;
    for(auto [start, goal, goal_time, start_time]:querys){
        int query_time = state.query(start, goal, goal_time);
        if(start_time < query_time) w_player += W[start]*W[goal];
        else w_opponent += W[start]*W[goal];
    }
    cerr << "w_player: " << w_player << ", w_opponent: " << w_opponent << endl;
    return w_player / double(w_player + w_opponent);
}

struct AirLine{
    int start;
    vector<int> goals;
    vector<int> goal_times;

    AirLine(int start):start(start){}

    void add_goal(int goal, int goal_time){
        int last_goal_time = goal_times.empty() ? 0 : goal_times.back();
        int start_time = last_goal_time + DIST[start][goal];
        assert(last_goal_time <= start_time);
        goals.push_back(goal);
        goal_times.push_back(goal_time);
    }
};

double get_score_from_airlines(const vector<AirLine>& airlines){
    State state;
    for(const auto& airline: airlines){
        int start = airline.start;
        for(size_t i=0;i<airline.goals.size();++i){
            int goal = airline.goals[i];
            int goal_time = airline.goal_times[i];
            int start_time = goal_time - DIST[start][goal];
            state.G[goal].emplace_back(start, start_time, goal_time);
            start = goal;
        }
    }
    state.sort_g();
    return get_score(state);
}

int main(){
    library::fast_io();
    get_input();

    vector<AirLine> airlines;
    rep(i,K){
        int cur_time = 0;
        int target = i + 1;
        airlines.emplace_back(target);
        int dist = DIST[0][target];
        rep(itr,100){
            int nxt_time = cur_time + dist;
            if(nxt_time > 900) break;
            int to = itr%2 ? target : 0;
            airlines[i].add_goal(to, nxt_time);
            cur_time = nxt_time; 
        }
    }
    // rep(i,4,25){
    //     int cur_time = 0;
    //     int target1 = (i-4)*2 + 5;
    //     int target2 = (i-4)*2 + 6;
    //     int dist1 = DIST[0][target1];
    //     int dist2 = DIST[0][target2];
    //     airlines.emplace_back(target1);
    //     rep(itr,100){
    //         int phase = itr % 4;
    //         if(phase == 0){
    //             int nxt_time = cur_time + dist1;
    //             if(nxt_time > 900) break;
    //             airlines[i].add_goal(0, nxt_time);
    //             cur_time = nxt_time; 
    //         }
    //         else if(phase == 1){
    //             int nxt_time = cur_time + dist2;
    //             if(nxt_time > 900) break;
    //             airlines[i].add_goal(target2, nxt_time);
    //             cur_time = nxt_time; 
    //         }
    //         else if(phase == 2){
    //             int nxt_time = cur_time + dist2;
    //             if(nxt_time > 900) break;
    //             airlines[i].add_goal(0, nxt_time);
    //             cur_time = nxt_time; 
    //         }
    //         else{
    //             int nxt_time = cur_time + dist1;
    //             if(nxt_time > 900) break;
    //             airlines[i].add_goal(target1, nxt_time);
    //             cur_time = nxt_time;
    //         }
    //     }
    // }

    // output
    for(const auto& airline: airlines){
        cout << airline.goals.size() << endl;
        rep(i,airline.goals.size()){
            int start = (i == 0) ? airline.start : airline.goals[i-1];
            int goal = airline.goals[i];
            int goal_time = airline.goal_times[i];
            int start_time = goal_time - DIST[start][goal];
            cout << start + 1 << " " << format_time(start_time) << " " << goal + 1 << " " << format_time(goal_time) << endl;
        }
    }

    State state;
    for(const auto& airline: airlines){
        int start = airline.start;
        for(size_t i=0;i<airline.goals.size();++i){
            int goal = airline.goals[i];
            int goal_time = airline.goal_times[i];
            int start_time = goal_time - DIST[start][goal];
            state.G[goal].emplace_back(start, start_time, goal_time);
            start = goal;
        }
    }
    state.sort_g();

    for(auto [start, goal, goal_time, start_time]:querys){
        int query_time = state.query(start, goal, goal_time);
        if(start == 15 && goal == 0){
            cerr << "Query: " << start << " -> " << goal << " at " << format_time(goal_time) << ", start_time: " << format_time(start_time) << ", query_time: " << format_time(query_time) << endl;
        }
    }
    cerr << "Score: " << get_score_from_airlines(airlines) << endl;

    
    return 0;
}