#1149421 (C++17(clang)) No.5023 Airlines Optimization

• 問題: No.5023 Airlines Optimization
• ユーザー: Pechi
• 提出日時: 2026-02-25 23:53:43
• 言語: C++17(clang) (clang++ 21.1.8 + boost 1.89.0)
• 結果: AC
• 実行時間: 956 ms / 1,000 ms
• コード長: 9,374 bytes
• コンパイル時間: 6,179 ms
• コンパイル使用メモリ: 196,000 KB
• 実行使用メモリ: 7,848 KB
• スコア: 47,960,643
• 最終ジャッジ日時: 2026-02-25 23:55:33
• 合計ジャッジ時間: 106,721 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

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

ソースコード

#define _USE_MATH_DEFINES
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;

#ifdef _MSC_VER
inline unsigned long long __builtin_ctzll(unsigned long long x) { unsigned long r; _BitScanForward64(&r, x); return r; }
inline unsigned long long __builtin_clzll(unsigned long long x) { unsigned long r; _BitScanReverse64(&r, x); return 63 - r; }
inline unsigned long long __builtin_ffsll(unsigned long long x) { unsigned long r; return _BitScanForward64(&r, x) ? r + 1 : 0; }
inline unsigned long long __builtin_popcountll(unsigned long long x) { return __popcnt64(x); }
#endif // _MSC_VER

#define LP(I,S,G) for (long long int I = (S); I < (G); ++I)
#define IN(X) 	for (int in = 0; in < X.size(); in++)cin >> X[in]
#define OUT(X) 	for (int in = 0; in < X.size(); in++)cout << X[in]<<" "
#define SORT(X) sort((X).begin(), (X).end())
#define CSORT(X,Y) sort(X.begin(), X.end(),Y)
#define COPY(X,Y) copy(X.begin(), X.end(), Y.begin())
#define ALL(X,Y) for (auto (X) :(Y))
#define FULL(a)  (a).begin(),(a).end()
#define BFS(Q,S) for(Q.push(S);Q.size()!=0;Q.pop())
typedef long long int ll;
typedef unsigned long long int ull;
long long int M = 998244353;

chrono::system_clock::time_point starttime;
using namespace std::chrono;
using namespace atcoder;
#ifndef ONLINE_JUDGE
#define DEBUG
#endif

inline float getTime() {
#ifdef DEBUG
    return duration_cast<milliseconds>(system_clock::now() - starttime).count() / 2;
#else
    return duration_cast<milliseconds>(system_clock::now() - starttime).count();
#endif
}


int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 };
inline long long int xor128() {
    static long long int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    long long int t = (x ^ (x << 11));
    x = y; y = z; z = w;
    return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}


mt19937_64 rnd;
struct Solver {
    int n, r, m, k;
    int plan_size = 10;
    vector<ll> x, y, w;
    vector<vector<array<int, 3>>> g;
    vector<vector<int>> dist, mask;
    vector<vector<array<int, 21>>> time_sq, time_ci;
    vector<vector<array<int, 4>>> plan;

    string convert(int t) {
        string a = to_string(t / 12 + 6);
        if (a.size() == 1)a = "0" + a;
        string b = to_string((t % 12) * 5);
        if (b.size() == 1)b = "0" + b;
        return a + ":" + b;
    }

    int convert(string s) {
        int a = stoi(string(s.begin(), s.begin() + 2)) - 6;
        int b = stoi(string(s.begin() + 3, s.end())) / 5;
        return a * 12 + b;
    }


    Solver() {
        cin >> n >> r;
        g = vector<vector<array<int, 3>>>(n);
        x = vector<ll>(n);
        y = vector<ll>(n);
        w = vector<ll>(n);
        for (int i = 0; i < n; ++i)cin >> x[i] >> y[i] >> w[i];
        cin >> m;
        for (int i = 0; i < m; ++i) {
            int a, b;
            string s, t;
            cin >> a >> s >> b >> t;
            --a, --b;
            g[a].push_back({ convert(s),b,convert(t) });
        }
        cin >> k;
        init_dist();
        init_time();
    }

    void init_dist() {
        dist = vector<vector<int>>(n, vector<int>(n));
        mask = vector<vector<int>>(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                double d = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
                mask[i][j] = (d >= 0.25 * r);
                dist[i][j] = ((int)ceil(3 * d / 40 + 40) + 4) / 5;
            }
        }
    }

    void init_time() {
        int p = 21;
        time_sq = vector<vector<array<int, 21>>>(n, vector<array<int, 21>>(n));
        time_ci = vector<vector<array<int, 21>>>(n, vector<array<int, 21>>(n));
        for (int v = 0; v < n; ++v) {
            for (int u = 0; u < n; ++u) {
                for (int i = 0; i < p; ++i) time_sq[v][u][i] = INT_MIN;
            }
        }
        int deadline[21];
        for (int i = 0; i < p; ++i) deadline[i] = convert("11:00") + 6 * i;
        vector<array<int, 4>> flights;
        for (int a = 0; a < n; ++a) {
            for (int i = 0; i < g[a].size(); ++i) {
                flights.push_back({ g[a][i][0], a, g[a][i][1], g[a][i][2] });
            }
        }
        sort(flights.begin(), flights.end(), greater<array<int, 4>>());
        static int dp[47][21];
        for (int to = 0; to < n; ++to) {
            for (int u = 0; u < n; ++u) {
                for (int i = 0; i < p; ++i) dp[u][i] = INT_MIN;
            }
            for (int i = 0; i < p; ++i) dp[to][i] = deadline[i];
            for (int i = 0; i < flights.size(); ++i) {
                int s = flights[i][0];
                int a = flights[i][1];
                int b = flights[i][2];
                int t = flights[i][3];
                for (int j = 0; j < p; ++j) {
                    if (dp[b][j] >= t && dp[a][j] < s) {
                        dp[a][j] = s;
                    }
                }
            }
            for (int from = 0; from < n; ++from) {
                for (int i = 0; i < p; ++i) {
                    time_sq[from][to][i] = dp[from][i];
                }
            }
        }
    }

    void update_time() {
        int p = 21;
        for (int v = 0; v < n; ++v) {
            for (int u = 0; u < n; ++u) {
                for (int i = 0; i < p; ++i) time_ci[v][u][i] = INT_MIN;
            }
        }
        int deadline[21];
        for (int i = 0; i < p; ++i) deadline[i] = convert("11:00") + 6 * i;
        vector<array<int, 4>> flights;
        for (int i = 0; i < k; ++i) {
            for (int j = 0; j < plan[i].size(); ++j) {
                flights.push_back({ plan[i][j][1],plan[i][j][0] ,plan[i][j][2] ,plan[i][j][3] });
            }
        }
        sort(flights.begin(), flights.end(), greater<array<int, 4>>());
        static int dp[47][21];
        for (int to = 0; to < n; ++to) {
            for (int u = 0; u < n; ++u) {
                for (int i = 0; i < p; ++i) dp[u][i] = INT_MIN;
            }
            for (int i = 0; i < p; ++i) dp[to][i] = deadline[i];
            for (int i = 0; i < flights.size(); ++i) {
                int s = flights[i][0];
                int a = flights[i][1];
                int b = flights[i][2];
                int t = flights[i][3];
                for (int j = 0; j < p; ++j) {
                    if (dp[b][j] >= t && dp[a][j] < s) {
                        dp[a][j] = s;
                    }
                }
            }
            for (int from = 0; from < n; ++from) {
                for (int i = 0; i < p; ++i) {
                    time_ci[from][to][i] = dp[from][i];
                }
            }
        }
    }

    double calc_score() {
        update_time();
        ll score_sq = 0, score_ci = 0;
        for (int u = 0; u < n; ++u) {
            for (int v = 0; v < n; ++v) {
                if (mask[u][v]) {
                    for (int i = 0; i < 21; ++i) {
                        if (time_sq[u][v][i] < time_ci[u][v][i]) score_ci += w[u] * w[v];
                        else score_sq += w[u] * w[v];
                    }
                }
            }
        }
        return (double)(score_ci) / (score_sq + score_ci);
    }


    vector<array<int, 4>> make_plan(int u,int v,int c,int base) {
        deque<array<int, 4>> q;
        int now = base;
        int end = 180;
        int idx = 0;
        vector<int> route = { c,u,v };
        while (now < end) {
            int n_idx = (idx + 1) % 3;
            int next = now + dist[route[idx]][route[n_idx]];
            if (next >= end)break;
            q.push_back({ route[idx],now,route[n_idx],next });
            now = next;
            idx = n_idx;
        }
        now = base;
        idx = 0;
        while (now > 0) {
            int n_idx = (idx + 2) % 3;
            int next = now - dist[route[idx]][route[n_idx]];
            if (next < 0)break;
            q.push_front({ route[n_idx] ,next,route[idx],now });
            now = next;
            idx = n_idx;
        }
        return vector<array<int, 4>>(q.begin(), q.end());
    }



    void solve() {
        for (int i = 0; i < k; ++i) {
            int u = i + 12;
            int v = i % 11 + 1;
            int c = 0;
            plan.push_back(make_plan(u, v, c, convert("11:00")));
        }
        double now_score = calc_score();
        cerr << now_score << "\n";
        while (getTime() <= 950) {
            int idx = xor128() % k;
            vector<array<int, 4>> backup;
            swap(backup, plan[idx]);
            plan[idx] = make_plan(xor128() % 46 + 1, xor128() % 46 + 1, 0, convert("11:00"));
            double new_score = calc_score();
            if (now_score < new_score) {
                now_score = new_score;
            }
            else {
                swap(backup, plan[idx]);
            }
        }
        cerr << now_score << "\n";
    }

    void answer() {
        for (int i = 0; i < k; ++i) {
            cout << plan[i].size() << "\n";
            for (auto act : plan[i]) {
                cout << act[0] + 1 << " " << convert(act[1]) << " " << act[2] + 1 << " " << convert(act[3]) << "\n";
            }
        }
    }

};

int main(int argc, char* argv[]) {
    starttime = chrono::system_clock::now();
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    Solver s;
    s.solve();
    s.answer();
    exit(0);
}