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

• 問題: No.5023 Airlines Optimization
• ユーザー: ぴぃいいいい
• 提出日時: 2026-03-01 01:42:47
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 17,618 bytes
• コンパイル時間: 5,660 ms
• コンパイル使用メモリ: 376,464 KB
• 実行使用メモリ: 9,856 KB
• スコア: 58,067,996
• 最終ジャッジ日時: 2026-03-01 01:44:25
• 合計ジャッジ時間: 95,984 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
other	AC * 98 TLE * 2

ソースコード

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

static constexpr int DL = 21;     // deadlines count
static constexpr int T  = 181;    // 06:00..21:00 in 5-min steps (inclusive)
static constexpr int CH0 = 16, CH1 = 16, CH2 = 15;

struct Edge {
    uint8_t to;
    uint8_t arr;
};

struct PlanFlight {
    int from, dep, to, arr;
};

static inline int parse_time_idx(const string& s) {
    int hh = (s[0]-'0')*10 + (s[1]-'0');
    int mm = (s[3]-'0')*10 + (s[4]-'0');
    int minutes = hh*60 + mm;
    return (minutes - 360) / 5; // 06:00=360
}

static inline string fmt_time_idx(int idx) {
    int minutes = 360 + idx*5;
    int hh = minutes / 60;
    int mm = minutes % 60;
    ostringstream oss;
    oss << setw(2) << setfill('0') << hh << ":" << setw(2) << setfill('0') << mm;
    return oss.str();
}

// duration in 5-min steps: ceil((40 + 60*d/800)/5)
static inline int calc_dur_steps(long double dx, long double dy) {
    long double d = sqrtl(dx*dx + dy*dy);
    long double raw = 40.0L + (60.0L * d) / 800.0L;
    long double v = raw / 5.0L;
    int steps = (int)ceill(v - 1e-12L);
    return max(0, steps);
}

// --------- 47-bit weight sum by chunk lookup ----------
struct WeightSum47 {
    vector<long long> sum0, sum1, sum2; // 2^16,2^16,2^15
    vector<long long> w;

    explicit WeightSum47(const vector<long long>& w_) : w(w_) {
        sum0.assign(1u<<CH0, 0);
        sum1.assign(1u<<CH1, 0);
        sum2.assign(1u<<CH2, 0);

        for (uint32_t m = 1; m < (1u<<CH0); m++) {
            uint32_t lsb = m & -m;
            uint32_t pm  = m ^ lsb;
            int b = __builtin_ctz(lsb);
            sum0[m] = sum0[pm] + w[b];
        }
        for (uint32_t m = 1; m < (1u<<CH1); m++) {
            uint32_t lsb = m & -m;
            uint32_t pm  = m ^ lsb;
            int b = __builtin_ctz(lsb);
            sum1[m] = sum1[pm] + w[CH0 + b];
        }
        for (uint32_t m = 1; m < (1u<<CH2); m++) {
            uint32_t lsb = m & -m;
            uint32_t pm  = m ^ lsb;
            int b = __builtin_ctz(lsb);
            sum2[m] = sum2[pm] + w[CH0 + CH1 + b];
        }
    }

    inline long long sum(uint64_t mask47) const {
        uint32_t m0 = (uint32_t)(mask47 & 0xFFFFULL);
        uint32_t m1 = (uint32_t)((mask47 >> 16) & 0xFFFFULL);
        uint32_t m2 = (uint32_t)((mask47 >> 32) & 0x7FFFULL);
        return sum0[m0] + sum1[m1] + sum2[m2];
    }
};

// --------- compute square latest depart (forward DP, from scratch) ----------
static void compute_latest_all_origins(
    int N,
    const vector<vector<Edge>>& outFlights, // size nodes = N*T
    vector<int16_t>& latest                 // size N*nodes
) {
    int nodes = N * T;
    latest.assign(N * nodes, (int16_t)-1);

    for (int o = 0; o < N; o++) {
        int16_t* dp = latest.data() + o * nodes;
        // can "start" at origin at any time t with departure time t
        for (int t = 0; t < T; t++) dp[o*T + t] = (int16_t)t;

        for (int t = 0; t < T; t++) {
            for (int c = 0; c < N; c++) {
                int node = c*T + t;
                int16_t val = dp[node];
                if (val < 0) continue;

                // wait
                if (t+1 < T) {
                    int node2 = node + 1; // same city, next time
                    if (val > dp[node2]) dp[node2] = val;
                }

                // flights
                for (const auto& e : outFlights[node]) {
                    int node3 = (int)e.to * T + (int)e.arr;
                    if (val > dp[node3]) dp[node3] = val;
                }
            }
        }
    }
}

// --------- incremental update for circle latest depart (difference update) ----------
static void relax_add_flights_incremental(
    int N,
    vector<vector<Edge>>& outCi,        // updated adjacency
    vector<int16_t>& ciLatest,          // size N*nodes, updated in-place
    const vector<PlanFlight>& added     // flights just added (for init relax)
) {
    int nodes = N * T;

    // queue buffers reused per origin (no reallocation inside loops)
    vector<int> q(nodes);
    vector<uint8_t> inq(nodes);

    for (int o = 0; o < N; o++) {
        int16_t* dp = ciLatest.data() + o * nodes;
        fill(inq.begin(), inq.end(), 0);
        int qh = 0, qt = 0;

        // initial relax only at the newly added edges
        for (const auto& f : added) {
            int fromNode = f.from*T + f.dep;
            int toNode   = f.to*T   + f.arr;
            int16_t val = dp[fromNode];
            if (val > dp[toNode]) {
                dp[toNode] = val;
                if (!inq[toNode]) {
                    inq[toNode] = 1;
                    q[qt++] = toNode;
                }
            }
        }

        // propagate improvements forward in time via wait + existing flights
        while (qh < qt) {
            int node = q[qh++];
            inq[node] = 0;

            int c = node / T;
            int t = node % T;
            int16_t val = dp[node];

            // wait
            if (t+1 < T) {
                int node2 = node + 1;
                if (val > dp[node2]) {
                    dp[node2] = val;
                    if (!inq[node2]) {
                        inq[node2] = 1;
                        q[qt++] = node2;
                    }
                }
            }

            // flights
            for (const auto& e : outCi[node]) {
                int node3 = (int)e.to * T + (int)e.arr;
                if (val > dp[node3]) {
                    dp[node3] = val;
                    if (!inq[node3]) {
                        inq[node3] = 1;
                        q[qt++] = node3;
                    }
                }
            }
        }
    }
}

// --------- reachDest[node][k] : destinations reachable from node by deadline[k] (including transfers) ----------
static void compute_reach_dest(
    int N,
    const array<int,DL>& deadlines,
    const vector<vector<Edge>>& outCi,      // circle schedule flights
    vector<uint64_t>& reachDest             // size nodes*DL
) {
    int nodes = N * T;
    reachDest.assign((size_t)nodes * DL, 0);

    vector<uint64_t> tmp(nodes, 0); // reused per deadline

    for (int k = 0; k < DL; k++) {
        int lim = deadlines[k];
        fill(tmp.begin(), tmp.end(), 0);

        for (int t = lim; t >= 0; --t) {
            for (int c = 0; c < N; c++) {
                int node = c*T + t;
                uint64_t val = 0;

                // wait
                if (t < lim) val |= tmp[node + 1];

                // stay => can reach destination "c" by deadline
                val |= (1ULL << c);

                // flights
                for (const auto& e : outCi[node]) {
                    if ((int)e.arr <= lim) {
                        int node2 = (int)e.to * T + (int)e.arr;
                        val |= tmp[node2];
                    }
                }

                tmp[node] = val;
            }
        }

        // store for all nodes (t<=lim); others remain 0
        for (int c = 0; c < N; c++) {
            for (int t = 0; t <= lim; t++) {
                int node = c*T + t;
                reachDest[(size_t)node * DL + k] = tmp[node];
            }
        }
    }
}

// --------- GoodDest[(o,cand),k] : destinations d where (ci<=sq) AND (sq < cand) AND eligible(o,d) ----------
static void compute_good_dest(
    int N,
    const array<int,DL>& deadlines,
    const vector<char>& eligibleOD,          // size N*N
    const vector<int16_t>& ciLatest,         // size N*nodes
    const vector<int16_t>& sqDeadline,       // size (N*N*DL)
    vector<uint64_t>& goodDest               // size (N*T*DL), index ((o*T+cand)*DL + k)
) {
    int nodes = N * T;
    goodDest.assign((size_t)N * T * DL, 0);

    // local bucket (on stack) to avoid heap alloc
    array<uint64_t, T> adds;

    for (int o = 0; o < N; o++) {
        const int16_t* dp = ciLatest.data() + o * nodes;

        for (int k = 0; k < DL; k++) {
            adds.fill(0);
            uint64_t base = 0;

            int limT = deadlines[k];

            for (int d = 0; d < N; d++) {
                if (d == o) continue;
                int od = o*N + d;
                if (!eligibleOD[od]) continue;

                int16_t ci = dp[d*T + limT];
                int16_t sq = sqDeadline[(od*DL) + k];

                // losing or tie: ci <= sq
                if (ci <= sq) {
                    if (sq < 0) {
                        base |= (1ULL << d);
                    } else {
                        int idx = (int)sq + 1; // include when cand >= sq+1  <=> sq < cand
                        if (idx < T) adds[idx] |= (1ULL << d);
                    }
                }
            }

            uint64_t cur = base;
            for (int cand = 0; cand < T; cand++) {
                cur |= adds[cand];
                goodDest[((size_t)o * T + cand) * DL + k] = cur;
            }
        }
    }
}

// --------- edge weight: (u,t)->(v,t2) considering transfers after arrival ----------
static inline __int128 edge_weight(
    int N,
    const WeightSum47& wsum,
    const vector<long long>& w,
    const vector<int16_t>& ciLatest,     // size N*nodes
    const vector<uint64_t>& reachDest,   // size nodes*DL
    const vector<uint64_t>& goodDest,    // size (N*T*DL)
    int u, int t, int v, int t2
) {
    int nodes = N * T;
    const uint64_t* reachPtr = &reachDest[(size_t)(v*T + t2) * DL];

    __int128 total = 0;

    for (int o = 0; o < N; o++) {
        const int16_t* dp = ciLatest.data() + (size_t)o * nodes;
        int16_t cand = dp[u*T + t];
        if (cand < 0) continue;

        const uint64_t* goodPtr = &goodDest[((size_t)o * T + (int)cand) * DL];

        long long sumWdest = 0;
        // DL=21 fixed small loop
        for (int k = 0; k < DL; k++) {
            uint64_t m = reachPtr[k] & goodPtr[k];
            sumWdest += wsum.sum(m);
        }

        total += (__int128)w[o] * (__int128)sumWdest;
    }

    return total;
}

static inline string to_string_i128(__int128 x) {
    if (x == 0) return "0";
    bool neg = false;
    if (x < 0) { neg = true; x = -x; }
    string s;
    while (x > 0) {
        int digit = (int)(x % 10);
        s.push_back('0' + digit);
        x /= 10;
    }
    if (neg) s.push_back('-');
    reverse(s.begin(), s.end());
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long R;
    cin >> N >> R;

    vector<long long> x(N), y(N), w(N);
    for (int i = 0; i < N; i++) cin >> x[i] >> y[i] >> w[i];

    // deadlines: 11:00, 11:30, ..., 21:00
    array<int,DL> deadlines{};
    for (int k = 0; k < DL; k++) deadlines[k] = 60 + 6*k;

    // duration matrix
    vector<int> dur(N*N, 0);
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (i != j) {
        long double dx = (long double)x[i] - (long double)x[j];
        long double dy = (long double)y[i] - (long double)y[j];
        dur[i*N + j] = calc_dur_steps(dx, dy);
    }

    // eligible OD: dist >= 0.25R
    long double thr = 0.25L * (long double)R;
    long double thr2 = thr * thr;
    vector<char> eligibleOD(N*N, 0);
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (i != j) {
        long double dx = (long double)x[i] - (long double)x[j];
        long double dy = (long double)y[i] - (long double)y[j];
        long double d2 = dx*dx + dy*dy;
        if (d2 + 1e-12L >= thr2) eligibleOD[i*N + j] = 1;
    }

    int M;
    cin >> M;

    int nodes = N * T;
    vector<vector<Edge>> outSq(nodes), outCi(nodes);

    // read square flights; also trust input duration if slight mismatch
    for (int i = 0; i < M; i++) {
        int a, b;
        string ss, ts;
        cin >> a >> ss >> b >> ts;
        --a; --b;
        int dep = parse_time_idx(ss);
        int arr = parse_time_idx(ts);
        if (dep < 0 || dep >= T || arr < 0 || arr >= T) continue;
        // fix dur if needed
        if (dep + dur[a*N + b] != arr) dur[a*N + b] = arr - dep;
        outSq[a*T + dep].push_back(Edge{(uint8_t)b, (uint8_t)arr});
    }

    int K;
    cin >> K;

    // candidate destinations per city (pruning for speed)
    // 近いNEAR個 + 人口上位TOP個 を候補に
    const int NEAR = 8;
    const int TOP  = 4;
    vector<vector<int>> candTo(N);

    // precompute order by population
    vector<int> popOrder(N);
    iota(popOrder.begin(), popOrder.end(), 0);
    sort(popOrder.begin(), popOrder.end(), [&](int a, int b){ return w[a] > w[b]; });

    for (int i = 0; i < N; i++) {
        vector<pair<long double,int>> ds;
        ds.reserve(N-1);
        for (int j = 0; j < N; j++) if (j != i) {
            long double dx = (long double)x[i] - (long double)x[j];
            long double dy = (long double)y[i] - (long double)y[j];
            ds.push_back({dx*dx + dy*dy, j});
        }
        sort(ds.begin(), ds.end());
        vector<int> v;
        v.reserve(NEAR + TOP);

        // nearest
        for (int k = 0; k < (int)ds.size() && (int)v.size() < NEAR; k++) {
            v.push_back(ds[k].second);
        }
        // top-pop
        for (int idx : popOrder) {
            if (idx == i) continue;
            bool exists = false;
            for (int t : v) if (t == idx) { exists = true; break; }
            if (!exists) v.push_back(idx);
            if ((int)v.size() >= NEAR + TOP) break;
        }
        candTo[i] = move(v);
    }

    // square latest depart
    vector<int16_t> sqLatest;
    compute_latest_all_origins(N, outSq, sqLatest);

    // sqDeadline[od*DL + k]
    vector<int16_t> sqDeadline((size_t)N*N*DL, -1);
    for (int o = 0; o < N; o++) {
        const int16_t* dp = sqLatest.data() + (size_t)o * nodes;
        for (int d = 0; d < N; d++) if (d != o) {
            int od = o*N + d;
            for (int k = 0; k < DL; k++) {
                int lim = deadlines[k];
                sqDeadline[(size_t)od*DL + k] = dp[d*T + lim];
            }
        }
    }

    // circle latest depart (incremental)
    vector<int16_t> ciLatest((size_t)N * nodes, (int16_t)-1);
    for (int o = 0; o < N; o++) {
        int16_t* dp = ciLatest.data() + (size_t)o * nodes;
        // start at origin at any time
        for (int t = 0; t < T; t++) dp[o*T + t] = (int16_t)t;
    }

    WeightSum47 wsum(w);

    vector<uint64_t> reachDest; // nodes*DL
    vector<uint64_t> goodDest;  // (N*T*DL)

    vector<vector<PlanFlight>> answer(K);

    // DP buffers for route search
    vector<__int128> best(nodes);
    vector<int> parent(nodes);
    vector<uint8_t> ptype(nodes); // 1=wait,2=travel

    for (int plane = 0; plane < K; plane++) {
        // rebuild reachDest for current baseline schedule (transfers included)
        compute_reach_dest(N, deadlines, outCi, reachDest);

        // rebuild GoodDest for current baseline vs square
        compute_good_dest(N, deadlines, eligibleOD, ciLatest, sqDeadline, goodDest);

        // longest path DP on time-expanded graph
        const __int128 NEG = -((__int128)1 << 120);
        fill(best.begin(), best.end(), NEG);
        fill(parent.begin(), parent.end(), -1);
        fill(ptype.begin(), ptype.end(), 0);

        // allow start anywhere at 06:00 (time=0)
        for (int c = 0; c < N; c++) best[c*T + 0] = 0;

        for (int t = 0; t < T-1; t++) {
            for (int u = 0; u < N; u++) {
                int node = u*T + t;
                __int128 cur = best[node];
                if (cur <= NEG/2) continue;

                // wait
                int nodeW = node + 1;
                if (cur > best[nodeW]) {
                    best[nodeW] = cur;
                    parent[nodeW] = node;
                    ptype[nodeW] = 1;
                }

                // travel edges (pruned candidates)
                for (int v : candTo[u]) {
                    int dt = dur[u*N + v];
                    int t2 = t + dt;
                    if (t2 >= T) continue;

                    __int128 wEdge = edge_weight(N, wsum, w, ciLatest, reachDest, goodDest, u, t, v, t2);
                    int node2 = v*T + t2;
                    __int128 nv = cur + wEdge;
                    if (nv > best[node2]) {
                        best[node2] = nv;
                        parent[node2] = node;
                        ptype[node2] = 2;
                    }
                }
            }
        }

        // choose best at 21:00 (time = T-1)
        int bestNode = 0*T + (T-1);
        for (int c = 1; c < N; c++) {
            int node = c*T + (T-1);
            if (best[node] > best[bestNode]) bestNode = node;
        }

        // reconstruct flights
        vector<PlanFlight> flights;
        int curNode = bestNode;
        while (parent[curNode] != -1) {
            int p = parent[curNode];
            if (ptype[curNode] == 2) {
                int vc = curNode / T, vt = curNode % T;
                int uc = p / T, ut = p % T;
                flights.push_back(PlanFlight{uc, ut, vc, vt});
            }
            curNode = p;
        }
        reverse(flights.begin(), flights.end());
        answer[plane] = flights;

        // add to circle schedule + incremental update of ciLatest
        for (const auto& f : flights) {
            outCi[f.from*T + f.dep].push_back(Edge{(uint8_t)f.to, (uint8_t)f.arr});
        }
        relax_add_flights_incremental(N, outCi, ciLatest, flights);
    }

    // output
    for (int i = 0; i < K; i++) {
        cout << answer[i].size() << "\n";
        for (auto &f : answer[i]) {
            cout << (f.from + 1) << " " << fmt_time_idx(f.dep) << " "
                 << (f.to   + 1) << " " << fmt_time_idx(f.arr) << "\n";
        }
    }
    return 0;
}